Author: Dave Gomboc
Date: 22:42:11 04/08/99
Go up one level in this thread
On April 09, 1999 at 00:00:55, Roberto Waldteufel wrote: [snippage] >I'm not too sure about Reversi/Othello, but for checkers I do not count captures >or promotions as plies, which is exactly the same technique I use for chess, >along with many (most? all?) other chess programmers. I agree with you that it >is the similarities rather than the differences between different games that is >interesting. A basic template algorithm like PVS or MTDF can be applied to many >games, and the "skeleton" of the program for different games will be pretty much >the same. The programs tend to look very different because the "flesh" is >game-specific. No program is going to perform well without a substantial amount >of game-specific enhancements like opening book, endgame databases, evaluation >function, move generator and so on: all these things will depend on the details >of the individual game, and tend to obscure the fundamental similarity of the >search mechanism. But the underlying structure and problems remain the same. Every move is a capture in Othello. So, any extensions would probably have to be more specific than captures, anyway. :-) >In essence the qsearch for any game needs to extend positions where a radical >change in the evaluation is imminant. For chess and checkers this generally >means captures and promotions, and for chess also some checks as well. For games >in general it will depend on what the dominant feature of the evaluation is for >that particular game. For chess and checkers it is material balance, but for >Reversi I am not so sure what it would be. Also the branching factor needs to be >taken into account, since this may limit the amount of extending that is >practical given reasonable time constraints. Michael Buro's ProbCut works really well for Othello. I don't know if anyone's had any success using it in chess though (instead of null-move). [more snippage] >Yes, the high branching factor and non-forced nature of captures mitigates >against extending the qsearch in chess without great caution, but in >compensation the comparative rarity of zugzwang allows the powerful tool of null >move pruning and "standing pat" in the chess qsearch. It is a case of seeing >what is appropriate to a specific game. Each technique for enhancing the search >needs to be weighed up carefully to see if it is appropriate for the game in >question. I think the key questions are: > >1) How common is zugzwang? If it is rare, then null move is called for. Or some other forward pruning mechanism. >2) What is the average branching factor? If high, move ordering is much more >important and extensions are more expensive. "First move" ordering is always important, though. >3) How volatile is the evaluation from one position to its successors? If it is >changing by large amounts from move to move, the qsearch becomes much more >critical. > >Programming a variety of games is a great eye opener. Often ideas can be >transplanted, albeit with some modification, from one game to another. Sometimes >an idea that fails in one game may work splendidly in another game. I think >there are very few really "bad" techniques, only ones inappropriate to a >specific game. Never write off an unsuccessful idea as a complete failure - it >may be a brilliancy in a different setting! [yet more snippage] > Roberto Dave Gomboc
This page took 0 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.