Author: Roberto Waldteufel
Date: 21:00:55 04/08/99
Go up one level in this thread
On April 08, 1999 at 22:56:04, Christophe Theron wrote: >On April 08, 1999 at 17:27:33, Roberto Waldteufel wrote: > >>On April 08, 1999 at 16:37:52, Christophe Theron wrote: >> >>>On April 08, 1999 at 13:44:11, Roberto Waldteufel wrote: >>> >>>>By a threat for the other side, I mean that, if it were in fact the other side's >>>>turn to play, he would have a capture. Therefore threats by side to move would >>>>mean that the side to move has one or more legal captures available, which is >>>>precisely the condition I started out with to trigger an extension. The >>>>enhancement was to extend if *either side* has pending captures. >>> >>>OK, I thought at first it was asymetric. >>> >>> >>>>The whole >>>>qseearch is easier than in chess precisely because of the obligation to capture >>>>whenever possible - it is not really a qsearch in the sense we use that term for >>>>chess >>> >>>It is the same than in chess from my point of view. QSearch is: "don't stop >>>while something is happening". The difference is how you judge that something is >>>happening... Even in chess you can think of different ways to implement a >>>QSearch, isn't it? >>> >> >>Yes, exactly so. It is only how I define "something is happening" that is a >>little bit different because of the different rules of checkers (as compared to >>chess) when captures are possible. > >It's interesting to find general concepts that can be applied to different >games, or a concept general enough to be implemented in several ways for a >single game. Then you can play and experiment with it. > >I'm wondering if the concept of QSearch (as defined above) applies to >Othello/Reversi too? > >Are you doing extensions in checkers as we do in chess? Do they use extensions >in Reversi? 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. 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. > > >>I think if I tried to implement the exact >>same method in chess, my Qsearch would explode and the search would never >>terminate. > >That's indeed the problem. > 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. 2) What is the average branching factor? If high, move ordering is much more important and extensions are more expensive. 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! > > Christophe > > >>>>- rather it is an extension of the full width search. The only cases that >>>>escape this technique are so called "pitch" moves, where neither side has a >>>>capture, but the side to move deliberately offers a sacrifice of a piece (which >>>>must be accepted because of the obligation to capture whenever possible) in such >>>>a position that the material scrificed can either be regained with interest or >>>>an overwhelming positional superiority can be established by means of the >>>>sacrifice. >>>> >>>>If you ever turn your hand to another game, I can highly recommend checkers. It >>>>has far more depth and subtlety than I ever thought possible with such a limited >>>>set of moves compared to chess. The late Dr Marion Tinsley, thought by many to >>>>be the best (human) player of all time, was also quite a strong chess player in >>>>his youth. He compared the two games nicely thus: "Chess is like looking out >>>>over a limitless ocean, whereas checkers is like looking down a bottomless >>>>well". >>> >>>I understand... >>> >>> >>> Christophe >>> >>> >>>>I understand from that quote that in checkers, because of the lower >>>>branching factor, you can look further ahead, but still sooner or later you must >>>>reach a horizon where a (possibly erroneous) positional evaluation must be made, >>>>just as happens in chess and other games. In my experience it is often more >>>>difficult to describe accurately what constitutes a positional advantage in >>>>checkers than it is in chess, although that might be because I am not very >>>>experienced at checkers, whereas I have played, studied and programmed >>>>competitive chess for many years. >>>> >>>>Best wishes, >>>>Roberto
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.