Monday 22 October 2012

Beating engines in the middlegame : A tip

For a chess computer the middle game begins as soon its opening database can no longer be used. In the middle game there are usually about 30 to 40 moves possible on each move. This is known as the branching factor and the larger this is then the larger the search needed. When the computer is searching for moves, it will therefore need to search about 1000 positions for one move from each player, 1000000 positions for two moves from each player, 1000000000 for three moves from each player and so on. The depth of the search that it can do depends on the speed of the computer and on the amount of time it has available to move. The search algorithm that most of the more modern chess computers use is called the Selective Iterative-Deepening Search. This searching algorithm searches all possible moves to a depth of one first, then all possible moves to a depth of two, then all possible moves to a depth of three and so on. If the computer calculates that there is a checkmate or a loss of its queen for example then it terminates that branch of the search. This means that the computer doesn't have to continue searching a large number of moves from that branch, so it can use its memory to search to a greater depth on other branches of the search tree. A tip is that if for example you sacrificed your queen knowing that in three moves time you could get checkmate using other pieces then that branch of the tree might get terminated by the computer before it realises that its just fell for a mate in 3 which it now can't avoid. Some computers might not fall for this however as the very best computers would have still continued searching that branch of the search.

No comments:

Post a Comment