Author: Don Dailey
Date: 21:11:20 06/23/98
Go up one level in this thread
On June 23, 1998 at 21:31:36, Robert Hyatt wrote: >On June 23, 1998 at 16:18:43, Don Dailey wrote: > >>On June 23, 1998 at 13:16:38, Ulrich Tuerke wrote: >> >>>On June 23, 1998 at 12:39:03, Bruce Moreland wrote: >>> >>>> >>>>On June 23, 1998 at 03:58:26, Ulrich Tuerke wrote: >>>> >>>>>I'm afraid this can imply some problems for the search. Assume >>>>>that you have flagged a position as a "draw" in your transposition >>>>>table because the 50 move rule had applied. If this position is later >>>>>reached at a lower depth via a transposition, then the hash table >>>>>would return a "draw". But may be, it really isn't because at lower >>>>>depth the search might be still below the 50 move threshold ? >>>>>This could result in real foolish moves returned from the t-table. >>>>>IMHO, similar remarks hold for the draw by repetition case. >>>>> >>>>>I think that I had once detected problems through storing these >>>>>kinds of positions in the hash table. Now, I don't store them. >>>>> >>>>>Did I get somehing wrong ? >>>> >>>>No, but you didn't get everything right, either. >>>> >>>>Draw scores don't just affect one node, they can propagate up the tree, and they >>>>can cause other nodes to have a different value, without that value necessarily >>>>being the draw score. >>>> >>>>So as long as you have a transposition table that doesn't take into account the >>>>path used to get to a node, there will always be problems. >>>> >>>>And taking into account the path used to get to a node defeats the purpose of a >>>>transposition table. >>>> >>>>So if you don't store 50-move and rep draws at the point you encounter them, >>>>maybe this will make things work better, but you can't say, "whew, it is perfect >>>>now", either. >>> >>>I know that it's not perfect. I have also taken care that a parent node of such >>>special draw node which became the current best cause of the draw evaluation >>>will not be stored either in the hash table. >>>But of course, this is still not perfect. But according to my experience it's >>>better than just to ignore the problem. I am pretty sure that in past I >>>occasionally have had serious trouble in my program resulting from 50 move rule >>>draw scores in the hash table. I am sure that the risk to obtain some >>>catastrophic move is in case of the 50 move rule is really there and may be far >>>larger than in the repetition case. >>> >>>So I changed it and it seems to work better; just a lot of pragmatism required >>>to maintain a chess program: try and see if it's useful, nothing for theorists >>>or perfectionists. >>> >>>Anyway, thanks a lot for the feedback here. >>> >>>> >>>>bruce >> >>My solution to the 50 move draw rule as it relates to hash tables is to >>simply ignore it. The draw position would only be solved by my program >>if it looked deep enough to see that repetition is eventually forced, >>but this probably would never happen since I don't look beyond 50 >>moves of state for this. >> >>I have some doubt as to whether implementing the 50 move rule in the >>search will help in a very noticable way. It's extremely rare that the >>program is in a 50 move situation AND a won position (which it can >>not win) simultaneously. The 50 move rule does not even guarantee >>the win in a won situation, it just makes a win (and a loss) somewhat >>more likely. I have seen it happen that other programs give up material >>to avoid a draw which causes it to lose. >> >>What is the general feeling on this? Does anyone feel it adds more >>than 1 rating point to the program? If it adds more than 1 rating >>point I might consider putting it in Cilkchess if the slowdown is >>less than 1 percent (which would approximately cancel the improvement.) >> >>I have never played a tournament game where any of my programs were >>ever in this situation and lost a half point for not getting desparate >>to avoid the draw although I realize this is always a possibility. >>I have seen it happen in test games, always on super fast levels like >>1 or 2 ply searches. In some of these situations it was just a >>technique problem and pawn moves or captures were not involved, it >>just couldn't win knight and bishop vs king or some other difficult >>ending. >> >>Some programs use progressively higher penalties (score gets closer >>to zero) as the search proceeds without captures or pawn moves or >>castling. I am kind of skeptical of this method too, especially >>with respect to hash tables and the tendency to play premature or >>desparate pawn moves and captures. >> >> >>- Don > > >it is simply a "hole" that needs filling. Otherwise you will walk into a >draw that could be a win... and that would be unfortunate. I didn't implement >the 50-move draw rule until I got burned several dozen times on ICC. It wasn't >in Cray Blitz at all, and I drew a winnable game against NuChess several years >ago because Slate had it and I didn't... Here is how I reasoned about this, and I freely admit I might be wrong here: A very small percentage of games ever get to the 50 move rule without a clear result (win loss or draw.) Of these games, you will have 2 basic cases, one side will be forced to give up material (probably a pawn), or advance a pawn to play for a win. Of course it could be either side. In the case where you give up material, you are taking a big chance because presumably you have a sure draw, and now you are taking a chance of losing in order to play for the win. Chances are this is still a sound strategy since the program will still feel it is better (perhaps it's up 2 pawns for instance), but a certain percentage of these games will now be LOST instead of drawn, presumably a bigger fraction will be wins but my bet is that most of these positions will be draws ANYWAY, but you are now just 1 less pawn. In the pawn push case, I have to ask myself why would the program refuse to push a pawn given 50 moves to attempt this? The answer is that there is probably something wrong with the pawn push, or your evaluation is out of whack. Perhaps the push let's both you and the opponent get a passer for instance, or maybe it just lets the opponent get a passer? So in this scenario we are encouraging the program to make a move it does not want to make. In all of these cases, I'm guessing it's slightly better to have the draw knowledge than not, after all it IS a perfect score and wouldn't we love to have more of these? My main argument is that it is fairly rare to even get to the 50 move rule, and I'm guessing the 50 move knowledge will almost always give the same result, a draw. It's a fraction of a fraction, a pretty small number of saved half points. This makes me wonder how many half points it will save me? I know it will occasionally cost me a game and somewhat more often win me a game. Either case will be fairly rare occurance. The question is how much will a 2 percent slowdown cost me assuming that is how much the implementation costs me? Unless I'm underestimating the benefit of the algorithm, I KNOW a 2 percent slowdown makes the program weaker in EVERY single position. Is it worth saving the half point it loses every 100 games if it is losing a couple games every 100 games because it is weaker in all positions? It's really a knowledge/speed tradeoff issue. I think a lot of people miss this point in general. Most fixes to a program are very visible, you will see a problem definitely fixed and this is gratifying. But any problems this change causes are completely unobservable. Numerous times in tournaments I would see my program about to make a losing move, only to change it's mind at the VERY LAST second. This happens often enough to completely amaze me, it's no mystery at all why a small speedup to a program makes it noticeably stronger. But the next time this happens will I wonder if that 50 move rule slowdown made me lose this game? Not a soul alive would identify the 50 move rule implemenation as being responsible for losing a middlegame position! Some pieces of knowledge I accept on faith. An example of this is the minor piece vs king rule, always a draw. I would not dream of leaving this out of the program, and yet years ago when I implemented it I tested the hell out of it and found no measurable improvement to the program. It kicked in once in a great while, but even those very few times, it did not change the results, the game was a draw anyway! I guarantee you that if I left it out I would be kicking myself sooner or later when it bit me. In the program involved, I took a 1 or 2 percent hit for having this rule but the implemenation make other rules possible. The tiny slowdown offset the tiny improvement it made to the program and of course I kept the rule. Probably I should view the 50 move stuff the same way. You say it saves games for you all the time. For my current program I doubt it will slow me down at all as I already have a counter in the position state that tells me the distance to the last irreversable move. I can implement this thing in 60 seconds. So my 2 percent thing was an exaggeration. Maybe I'm also exaggerating about 1 game saved every 100? I have a feeling this will help the fast games a lot more than the long time control games. I will take a look at one of my autotest result files and look for cases of where this might have saved the day. - Don
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.