Author: Greg Lazarou
Date: 23:22:29 02/06/99
Go up one level in this thread
On February 07, 1999 at 01:44:04, KarinsDad wrote: >On February 05, 1999 at 22:01:52, Greg Lazarou wrote: > >>On February 05, 1999 at 21:11:23, James Robertson wrote: >> >>>My program is losing too many half-points by 3rd repetition draws. How do other >>>programs detect these draws? >>> >>>Thanks! >>>James >> >>Well, I have a very basic little chess program (started by reading TSCP a month >>or so ago) and I recently implemented the 3rd repetition draw logic in a way >>that did not seem to compromise performance too much (I could not detect any >>slowdown in nodes per second): >> >>1) I have the typical MakeMove/TakeBack functions used in the searches >>2) I also implemented ApplyMove/UndoMove functions that are used not by the >>search functions but only when the move is actually made (either by opponent or >>the engine). These are not executed as often so we can do more stuff here: >>2a) In ApplyMove I save the board position in a board history stack/array. >>2b) I search backwards to see if the current board is a duplicate of nay other >>board in history (BTW you don't need to look back past boards created by >>captures, promotions or pawn moves) >>2c) If it is a duplicate I store it in a dups stack. >>2d) If the current board was caused by a capture/pawn advance/promotion I clean >>the dups stack. >>3) During the AB search I search through the dups stack for the current board >>and if found we have a draw by repetition ==> return 0. >> >>This way during the more frequent operation we only have to look through a few >>boards (the dups stack) looking for the 3rd repetition. That means that we may >>not evaluate correctly in general when the repetitions happen within a given >>search (we should give a value of zero to some board position far into the >>search but we will not) but I thought that it is a lesser evil to do that than >>to slow down everything to do it perfectly... At least if we are ahead we'll >>avoid the 3rd repetition (if we have better things to do) and if we are behind >>and we see an opportunity for a draw we'll jump on it... >> >>tell me if you find a better way to do this... >> >>Greg > >This seems reasonable. I was going to put something similar into my program (if >I ever get there). > >One other thought. > >Once you have a PV established or possibly once you've used up 1/3 or 1/2 of >your alloted time for a move, you could check through your PV and some side >lines for repetition. If you find instances of it (especially ones forced by >your opponent), you can set a flag indicating that you should search for it. > >If your best move in each position for your PV and for all best moves to 3 ply >does not lead to a repetition, then do not set the flag and do not worry about >it (a flag may not be needed, it just depends on how your code is written). > >For example, at ply 1, your best move is x. At ply 2, your opponent has approx. >40 moves to make in reponses to x. Check them all for rep with your dup table. >For ply 3, you have 40 best moves (one for each of the ply 2 responses by your >opponent). For each of these, your opponent has 40 replies. Check each of these >or 1600 checks. Note: you do not have to compare ply 4 with ply 2 since they >will not be the same. > >You can now search for rep along the PV path to whatever depth it went and only >check the immediate responses. Remember to search for reps both along the >current path and with the dup table. Not just with the dup table. > >What this does is ensure that you will not have draw by rep to at least 4 ply >down and not within your main PV. > >If you detect it, you will have to avoid it (get a new PV, at least somewhere >along the path). If you do not detect it, you are fine. > >This just adds a safety net to what you are already doing. But you are only >checking for rep in 40 +1600 +12*40 or 2120 positions (for 14 ply down). Hardly >any checking at all compared with 50,000 nps * even 5 seconds in blitz. > >You can also redo this check, just before you decide to move. But you can even >get tricky here and only check below where you checked before in the current PV >(i.e. if the current PV is the same to ply 6 and different below that since the >last check, you do not have to check until ply 8). > >KarinsDad Oof! I'm getting a headache thinking about this... I'm not sure I need it right now. As it stands it will see the 3rd move (either for its side or for the opponent) that causes the draw and can either avoid it by messing with the board or lean towards it depending on the relative value of score=0 vs. its other best scores. It will not lean towards or avoid the moves that create the dup though. But this is not too detrimental as I'm thinking about it - or am I missing something? BTW do you have your engine working to a point that I can try it in Winboard against mine? My engine currently looses to almost all other engines that I try it against :-)But it usually beats me (if I don't take moves back). If you'd like to try mine check at http://home.att.net/~glazarou/ Greg
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.