The chess board
The computer works only with numbers. So the computer sees the chessboard as 64 addresses in his memory. Each address represents a field. The number that is saved under an address says the computer which piece on the field is. One address is behind the previous and the computer can access those addresses with an index (for programmers: It is an array).
This description was really abstract. I will try to make the situation more clear with an example.
Imagine you're sitting in front of a bureau with 64 drawers. Those drawers are numbered from 1 to 64. You have also numbered a chessboard, so that each drawer corresponds to a field of the chessboard. If a piece is on a field on the chessboard, the same piece is also in the drawer that corresponds to the field. Of course you can't see the chessboard (the computer can't see the board, too), but if you want to know which piece is on the field with the number 12, for example, you can look in the corresponding drawer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 The chess rules
The most important rule of chess is the movement of the pieces. Most of the other rules bases on this rule. Because the computer can only work with numbers, we have to express the movement of the pieces in a mathematical way.
Let's go back to the example of the commode. If you want to move a piece on the real chessboard, you would just shift the piece from one field of the board to another. You can't do that with your commode. To move a piece you have to take the piece out of a drawer and put it in another one. But you can't put it in any one cause you could make an invalid move. On a chessboard, you can't move from one to any field too. But on the chessboard, you have easy rules lie "one field in each direction (king)" or "always a L (knight)". With our commode, it is really difficult to follow such geographical rules because we have only drawers with numbers on them in front of us.
Let's view which fields a knight can move to from field 29:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
- to field 19 (19 - 29 = -10)
- to field 12 (12 - 29 = -17)
- to field 14 (14 - 29 = -15)
- to field 23 (23 - 29 = -6)
- to field 39 (39 - 29 = +10)
- to field 46 (46 - 29 = +17)
- to field 44 (44 - 29 = +15)
- to field 35 (35 - 29 = + 6)
And from field 37?
- to field 27 (27 - 37 = -10)
- to field 20 (20 - 37 = -17)
- to field 22 (22 - 37 = -15)
- to field 31 (31 - 37 = - 6)
- to field 47 (47 - 37 = +10)
- to field 54 (54 - 37 = +17)
- to field 52 (52 - 37 = +15)
- to field 43 (43 -37 = + 6)
Did you remark something? We can express each possible move of the knight with a simple addition or subtraction. If we take the knight from one drawer and put it into another one 10 drawers away, we made a valid move. Also the way of moving of the other pieces can be expressed with additions and subtractions - just try it!
Of course has the computer to check for checks or if he crosses the border of the chess board if he makes a move. We do not go into the detail of these control structures; they will be treated in the practical part.
The evaluation of a position
A good chess player has to do more than only know the rules. The computer can't easily choose a move randomly and hope the best. To see if a move is good or not, the computer evaluates the position that will be build if he makes the move. So the computer can find the best move. To evaluate a position, the computer counts the material of both sites, the structure of the pawns, the occupation of the center and many other things.
Searching the best move
To look for the best move, the computer generates a so-called move tree. To make this he generates a node for each valid move of a position. Of course, to calculate only the next one move is really weak and will not make good results. So the computer goes to each node, executes the move on his board and calculates all valid moves again. This will repeat until the computer reached the search deep.
If an end node is reached, i.e. a node the computer generates no more sub-nodes for; the end node will be evaluated.
Now the computer chooses the best move. Therefore he uses the "Minimax" Algorithmus. This algorithmus says that each player moves in a way that maximize his advantage or that minimize the advantage of the enemy. This means if the computer evaluates the value of a node that is not a end node, he first look if the node belongs to one of his own moves or to one of his enemy. If it is one of his moves, the node takes the value of the highest valued sub-node. If not, the node takes the value of the lowest valued sub-node.
After some calculation time, all sub-nodes of the root have values. Now the computer chooses the best and executes it as his move.
The theory