Author: Roberto Waldteufel
Date: 17:57:55 04/07/99
Go up one level in this thread
On April 07, 1999 at 20:25:42, Christophe Theron wrote: >On April 07, 1999 at 12:10:20, Roberto Waldteufel wrote: > >>Hi all, >> >>I wonder how many here have programmed other games besides chess. Before I wrote >>my chess program I cut my teeth on several games of gradually increasing >>complexity until finally I felt ready to tackle chess. One of the most >>interesting of these was checkers. In fact, I used bitboards for my first ever >>attempt at checkers before knowing about their widespread use in chess, so when >>I came to program chess I was naturally inclined to lean heavily in the >>direction of bitboard representations of information. Recently I returned to my >>old checkers program and rewrote it from scratch making use of many new things I >>have learnt from programming chess, resulting in a strong program based on Aske >>Plaat's MTDF algorithm. On 24 April there is to be a match between my program >>and Nexus99, one of the top commercial checkers programs. I may even release my >>own checkers program commercially in due course. >> >>I think the same techniques that have proved themselves in computer chess are >>applicable to several other games, such as Shogi, Go and of course checkers too. >>I would be interested to hear if anyone else here has found the same to be true. >>In particular, if anyone else has programmed checkers, it would be interesting >>to "compare notes". >> >>Best wishes, >>Roberto > > >Just by curiousity, does null-move or other threats detection techniques work >for checkers? > >I know it does not work in Othello/Reversi because zugzwang positions happen all >the time, but I suppose this is not the case in checkers? > >Can you tell us about selection techniques that work in checkers but do not >apply to chess? > >Just curious, I'm not planning to write any non-chess game playing program. I >went directly from tic-tac-toe to chess in the early '80s! > > > > Christophe Hi Christophe, Wow! Tic-Tac-Toe to chess is quite a leap. Regarding null move, I used it very successfully for chess, but I do not use it at all for checkers because of the reason you mention. In checkers zugzwang is very common indeed, and it is not confined to the endgame, as it is to a very high degree in chess: zugzwang with all 24 pieces still on the board is quite common in checkers. Don't forget that in checkers the aim is to deprive the opponent of any legal moves, so stalemate is a loss, not a draw. However, one form of pruning that seems to work well is connected with a learning process I have devised whereby the program learns through experience to recognise certain positions as "known losses". This is especially useful in the early phase of the game, since transpositions are much more abundant than in chess. Also, because captures are forced, the quiescence search is somewhat easier to implement than is the case in chess. The branching factor is much lower, so selectivity is not as crucial as it is in a high branching factor game like chess, but even so it would be nice to be able to prune away some of the duff moves. This is very difficult to do well, however. Blitz, a fairly strong shareware checkers program, does a "partially selective search", but I do not know any details of how this works. When my program plays against Blitz, I usually find that Blitz claims to search about twice as deep as my own program, but nonetheless my program often outsearches Blitz, so I conclude that the selectivity is far from perfect. I suspect that the benefits to be gained from selectivity in any game increase as the branching factor gets higher, although the risks are probably about the same, so it may be that in games with relatively low branching factors like checkers the risks outweigh the benefits, whereas in games with extremely high branching factors like Go it is practically essential to be selective. Chess occupies a middle ground between the two extremes, and I think it is no coincidence that the part of a chess game where null move selectivity is effective is also the part where the branching factor is at its highest, namely the middle game. One might even argue that in chess zugzwang is mainly an endgame phenomenon precisely because the branching factor goes down rather than because the number of pieces goes down. When the branching factor is high, it is less likely that every one of a large number of moves will prove to be bad. I hope this answers your query. Best wishes, Roberto
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.