Author: Roberto Waldteufel
Date: 20:03:07 04/07/99
Go up one level in this thread
On April 07, 1999 at 21:47:25, Christophe Theron wrote: >On April 07, 1999 at 20:57:55, Roberto Waldteufel wrote: > >>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. > >Yeah... Imagine: from tic-tac-toe in Basic to chess in assembly! One of the nice things about my compiler (PowerBasic) is that you can freely mix (compiled) Basic with 32-bit assembler, including the full set of Pentium 32-bit instructions, all the Math coprocessor instructions and MMX instructons being supported as well. I find this a very pleasant tool, and in fact my most speed-critical code is all written in assembler within the framework of the Basic programming language. I never did get to grops with the ubiquitous C. > > >>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. > >Isn't there any way to build a zugzwang detector? It may be easier than in chess >for some cases (for example some kind of free pawns in the back ranks may be >enough to prove you have at least a move that is not worse than doing nothing). >Just a silly idea from somebody that lives in another world! :) > In checkers it is often weakening to move men off the back rank, because this makes it easier for the opponent to get a king. I have tried very hard to devise some sort of detector for non-zugzwang positions because I wanted to be able to use null move in such cases, but I have so far failed to come up with anything. In the process of developping the program I have collaborated with Brian Hinkle, one of the world's top checker analysts (but not a programmer), and he could not think of any reliable way to detect non-zugzwang positions either. Although I have played competitive chess for many years, and I understand the positional features of chess reasonably well, I am not a very good checker player, so I have had to rely on advice from checker masters. My chess background has, however, given me a good head-start in grasping checkers. >Well, I admit that if your branching factor is already low you have maybe much >more to gain from other parts of the program... > > > >>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. > >So you do full width until QSearch? > Yes. Also Qsearch is full width but variable depth. Remember that in checkers, unlike chess, if you can capture then the rules insist that you *must* capture, so a capture-based Qsearch is necessarily full width because if any captures are possible, then there cannot be any legal non-capture moves. I just extend the search as long as there are legal captures, or as long as there is the threat of a capture by the other side. This latter point took a while to for me to realise, but it improved the quality of play quite noticeably. > >>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. > >Yes, thank you. Always nice to have some fresh air from outside the chess world. >:) > > > Christophe
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.