Back Up Next

Pondering

What to do when it's your opponent's move

A chess program can think about the position for a specified time, makes what it thinks is the best move, sit back and wait for the opponent to move, and when the move comes in, repeat the process.

This is very easy to program, but it has the disadvantage of wasting a lot of processor time, since the program is sitting there idle when the opponent is thinking.

In some books on human chess, there are ideas about what to do when it's not your move.  One idea is to think of strategic aspects while your opponent is thinking, and then concentrate on specific lines when it is your move.  This might be a good idea for humans, but if it's possible to do in a computer chess program, it is not easy.

When I took my program to the Hong Kong WCCC in 1995, I thought I had this problem solved properly.  When it was the opponent's turn to move, my program would pretend it was the opponent, and just sit there and think.  When it came to be my program's turn to move again, it had its hash tables primed with interesting stuff and burned through the first few plies very quickly.

A better way, I think

This worked well enough that my program didn't finish in last place, but at that tournament I learned about a better way to do it, which I think that everyone is doing now (and probably was then).  This technique is called pondering or something that is translated as permanent brain if you are German.  I don't speak German, but it's possible that a better translation might be "continuous thinking".

When your program moves, it has a principal variation that it has constructed.  This principal variation is usually more than one move long.  The first move in the principal variation is the one that is made on the chess board, but the rest of it has some utility other than just being something that you'd display on the screen.

The second move is the move that the program thinks that the opponent will make.  It's often a pretty good move, and in many cases it is the move that the opponent finally does make.

It is possible to gamble that the opponent will make this move, and tell the program that the opponent did in fact make the move.

So while the opponent is off trying to select a move, your program had made a guess about which move will be selected, and is considering a reply.

The your program's guess was correct, you've gotten a big head-start toward selecting your next move, and it's even possible that your program might decide that it's thought about this move for long enough, and move instantly.

This leads to a situation often observed in games between two computers.  One program will think about a move, and then make it.  The second one will reply instantly.  The first one will think again and make a move, to which the second one will reply instantly again.  This can happen for many consecutive moves, until the second program has accumulated so much extra time on its clock that it feels that it doesn't need to move instantly.

If the opponent doesn't make the predicted move, your program will simply undo the mis-predicted move, execute the one that was actually made, and begin thinking about a move of its own.

Another idea

At the 1995 WCCC, my program had the privilege of playing Hitech.  My program got a lost position and started thinking for a long time.  Rather than thinking on the move that it thought my program would play, for the entire time that my program was thinking, Hitech eventually decided that it had thought for long enough about that particular move, and went onto the next one.  If my program made any of the ones that Hitech had already thought about, it would move instantly.

I don't know if this is good or bad, but it's another approach that is worth considering.

Strength increase due to pondering

I have no idea, but it results in deeper searches and/or less time consumed, so there must be some.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 11/04/02