Chess program
| a | b | c | d | e | f | G | H | ||
| 8th |  |
 |
 |
 |
 |
|
|
|
8th |
| 7th |  |
|
|
|
|
|
|
|
7th |
| 6th |  |
|
|
|
|
|
|
|
6th |
| 5 | |
|
|
|
|
|
|
|
5 |
| 4th | |
|
|
|
|
|
|
|
4th |
| 3 | |
|
|
|
|
|
|
|
3 |
| 2 |  |
|
|
|
|
|
|
|
2 |
| 1 |  |
 |
 |
 |
 |
|
|
|
1 |
| a | b | c | d | e | f | G | H |
Two-dimensional chess board, as shown on the screen by many chess front ends
A chess program is a computer program that is able to play chess . It runs either on PCs or on chess computers specially made for playing chess . The development of chess programs is a discipline of computer chess .
While in earlier chess programs the entire functionality was combined in one program, modern chess software usually consists of two parts: the so-called engine - the actual chess program that calculates the moves played by the computer - and the chess front end , the display and the User interaction takes over. There are two widely used open chess communication protocols for communication between the chess engine and the front end : the XBoard protocol and the newer Universal Chess Interface (UCI) . The positions and games are saved in proprietary formats or in the open portable game notation format (PGN).
Current programs
One of the best-known free chess programs is Crafty , an open source project by Robert Hyatt . Another strong chess program is Fruit , which took second place in the 2005 World Computer Chess Championship. Up to version 2.1 Fruit is also available under an open source license, as is Glaurung 2.1, which is about the same strength.
The open source program Stockfish emerged from Glaurung. It is available for various operating systems with 32-bit or 64-bit architecture and is one of the most powerful chess programs ever. Because of its open development, Stockfish is not suspected of plagiarism. It is available for free.
Since 2014, the ranking lists , which are determined by means of games between the programs, have been headed head to head by the commercial program Komodo and the open source development Stockfish described above.
The commercial program Houdini has been one of the best playing for years, but it is controversial. The programmer of the chess program Rybka claims that source code was stolen from him and that various, very powerful chess programs ( IPPOLIT family) were created on this basis , including Houdini. No evidence has been provided - at least publicly - for this claim. The programmer of the chess program Rybka is said to be based on Fruit. Because of this controversy, Houdini - like some other programs of the Ippolit family - was temporarily not listed by various ranking list operators. In the further course of the program Rybka was classified as plagiarism by Fruit , whereby Rybka was stripped of all titles and successes. The Rybka programmer was banned from all computer chess tournaments for life. Houdini, on the other hand, which in turn is supposed to be based on Rybka, was then recognized to be the most powerful chess engine and was used together with the frontend aquarium for analysis at the World Chess Championships.
For beginners, there is a scalable engine that can be limited in rating like Ufim .
A user interface called a chess front end is required for convenient operation . The XBoard program, for example, can be used for this purpose . It runs under the operating systems Microsoft Windows (under the name WinBoard ), Unix / Linux and Amiga and is delivered together with GNU Chess. A graphical java -based chess frontend with database functions is the José , which is also published under the GPL . Another popular user interface on Windows for more than 250 chess programs is Arena , which is available as freeware. There is also other freeware that is suitable for beginners, such as Arasan . The KDE chess front end is Knights.
Ambitious players often resort to commercial programs that, in addition to the pure game of chess, also offer many additional options, such as game analysis and chess training. The Shredder and Fritz programs should be very well known . These programs are distributed among others by the Hamburg company ChessBase , which is increasingly dominating the (European) market for professional chess software. The Rybka program has made headlines in specialist magazines and computer forums since 2005 . Rybka has distinctive skills in positional or chess strategic terrain and is therefore closer to the human way of playing than most other chess programs. Rybka led the most important computer chess rankings - in which Houdini was not listed - with 50-150 points ahead. Chess grandmasters such as Anand, Topalov or Morozevich used Rybka for analysis, now Stockfish, Critter or Houdini are used more frequently.
You can now play high-quality chess on cell phones , PDAs and other handhelds . On Palm OS-based devices, for example, OpenChess is a free chess program that offers the choice between several chess engines.
With the free program ChessV you can also try out different chess variants .
construction
The main components of a chess program are the move generator , the evaluation function and a program part to control the search and the selection of the next move. Starting from the current position (game situation), the program carries out an iterative depth first search . In each iteration, it executes various move sequences in sequence, evaluates the positions reached (leaves of the search tree ) with the evaluation function, and based on these leaf values it evaluates the inner nodes of the search tree and thus also the moves that are in each case according to the minimax principle lead to a knot. After the last iteration, it plays the highest valued move in the root node (which represents the current position).
An important feature of a chess program is the type of internal board display that all other components of the program use.
Train generator and internal board display
| a | b | c | d | e | f | G | H | ||
| 8th | |
|
|
|
|
|
|
|
8th |
| 7th | |
|
|
|
|
|
|
|
7th |
| 6th | |
|
|
|
|
|
|
|
6th |
| 5 | |
|
|
|
|
|
|
|
5 |
| 4th | |
|
|
|
|
|
|
|
4th |
| 3 | |
|
|
|
|
|
|
|
3 |
| 2 | |
|
|
|
|
|
|
|
2 |
| 1 | |
|
|
|
|
|
|
|
1 |
| a | b | c | d | e | f | G | H |
The example of the
game position used in all of the following representations : 1. e4 e5 2. Nc3
The move generator generates a list of all legal (rule-compliant) moves in a certain position (possible movements of the playing pieces). In the starting position 20 moves are possible (16 pawn moves, 4 knight moves), in the further course of the game you can expect an average of about 40 legal moves in each position, in the endgame fewer. The move generator must also complicated features such reshuffles , Bauer conversions and En passant -Schläge considered.
As a rule, you let the train generator calculate all pseudo-legal moves, i.e. H. the rule of kings is ignored; z. B. such a move could move the king to a threatened square. This makes the train generator considerably easier and faster. The illegal moves are later sorted out by the part of the program for controlling the search: a move was illegal if the following move list contains a move that defeats the king.
The following integers are used in the examples to code the figures:
| figure | Coding | |
|---|---|---|
| White | black | |
| empty field | 0 | 0 |
| Farmer | 1 | 2 |
| tower | 11 | 21st |
| Jumper | 12 | 22nd |
| runner | 13 | 23 |
| lady | 14th | 24 |
| king | 10 | 20th |
| invalid field | -1 | -1 |
The implementation of the train generator is closely related to the internal board display. There are four important representatives here:
12 × 10 representation
| -1 (0) | -1 (1) | -1 (2) | -1 (3) | -1 (4) | -1 (5) | -1 (6) | -1 (7) | -1 (8) | -1 (...) |
| -1 (10) | -1 | -1 | -1 | -1 | -1 (15) | -1 | -1 | -1 | -1 (19) |
| -1 (20) | 21st | 22nd | 23 | 24 | 20th | 23 | 22 (27) | 21st | -1 |
| -1 | 2 | 2 | 2 | 2 | 0 (35) | 2 | 2 | 2 | -1 (39) |
| -1 | 0 | 0 | 0 | 0 | 0 | 0 (46) | 0 | 0 (48) | -1 |
| -1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | -1 |
| -1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | -1 |
| -1 | 0 | 0 | 12 | 0 | 0 | 0 | 0 | 0 | -1 |
| -1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | -1 |
| -1 | 11 | 0 | 13 | 14th | 10 | 13 | 12 | 11 | -1 |
| -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| -1 | -1 | -1 | -1 | -1 (...) | -1 (115) | -1 (116) | -1 (117) | -1 (118) | -1 (119) |
The game board is mapped onto a one-dimensional, 120-element array . The index (numbers in brackets) usually runs line by line, here from 0 (top left) to 119 (bottom right). In addition to the 64 valid fields, the array contains fields which a piece would reach when leaving the board and which form an edge around the regular board. A certain value (here -1) is stored on these squares, and if a piece were to move onto a square with this entry, it means that it would leave the board. This can easily be queried, since you have to check anyway whether the target space is occupied by your own figure, which would make the move illegal. This technique makes the train generator quick and easy. The left and right edge on each side only needs to be one square, because a knight who pulls sideways from the board always lands either on the left or right edge row.
By adding the following constants to a field index, the possible target fields for a figure on this field can be determined.
| Move | Constants |
|---|---|
| Horizontal and vertical movement (rook, queen, king) | -10, -1, +1, +10 |
| Diagonal movement (bishop, queen, king) | -11, -9, +9, +11 |
| Move like a jumper | -21, -19, -12, -8, +8, +12, +19, +21 |
Let us consider the black knight on square 27 (Ng8). Adding these constants to 27 results in the potential target fields: 6, 8, 15, 19, 35, 39, 46 and 48. If the value in the target field is -1, then the move is not possible because the knight would move over the edge . If the value is 1 or 10 to 14, there is a white piece on the field that can be captured, and if it is zero, a move to the empty field is possible. The knight can therefore make three different moves on the target spaces 35, 46 and 48, which are added to the move list. If the move generator is only supposed to generate legal moves - and not all pseudo-legal moves, you still have to consider whether the knight is tied up or whether there is a check that you have to fend off.
It is similar with the other types of figures. Those with long strides (queen, bishop, rook) cannot jump over an occupied space. After this has been reached, no further move is possible in this direction and you go to the next direction.
While the train generator is quite simple and fast, the static evaluation functions are slower.
8 × 8 representation
| 21st | 22nd | 23 | 24 | 20th | 23 | 22nd | 21st |
| 2 | 2 | 2 | 2 | 0 | 2 | 2 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 12 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 11 | 0 | 13 | 14th | 10 | 13 | 12 | 11 |
The 8 × 8 representation is closest to the human view. The GNU Chess program used them up to version 4. The board is modeled as a one-dimensional array, as is the case with 12 × 10, here with an index range from 0 to 63 (alternatively 1 to 64). A two-dimensional array seems closer, but is slower, because a field has to be designated with two numbers (row and line), a constant must be added to both when generating the move, and when accessing a field, the address calculation with two indices is more complicated .
The train generator is usually more complex and slower than with the 12 × 10 display, since the special cases at the edge have to be dealt with separately. The static evaluation function works more efficiently, however, because the row and line on which a field is located can be determined with fast bit operations : AND operation of the index with 7 results in the line and shifting to the right by 3 bits results in the row (with row-by-row field arrangement and index range 0 to 63). With the 12 × 10 board, however, you have to divide by 10. The scoring function often needs this information, e.g. B. for double pawns or Isolani recognition.
Even with the 8 × 8 board, trains can be generated quickly and easily using table access, but this increases memory consumption considerably. GNU Chess uses a two-dimensional array nextpos with 64 by 64 elements for each type of figure , the entries of which are calculated in advance. If you index it with the starting square f of a piece and one of its target squares, you can read off the next target square for the piece. nextpos (f, f) returns the first target field. For the long-stepped pieces there is also the array nextdir , from which the next target field is read when the target field is occupied (first field in a new direction of movement). If there is no longer a target field, both return the value f .
Another possibility is a three-dimensional array that contains all target fields for all fields and figure types that this figure can reach from this field. The third index runs over these target fields. The memory consumption is lower here, especially if a two-dimensional array of pointers is used, each pointing to a Halden array of the appropriate size, corresponding to the different number of target fields. The entries are in two parts: the first part is the target field index and the second is the number of fields following in the array that are to be skipped if the target field is occupied (or directly the next index in the array).
0x88 representation
This is a further development of the 8 × 8 display. In the line-by-line display with 16 fields per line, the left area of 8 by 8 fields forms the chessboard, the right area of 8 by 8 fields is not used. If a figure would move over the edge, this can be recognized by the bit-wise ANDing of the target field index with the hexadecimal number 0x88 (= 136). If the result is zero, the square index indicates a valid square, otherwise the piece would leave the board. The row and line of a field can be calculated similarly to the 8 × 8 board by shifting 4 bits to the right or ANDing with 7.
With this representation you can also use the index difference between two fields to determine whether and with which piece a move from one field to the other is possible. For example, a tower move is possible if the difference is in the range -7 to 7 or a multiple of 16. This is not possible with the 8 × 8 or 10 × 12 representation, because the criterion is also met by field pairs that do not allow a corresponding move. The squares h4 and a5, for example, have an index difference of less than 8, although no rook move is possible.
Bitboards
Some modern chess programs, such as Rybka , Crafty or GNU Chess 5, use bitboards . These can be implemented particularly efficiently on 64-bit computer architectures , where the number of bits in a register / word corresponds to the number of fields. Each bit position in a word is assigned to a field on the board, and the bit at that position provides an indication of the corresponding field.
The following example shows the position after moves 1. e4 e5 2. Nc3 with eight 64-bit registers. The register Bcontains a 1-bit wherever there is a pawn (of any color) on the corresponding field. There is also a register for the other types of figures. WEIand SCHindicate where a white or black figure is located. For the sake of clarity, bits with the value 0 are represented by -.
Reihe 8 7 6 5 4 3 2 1
Linie abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh
Bitposition 63 56 48 40 32 24 16 8 0
Registername | | | | | | | | |
| | | | | | | | | |
Bauern B -------- 1111-111 -------- ----1--- ----1--- -------- 1111-111 --------
Türme T 1------1 -------- -------- -------- -------- -------- -------- 1------1
Springer S -1----1- -------- -------- -------- -------- --1----- -------- ------1-
Läufer L --1--1-- -------- -------- -------- -------- -------- -------- --1--1--
Damen D ---1---- -------- -------- -------- -------- -------- -------- ---1----
Könige K ----1--- -------- -------- -------- -------- -------- -------- ----1---
Weiss WEI -------- -------- -------- -------- ----1--- --1----- 1111-111 1-111111
Schwarz SCH 11111111 1111-111 -------- ----1--- -------- -------- -------- --------
With fast bit-wise operations , information about the position can now be calculated for all fields in parallel. For example, T & WEIall positions of the white rooks can be determined by the AND operation , and ((B & SCH) >> 8) & ~(WEI | SCH)provides a bit pattern with the fields on which a black pawn can move with a single step. >> The bit shift to the right (to the lower end) denotes the ~ negation and | the OR link.
Evaluation functions
The evaluation function provides the heuristic evaluation of a position without determining the successors. It is composed of a material and a positional component. The positional component complements the material one, as the strength of the pieces also depends on their positions among each other. Simplified evaluation functions can also be carried out by human players, but this is only of historical significance. Computer programs very often show the evaluation of a game situation numerically (in so-called pawn units ), with positive values indicating advantages and negative values indicating disadvantages for a certain player.
material
For the material scoring, values are added up for the pieces on the board. The approximate value of the types of pieces in 1/100 pawn units is given in the following table.
| Farmer | Jumper | runner | tower | lady |
|---|---|---|---|---|
| 100 | 310 | 320 | 460 | 900 |
The white pieces (or those of the party to move) are counted positively and the black pieces (or those of the following party) are counted as negative. The king does not need to be counted as both parties have a king during the entire game.
position
The positional determine standings, is a task of greater complexity, the different chess programs differ from each other in the clear. It remains a well-kept secret with commercial programs. In positional scoring, an attempt is made to assess positions based on chess-relevant parameters. Chess-relevant parameters can be roughly classified into king security, pawn structure, controlled and threatened fields as well as piece development. For example, a position in which the rooks are still narrowed between knights and pawns is rated worse than one in which the rooks are already on open lines.
Within these categories there are virtually any number of parameters (for pawn structures, for example, passed pawns , double pawns , levers , rams , isolani , pawn chains ; for king security, for example: can the king castle easily left or right? Can he stay in the center? Are pawns in front of the King?). It makes sense to first extract these parameters from the given position in a value-neutral manner. Chess programmers have to decide how much computing time they should spend on the positional component of a sophisticated evaluation function, and which parameters should even be included: The deeper the chess programs can analyze the search tree, the sooner the conversion of positional advantages into material advantages becomes visible.
Static evaluation function
If a chess program can efficiently determine the values of these parameters per position, they must be weighted among each other. The weighting of the positional component can partly be done automatically by analyzing chess databases or by playing against other chess programs. If this happens in advance of the program development, one speaks of a static evaluation function. Simply structured evaluation functions use positional weights for the six types of pawns for the positional component, but they turn out differently for the opening, middle and end game.
Except in borderline cases such as endgames or mate or stalemate situations, the evaluation function cannot deliver any objectively correct results. As the evaluation function combines the material and positional components into a single evaluation number, it enables the sorting and selection of the “best” or “worst” move.
Dynamic evaluation function
As a rule, the evaluation function is implemented by the programmer and is no longer changed during the game. An extended possibility is to determine comparable positions from a chess database during the game and thus to optimize the weighting of the positional parameters. This is more in line with the human approach. An experienced player takes into account criteria such as king's security or passed pawns, also taking into account known games and their results.
Control of search and train selection
Basically, the control of the search is based on the game tree . It contains, starting with the current position (root node), all moves of the attracting player, then again all possible response moves of the following player and so on, in each case up to reaching an end position (mate, stalemate, technical draw or repetition of positions). The game tree is usually much too big to be completely calculated, so the program is limited to a part of it (search tree).
In the simplest case, the program works according to the A strategy , i. H. it calculates all possible train sequences up to a certain depth (number of successive trains), which is limited by the computing power and the available time. Every position that arises is evaluated. If there is no end position such as a checkmate, the heuristic evaluation function is used. With the Minimax algorithm , the moves are rated in the root position and the highest rated is played.
Since the number of positions to be examined grows exponentially with depth, and on the other hand, a higher depth brings a corresponding improvement in skill level, a whole arsenal of acceleration measures has been invented in the approximately 50 years of program development, which can be divided into two areas. Some try to reduce the search tree using general computer science algorithms , for example:
- Alpha-Beta Search (Negamax Procedure)
- Hash table for the detection of train changes
- Zero move search
The alpha-beta search cuts off parts of the search tree that do not need to be considered to determine the highest rated move in the root node. This technique saves a lot: with good implementation, the achievable depth is almost doubled.
The limited computing depth often allows the program to overlook a tactical combination. To mitigate this, you deepen individual interesting move sequences, for example according to chess rules or moves that weaken the opposing king position in order to discover mate combinations more easily. The so-called recapture heuristic deepens move sequences that contain an exchange in order to better estimate the consequences of the exchange. The method of singular extensions ( German "isolated extensions" ) deepens the search for forced (forced) sequences of moves, i.e. in cases where there is only one single "reasonable" answer for one or both sides.
Further techniques for acceleration are the use of simplified evaluation functions according to move orders, which are judged to be of little use, as well as the incremental evaluation, which does not always recalculate the value of a position, but updates it when a move is made. Some programs do a large part of the evaluation work by analyzing the position of the roots and saving the results in data structures, which then simplify and accelerate the evaluation process considerably (e.g. figure-field tables).
Some programs do not (or not always) calculate all moves that are possible in a position ( B strategy ). The values of the trains are heuristically estimated, after which only the highly rated ones are included in the search tree. This mimics the behavior of a human player. The search tree becomes considerably smaller, but you run the risk that the heuristic will sometimes miss a good move. These procedures are much more difficult to implement than the A strategy. They also cannot be easily transferred to other games such as Go , because the criteria for selecting a move are completely different.
You must not abort the calculation and carry out the leaf evaluation if the lot is in the middle of an exchange, this would result in a distorted material balance. If a party has just defeated a covered piece and is rated here, you receive a false material overweight for this party. A remedy that is often used is the so-called quiesence search: In a position on the leaf, all punch moves are calculated, and then only the punching response moves, etc., whereby the less promising moves are usually cut off, and the maximum length of the Impact sequence limited so that the whole thing does not take too much time. In every position reached in this way, the hand evaluation is carried out by the heuristic evaluation function, and the value of the position is the maximum of the hand value and the values of the pulls. The hand value stands for the values of the non-capturing moves, because every move could be a mistake and it is best not to capture here.
Libraries and databases
Opening library
Chess is played for time in competition, which means that only a defined time is available for a number of moves. Many chess programs are therefore equipped with an opening library in which a large number of “good” move orders in the opening phase of chess games are stored. In the initial phase of the chess game, the program looks up in this library which move is the most suitable in a particular position on the board. This "checking" is faster than calculating the pull. The computing time saved in this way is then available to the program in later phases of the game. The process of saving board positions including the “good” moves is only useful for the opening and the endgame, as the number of board positions is still manageable here. Opening libraries of commercially available programs are growing in size. They are mostly generated from master games. This harbors the risk that unnoticed errors that the program would not play based on its own calculations will also be accepted.
The coordination of the opening library with the evaluation function used later in the game plays a large part in the playing strength.
Endgame database
In the endgame , when there are only a few pieces left on the board, you can calculate the optimal move in advance using a full analysis ( brute force method ). There are quite a few endgame positions in which human thinking, but also computer analysis in real time, would be completely overwhelmed. Many chess programs therefore use endgame databases that contain all possible positions with 3, 4, 5 or even 6 pieces as well as their outcome (if the game is optimal). The creation of endgame databases goes back to Ken Thompson . The first six stone figures were fully calculated by Lewis Stiller in 1991.
Chess database
Chess databases contain games that have been played. They help, for example, with studying openings and preparing for the next opponent.
Opening libraries can be generated from the database for chess programs. It is also possible to determine comparable positions from a chess database during the game and to optimize positional evaluation parameters (see above) taking into account the course of the game recorded there (dynamic evaluation function).
history
The history of the chess program is very closely related to the history of the chess computer and can usually not be treated separately. Only developments of the basic algorithms are described here. For the media-effective competitions with world-class players in recent years, see Chess computers in the game against people .
Konrad Zuse
In the years 1942 to 1945 Konrad Zuse wrote the world's first chess program in his newly developed programming language, the Plankalkül . The language was first implemented in the 1970s.
Alan Turing
The British mathematician and code breaker Alan Turing developed a method that assigns a value to every possible move. The best move should always be calculated. Turing's chess program was based on the following principles:
- Each piece received a certain value: pawn = 1; Jumper = 3; Runner = 3.5; Tower = 5; Queen = 10 and King = 1000 (so that this could never be sacrificed).
- All white moves and all black counter moves were examined. If White was able to make a stroke, then all of the opponent's strokes, all of White's subsequent strokes, etc. were examined until the position was "dead", that is, until there were no further strokes and no mate. A figure count was carried out in the resulting positions and the move selected which gained the most material or lost the least. However, since most of the moves available for selection delivered the same result (close to zero), especially in the opening phase, Turing also introduced some positional evaluation criteria, such as mobility (possible moves), possibility of hitting, castling or threat of checkmate.
| a | b | c | d | e | f | G | H | ||
| 8th | |
|
|
|
|
|
|
|
8th |
| 7th | |
|
|
|
|
|
|
|
7th |
| 6th | |
|
|
|
|
|
|
|
6th |
| 5 | |
|
|
|
|
|
|
|
5 |
| 4th | |
|
|
|
|
|
|
|
4th |
| 3 | |
|
|
|
|
|
|
|
3 |
| 2 | |
|
|
|
|
|
|
|
2 |
| 1 | |
|
|
|
|
|
|
|
1 |
| a | b | c | d | e | f | G | H |
Position after the 29th move
Since there were no suitable programmable calculators at the time, Turing had to calculate each move by hand on paper himself, which meant a lot of time. At least the functional principle, according to which all today's chess programs still work, was evident. The first batch of his "paper machine" took place in 1952 and should be listed here as an example:
- Turing's paper machine - Alick Glennie, Manchester, 1952
- 1. e4 e5 2. Nc3 Nf6 3. d4 Bb4 4. Nf3 d6 5. Bd2 Nc6 6. d5 Nd4 7. h4 Bg4 8. a4 Nxf3 + 9. gxf3 Bh5 10. Bb5 + c6 11. dxc6 0–0 12. cxb7 Rb8 13. Ba6 Da5 14. De2 Nd7 15. Rg1 Nc5 16. Rg5 Bg6 17. Bb5 Nxb7 18. 0–0–0 Nc5 19. Bc6 Rfc8 20. Bd5 Bxc3 21. Bxc3 Qxa4 22. Kd2 (22. h5 would have the bishop 22.… Ne6 23. Rg4 Nd4 (23.… Rxb2 24. Bxb2 Rxc2 +) 24. Qd3 Nb5 25. Bb3 Qa6 26. Bc4 Bh5 27. Rg3 Qa4 28. Bxb5 Qxb5 29. Qxd6 Rd8 0: 1
There are also implementations for today's computers for the “paper machine”.
Claude Shannon
On March 9, 1949, Claude Shannon gave a lecture that was crucial for the development of chess programs at Bell Laboratories . There he described the internal board display, the tree search , the evaluation function and the move search with the help of the Minimax algorithm . He has already given two different strategies for determining the best move: A strategy and B strategy .
Dietrich Prinz
In November 1951 Dietrich Günter Prinz from the University of Manchester created a program for the Ferranti-Mark-I-Computer (GB) that solved a two-part mating task in 15 minutes. The program is considered to be the first solving program in chess history.
John von Neumann
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| initial position |
John von Neumann classified the game of chess in his game theory as a two-person zero-sum game with complete information. This class of problems (including tic-tac-toe ) can be solved with the minimax algorithm . However, chess is too complex to be able to completely work through the search tree. Chess programs are therefore dependent on approximation methods.
John von Neumann's chess program was completed in the mid-1950s and ran on the MANIAC I tube computer installed in 1950 . For the sake of simplicity, it was only played on a 6x6 board. The program played a total of three games: the first against itself, it lost another against a strong chess player, although the latter gave him a queen, and the third won it against a young woman who had only been playing chess for a week and especially for this Had trained game.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Position after the 21st move |
- MANIAC I - Man, Los Alamos, 1956:
- (6 × 6 board without bishop, no double step or castling)
- 1. d3 b4 2. Nf3 d4 3. b3 e4 4. Ne1 a4 5. bxa4 (5.Nd2 and 6.Nc4 + Nxc4 7. bxc4 with good play) 5.… Nxa4 6. Kd2 Nc3 7. Nxc3 bxc3 + 8. Kd1 f4 9. a3 Rb6 10. a4 Ra6 11. a5 Kd5 12. Da3 Qb5 13. Da2 + Ke5 14. Rb1 Rxa5 15. Rxb5 Rxa2 16. Rb1 (to prevent 16.… Ra1 mate) 16.… Ra5 17. f3 Ra4 18. fxe4 c4 19. Nf3 + Kd6 20. e5 + Kd5 21. exf6 (= D) 21.… Nc5 (22. Qxd4 + Kc6 23. Ne5 mate.) 1: 0
For the first time a person has lost to a chess program. This simplified chess variant is also called Los Alamos Chess .
In 1957, the IBM employee Alex Bernstein implemented a chess program on an IBM 704 that played according to the standard rules. It selected the seven most plausible moves in each position and carried out a search of 4 half-moves, which required about 8 minutes of computing time. Bernstein received support from the American grand master Arthur Bisguier during the development . The program lost without a chance against chess master Edward Lasker , who, however, certified the computer to be an acceptable amateur level.
In 1958, the alpha-beta search was discovered by Allen Newell , John Clifford Shaw and Herbert A. Simon and brought a huge boost in performance.
Richard Greenblatt
| a | b | c | d | e | f | G | H | ||
| 8th | |
|
|
|
|
|
|
|
8th |
| 7th | |
|
|
|
|
|
|
|
7th |
| 6th | |
|
|
|
|
|
|
|
6th |
| 5 | |
|
|
|
|
|
|
|
5 |
| 4th | |
|
|
|
|
|
|
|
4th |
| 3 | |
|
|
|
|
|
|
|
3 |
| 2 | |
|
|
|
|
|
|
|
2 |
| 1 | |
|
|
|
|
|
|
|
1 |
| a | b | c | d | e | f | G | H |
Matt position after move 37
The first program to participate in human tournaments was Mac Hack , developed by Richard Greenblatt at MIT from 1965 to 1967 .
- Hubert Dreyfus - MacHack, MIT, 1967
- 1. e4 e5 2. Nf3 Nc6 3. Bc4 Nf6 4. Nc3 Bc5 5. d3 0-0 6. Ng5 Sa5 7. Bd5 c6 8. Bb3 Nxb3 9. cxb3 h6 10. Nh3 d5 11. exd5 Bg4 12. f3 Bxh3 13.gxh3 Nxd5 14.Nxd5 Qxd5 15. Bd2 Qxd3 16.b4 Be7 17.Rg1 e4 18.fxe4 Bh4 + 19.Rg3 Bxg3 + 20.hxg3 Qxg3 + 21. Ke2 Qxh3 22.Qg1 h5 23.Bc3 g6 24.Qf2 h4 25. Qf6 Qg4 + 26. Kd2 Rad8 + 27. Kc2 Qxe4 + 28. Kb3 De6 + 29. Qxe6 fxe6 30. Rh1 Rf4 31. Be1 Rf3 + 32. Ka4 h3 33. b5 Rd4 + 34. b4 cxb5 + 35. Kxb5 Ra3 36. Kc5 Rd5 + 37. Kc5 # 0: 1
From 1967 to 1970 there was a boom in chess programming, which resulted in the first computer chess championship in history , which was held by the Association for Computing Machinery (ACM) . The winner was Chess 3.0 .
Peter Jennings
In 1976 Peter Jennings developed Microchess for the KIM-1 home computer. The program was sold over 50,000 times by 1979, making it the first commercially successful microcomputer program. Due to the only 1152 bytes RAM memory, castling , en passant and pawn conversion were not implemented.
Ken Thompson
Ken Thompson developed the famous Belle chess machine in 1979 , which worked with an opening library and hashtables .
Feng-hsiung Hsu
The first computer program that beat a reigning world chess champion in a regular tournament game was Deep Blue . Developed by IBM due to excitation and under the direction of the young computer scientist Feng-Hsiung Hsu, this program defeated on February 10, 1996 to an adapted and optimized for chess computer hardware, which also originated from IBM, the then world champion Kasparov in a characterized known become part . Garry Kasparov was able to win the competition with 4 to 2. An improved version of Deep Blue, however, took this hurdle on May 11, 1997 and achieved overall victory over Kasparow with 3.5 to 2.5 in a second competition with the sixth tournament game. Deep Blue was dismantled and mothballed after the spectacular victory. The origin of the program was later described in a book by the inventor.
Chrilly Donninger and Ulf Lorenz
The first who, after Deep Blue, relocated to the construction of specialized chess hardware components as the basis for a chess program, was the Austrian chess programmer "Chrilly" Donninger, who had previously participated in computer chess tournaments with his PC program for years. From 2002 he designed a chess computer with hardware that he modified himself, which he initially called Brutus. Funding ChessBase withdrew its support after the poor performance at a tournament in Graz in 2003; Christian Donninger and Ulf Lorenz initially pursued the project on their own under the new name Hydra . In 2004 Donninger and Lorenz found a new sponsor from the Arab Emirates, PAL Computer Systems . In the same year Hydra beat the then computer world champion Shredder . In June 2005 , a competition took place under tournament conditions against the British grandmaster Michael Adams , who was seventh in the world rankings at the time, which Hydra won with 5.5 to 0.5. This corresponds to a tournament performance of over 3100 Elo points, more than anyone has ever achieved. In this version with 64 processors, Hydra was currently the most powerful existing chess-playing computer system in the world.
Current developments
The distribution of the computing effort over many individual sub-processes, which can run in parallel and thus use multi-processor systems sensibly, is not trivial due to the tree search and is a current research area of chess programming (see Hydra ).
In the field of conventional PC chess programs, the parallel use of several processor cores has been possible for a number of years and is carried out through the so-called "deep versions" of the respective engines. This development followed on from the increasing spread of the corresponding PC hardware with multi-core processors. The same now applies to operating systems with 64-bit architecture and special chess program versions that support them advantageously or run faster on them than the 32-bit versions.
A possibly new trend is the use of a particularly large number of CPUs, but in contrast to Hydra based on conventional computers, combined into so-called clusters. Tournament stakes of the engines Toga and Rybka on cluster hardware have become known.
Competitions
There are various competitions in which chess programs measure each other in terms of their skill level, rarely also against human chess players. One of the most important is the (open) computer chess world championship , the World Computer Chess Championship (WCCC) , which has been held since 1974 and is open to all types of hardware and software . The oldest event was the North American Computer Chess Championship (NACCC), held from 1970 to 1994 . In addition, from 1980 to 2001 there was a special world chess championship for microcomputers only , the World Microcomputer Chess Championship (WMCCC) .
Elo ratings
| rank | Surname | Points |
|---|---|---|
| 1 | Stockfish 8.0 x64 12CPU | 3543 |
| 2 | Houdini 5.0 x64 12CPU | 3538 |
| 3 | Komodo 10.3 x64 12CPU | 3485 |
| 4th | Gull 3.0 x64 12CPU | 3248 |
| 5 | Fritz 15 x64 12CPU | 3175 |
| 6th | Deep Shredder 13 x64 1CPU | 3153 |
| 7th | Ginkgo 1.8 x64 4CPU | 3150 |
| 8th | Jonny 8.00 x64 4CPU | 3143 |
| 9 | Rybka 4.1 x64 12CPU | 3133 |
| 10 | Andscacs 0.871 x64 4CPU | 3130 |
Chess programs can also be given an Elo number that describes their skill level. For comparison: A world chess champion of today is in the range of Elo 2850. The Elo numbers in computer rankings cannot be easily compared with those of human chess players, since they were determined almost exclusively through games between computers. With regard to the absolute size of the valuation numbers, there is no calibration between the performance scales of human master players and those of chess programs; this would require very numerous serious competitive games between the two groups of players. I.e. the number level in pure computer rating lists must necessarily be based on a plausible or practical assumption, and the concrete results of the programs against each other merely determine the ranking and the distances between their ratings.
Because of the fundamentally different methods of people and computer programs when playing chess, a high level of skill against another chess program does not necessarily mean a correspondingly better performance against a human opponent. Competitions between chess programs therefore only say something about the level of play against people to a limited extent. However, practice has shown that a high level of skill against programs usually also means a high degree of skill against people. The Rybka program was able to win against various grandmasters - some with a pawn handicap . Other programs are now even stronger.
An assessment of the playing strength of chess programs and chess computers is also possible with the help of a set series of chess problems. For example, a test called BT2450 consists of 30 positions, for which the respective solution move can be found. From the times required for all positions, a BT2450 test value is calculated, which is comparable to a limited extent with the Elo number of human players. There are now other, sometimes more extensive and / or more difficult tests that are created and used within the computer chess community.
See also
swell
- ↑ CCRL 40/4
- ↑ CCRL 40/40
- ↑ CCRL 404FRC
- ↑ a b CEGT 40/4
- ↑ CEGT 40/20
- ↑ a b CEGT ranking list , accessed on February 5, 2017
- ↑ Plagiarism allegation against computer chess world champions , Heise.de, March 1, 2011
- ↑ WBEC Ridderkerk ( memento of August 6, 2011 in the Internet Archive ), accessed on March 1, 2011
- ↑ Arasan website , accessed March 1, 2011
- ^ Sourceforge.net , accessed March 1, 2011
- ↑ Raúl Rojas et al. a .: Konrad Zuses Plankalkül - Its genesis and a modern implementation. ( Memento from April 23, 2012 in the Internet Archive ) FU Berlin, FB Mathematics and Computer Science
- ↑ a b c Dieter Steinweder, Frederic A. Friedel: Chess on the PC , market and technology, hair b. Munich 1995, ISBN 3-87791-522-1 , pp. 33-35
- ↑ Frederic Friedel: Reconstructing Turing's “Paper Machine” (English) from ChessBase, accessed on December 7, 2017
- ↑ Eric van Reem: History of the computer chess . January 2003. Retrieved July 21, 2010
- ↑ Feng-hsiung Hsu: Behind Deep Blue. Princeton University Press Princeton and Oxford 2002, ISBN 0-691-09065-3 .
- ↑ heise online - Computer chess: Grandmaster of Hydra outclassed.
literature
- Rainer Bartel, Hans-Joachim Kraas, Günther Schrüfer: The great computer chess book. Data Becker, Düsseldorf 1985, ISBN 3-89011-117-3 (good introduction to programming computer chess with examples in BASIC )
- Computer chess and games (CSS). 1/1986 to 6/2004 (after that only online); Magazine mainly on the subject of computer chess.
- Claude Shannon : Programming a Computer for Playing Chess. In: Philosophical Magazine. 1950/41, pp. 256-257
- Claude Shannon: Programming a Computer to Play Chess. In: Scientific American. 2/1950, pp. 48-51
- Dieter Steinwender , Frederic A. Friedel : Chess on the PC. Markt und Technik, Haar bei München 1995, ISBN 3-87791-522-1 (history of computer chess, didactic chess program with sources in BASIC and C , incl. CD)
Web links
- Page by Ed Schröder Author of Rebel and ProDeo, a lot of information about computer chess and detailed descriptions of the inner workings of Rebel (English)
- Chess program Micro-Max Chess program in C with less than 2000 bytes of source code (English)
- The world's first chess program as a modern Java applet
- The alphabet algorithm: how do I get my computer to play chess? B. Monien, U. Lorenz & D. Warner (2006).
- 9th Computer Chess World Championship from June 14th to 20th, 1999 in Paderborn Report on TeleSchach
- Online continuation of the former magazine Computerschach und Spiele
- SSDF computer ranking
- IPON Ponder ON computer ranking
- Microchess - the first microcomputer chess program
- Chess Programming Wiki
