When computer chess programs sulked…

Share on Facebook0Share on Google+0Tweet about this on Twitter0Share on LinkedIn9Email this to someoneShare on Reddit0

KnightIn the early development of computer chess programs, some programs manifested a very interesting characteristic. The programs appeared to be pouting/sulking. The observed behavior occurred when the computer found it was in a losing position and it started to make “stupid” moves giving away pieces and making nonsense checks with loss of material. This puzzled many of the developers until the underpinnings of the behavior were understood. This post explains how such a phenomenon could happen in a chess program.

Computer chess programs try to predict how a game sequence will transpire by analyzing moves, counter-moves, counter-counter moves etc. The brute force computational power that is available today was not available in the early days of chess computing, so the depth of the search had to be limited to a smaller number of moves, or to use chess programming parlance, plies.  Going very deep would mean the “think” time would become unacceptable.  From an earlier post, you may recall that, on average, each player can make about 30 moves. Each ply that the search engine looks deeper is a power of 30 positions or nodes to evaluate. For example, a program that searches 6 ply deep needs to evaluate 630 positions, which results in approximately 750,000,000 end nodes. So the initial programs only looked a fixed depth.  These programs had a “horizon” across which they could not see.

During the analysis of a given position, a program sometimes discovered an outcome that was unavoidable, for instance the loss of its queen.  That is to say, within its horizon it saw the loss of the queen as inevitable.  However, it found that if it interpolated an in-between move that though wasteful and irrelevant, forced its opponent to take some action, the loss of the queen was pushed beyond the horizon and therefore could not be seen. So the computer would play a check with its bishop that would be immediately be captured and now the queen loss was back inside the horizon again. The computer would play another stalling move, usually causing loss of material to try and “save” the queen. This would continue until there were no more interpolating moves left. Superficially, the play of the computer looked like it was sulking about the inevitable queen loss! This phenomenon is known as the horizon effect in chess programming.

How was this resolved? Programs had to search variable depth. In dynamic positions with piece exchanges taking place, the programs had to look down each playing line and evaluate only when the play was quiesced. This required a level of magnitude of complexity more than fixed depth programs were capable of at the time. Today’s modern programs all have variable depth programming in order to avoid this kind of behavior.  Computer chess programs will sulk no more!

 

The following two tabs change content below.

No comments yet.

Leave a Reply