Author: Roberto Waldteufel
Date: 09:11:14 04/09/99
Go up one level in this thread
On April 09, 1999 at 01:42:11, Dave Gomboc wrote: >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. :-) > Well, I guess it depends on your definition of a capture. In chess and checkers every capture reduces material, and so a series of captures normally causes the branching factor to reduce, a point made by Slate and Atkin in their famous paper on Chess 4.x, so a qsearch based on captures is more feasible than would otherwise be the case. In Reversi/Othello the "captures" are fundamentally different in that material *increases*, so I would not call these captures, at least not in the sense that the word is used for chess and checkers. Since the pieces played in the early phases change sides many times during a game, the instantaneous state of a particular square may not be very relavent for evaluation purposes unless it becomes stable (unflippable), eg a corner square. This is why I am unsure as to what would constitute the dominant factor(s) in the evaluation function, and hence what would be the appropriate formulation of a qsearch for that game. >>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). > I'm not sure what ProbCut is - could you elaborate? >[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. Yes, indeed. Null move seems to be the most successful method I have seen to date, but maybe something else could do as well or even better. It seems to me that the prevalence of zugzwang is the key question for null move pruning: any game where zugzwang is absent, or at least very rare, would seem to be a fertile ground for null move. Unfortunately this is not the case in checkers :-( > >>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. > Yes, this is certainly true, but the amount of improvement to be gained by getting the best move first rather than last (or near last) will be greater for games with high branching factors (like chess), and this is important because it affects the amount of overhead that can profitably be incurred in order to improve the chances of hitting the best move first. An expensive move ordering trick might pay for itself in chess, but be prohibitively expensive in checkers due to the lower branching factor, ie same cost for smaller reward. Roberto >>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.