Author: Dann Corbit
Date: 17:44:02 08/23/01
Go up one level in this thread
On August 23, 2001 at 18:47:02, Slater Wold wrote:
>On August 23, 2001 at 16:42:56, Dann Corbit wrote:
>
>>On August 23, 2001 at 16:36:21, Slater Wold wrote:
>>[snip]
>>>Ed & Chris might have a stronger engine, but they offer me _NO_ knowledge. How
>>>many times have you seen Frans, or Shay, or Ed, or Chris, respond to a thread
>>>titled, "How to improve time management?" They won't! They won't even share
>>>their ideas on TIME MANAGEMENT!
>>
>>Ed and Chris have shared a good deal on how to do computer chess programming. I
>>don't know if they have ever said anything about time management, but I suspect
>>that they might.
>
>I've been here a year, and I myself have never seen it. Perhaps I wasn't paying
>enough attention. My apologies (I doubt either of them care) to both if they
>have. I've just never seen it.
I've been here a very long time (since the first year they opened).
Samples:
CHRISTOPHE-->
===========================================================================
Subject: Re: SEE checking
From: Christophe Theron
E-mail: ctheron@outremer.com
Message Number: 142237
Date: December 01, 2000 at 16:23:27
In Reply to: Re: SEE checking
Message ID: 142164
Posted by: Tony Werten
At: a.werten@cs.unimaas.nl
On: December 01, 2000 at 03:31:19
On December 01, 2000 at 03:31:19, Tony Werten wrote:
>On December 01, 2000 at 02:49:54, Christophe Theron wrote:
>
>>On November 30, 2000 at 02:33:06, Scott Gasch wrote:
>>
>>
>>
>>What you are doing is the right thing to do.
>>
>>I have the same overly paranoid debug code spread all over Chess Tiger's
>>sources. After so many years of chess programming, it turns out that it is not
>>paranoid at all. It is just enough to catch very nasty bugs.
>>
>>So from time to time, without any special immediate need, I add paranoid
>>checking code. I have #if (DEBUG_xxx) conditionals all over the sources
>>(DEBUG_xxx allowing to turn on checking code for a specific thing).
>>
>>A very efficient way to find bugs is to have several versions of the same
>>routine. For example, generate moves in several different ways, collect the
>>resulting moves lists, and compare them. That's what I do in "debug genmove"
>>mode. I have also a code that compares the incrementally computed hash codes to
>>hash codes computed from scratch in every position. An obvious thing to check, I
>>would say.
>>
>>From time to time I launch a big test. The program has to compute a given number
>>of fixed positions to a given ply depth with all the debug code turned on. It
>>runs 20 times slower than the normal version, but I feel more comfortable once I
>>have run this test and no error has been found. The goal is not to check if the
>>program finds the right moves for the positions, but just to check that the
>>debug code does not catch a problem.
>
>For some sort of stupid reason, by bugs are ( by far ) in de checking code. This
>means I spend a lot of time trying to fix my original code to find out I was
>just comparing the wrong stuff.
>
>Tony
It's an investment. You have first to find bugs in your debug code (which sounds
crazy). But once it works, this debug code can stay there, and will be available
at any time later. And it WILL catch bugs. Because in the normal course of
developpement you will have to change the other parts of the code (the non-debug
parts) and it's likely that bugs will slip into them anyway.
Spend one day on debug code now, it will save you 10 days later this year.
I think that well thought debug code can slash the developpement time by two in
many cases. In a chess program it is particularly critical.
Christophe
Subject: Re: MVV/LVA or SEE - liability?
From: Christophe Theron
E-mail: ctheron@outremer.com
Message Number: 142160
Date: December 01, 2000 at 02:59:35
In Reply to: Re: MVV/LVA or SEE - liability?
Message ID: 142117
Posted by: Bruce Moreland
At: brucemo@seanet.com
On: November 30, 2000 at 20:20:15
On November 30, 2000 at 20:20:15, Bruce Moreland wrote:
>On November 30, 2000 at 14:25:32, Severi Salminen wrote:
>
>>
>>>>Well, I'm not performing any illegal captures (which leaves king in check) - so
>>>>if a piece or a pawn is pinned to (?) king it can't maybe capture and SEE
>>>>doesn't see that. I ment no other pins. But maybe king pinning situations are
>>>>_very_ rare that one doesn't have to consider them.
>>>>
>>>>Severi
>>>
>>>If you have code that lets you try it both ways, there is one way to find out.
>>>My intuition is that even if it's not particularly rare, it isn't critical to
>>>avoid a few mistakes at the tips.
>>
>>I don't have either MVV/LVA nor SEE. I just wanted to know if there are _any_
>>reasons to pick MVV/LVA instead of SEE (other than simplycity). But apparently I
>>must go for SEE, sounds like a few days of programming :(
>>
>>Severi
>
>MVV/LVA is a very quick and very dirty SEE. SEE gives you a better resolution
>of the swapping sequence. I think it would be insane to use MVV/LVA to prune
>out losing captures, because you don't detect them. You can get away with using
>a SEE to do it.
>
>I can't think of any reason not to use SEE at least to get better move ordering,
>other than that a SEE is computationally expensive. This means that whether
>it's better or not is implementation dependent.
>
>I think that most implementations would get a higher node rate with MVV/LVA, but
>they'd search more deeply with a SEE, at least if losing captures are pruned
>out.
>
>bruce
It is actually rather easy to write a SEE. Think of it as an alphabeta search
algorithm. The difference is that the move generator is degenerated: it
generates only one capture at any level (the capture by the smallest piece that
has not been already used to capture on the target square).
I have an SEE which is programmed like a recursive alphabeta search, with a
couple of optimizations. It is easy to write a simple one. Then it takes a
little more time to improve it to handle aligned pieces (a bishop attacking thru
a friendly queen for example), but with the framework of the alphabeta search
it's no big deal.
Christophe
Subject: Re: Moves per position.
From: Christophe Theron
E-mail: ctheron@outremer.com
Message Number: 34161
Date: November 27, 1998 at 16:31:13
In Reply to: Re: Moves per position.
Message ID: 34153
Posted by: Frank Phillips
At: frank@frankp.force9.co.uk
On: November 27, 1998 at 13:55:44
On November 27, 1998 at 13:55:44, Frank Phillips wrote:
>On November 25, 1998 at 14:42:52, Christophe Theron wrote:
>
>>On November 25, 1998 at 13:23:42, Frank Phillips wrote:
>>
>>>I am disappointed with the number of moves my program analyses per position in
>>>the main search. With basic shuffling to the head of the move list of the pv
>>>move, hash table refutation move and capture of valuable pieces by less valuable
>>>pieces, the search is making around 9 moves in each middle game position and
>>>about five in the endgame. A few more with the sorting turned off. What is
>>>normal?
>>
>>What do you call PV move?
>>
>>The move given by the hash table should be tried first IMO. You should also use
>>killer moves.
>>
>>
>> Christophe
>Thank you for the advice. Had not tried killer moves before. My initial
>impression from some very quick, very unscientific tests indicate that they have
>not helped. The nodes needed to reach the same depth went up by at least 20%
>and sometimes 80%. The refutation hash table and considering captures first
>seemed more important. Perhaps with refutation hash and history heuristic
>table, killer moves are less important?
They are less important but still absolutely necessary.
There is something wrong in your implementation I suppose. You should find
killers to be VERY useful.
>Could be wrong since the testing was weak; and I may have not implemented the
>killer moves properly. I simply stored two killers for each ply (killer1[ply]
>and killer[ply]), storing killer1 in killer2 and the new move in killer1 if it
>caused a beta cutoff. If the killers were in the move list at the current ply,
>these were searched first – and they were on many occasions.
Your description sounds correct to me. But check this:
Try them after the hash table move. The HT move should always the first move you
try.
If you search captures before the other moves, try without storing captures in
the killer tables.
Try killers before or after the captures. Compare the 2 versions.
Try with and without killers in the QSearch. Depending on your program it may
impact in the wrong direction.
>Still interested in the number of moves per position it is normal to have to
>search. As I said previously mine is searching on average around 9 moves in
>each middle game position, which seems a lot
At what time control, on which computer and with how many HT?
In assembly or with interpreted Basic?
And on which planet? :)
Christophe
Subject: Re: Why bitboards at all?
From: Christophe Theron
E-mail: ctheron@outremer.com
Message Number: 115536
Date: June 21, 2000 at 14:38:23
In Reply to: Re: Why bitboards at all?
Message ID: 115525
Posted by: Tom Kerrigan
At: Thomas.Kerrigan@colorado.edu
On: June 21, 2000 at 13:33:14
On June 21, 2000 at 13:33:14, Tom Kerrigan wrote:
>On June 20, 2000 at 21:39:01, Robert Hyatt wrote:
>
>>On June 20, 2000 at 15:52:53, Tom Kerrigan wrote:
>>
>>>On June 20, 2000 at 15:03:48, Robert Hyatt wrote:
>>>
>>>>On June 20, 2000 at 14:07:39, Tom Kerrigan wrote:
>>>>
>>>>>On June 19, 2000 at 21:32:56, Robert Hyatt wrote:
>>>>>
>>>>>>On June 19, 2000 at 20:50:11, John Coffey wrote:
>>>>>>
>>>>>>>On June 19, 2000 at 19:48:36, Larry Griffiths wrote:
>>>>>>>
>>>>>>>>I have found bitboards to be an even trade-off on my Pentium system. I have to
>>>>>>>>update about 6 bitboards when a piece moves and this generates a lot of
>>>>>>>>instructions. I get it back in my IsKingInCheck code so it evens out. I like
>>>>>>>>to have fast move generation code, but most of my gains have been through
>>>>>>>>alpha-beta, hash-table, killer-move and movelist ordering etc.
>>>>>>>>
>>>>>>>>Larry.
>>>>>>>
>>>>>>>
>>>>>>>Maybe I am too much of a novice, but I don't see yet why I should convert over
>>>>>>>to bitboards. Is move generation faster? If so, why? My program scans the
>>>>>>>board and uses simple loops to generate moves. Do you not have to do loops
>>>>>>>with bitboards?
>>>>>>
>>>>>>Not to generate moves, No. You generate all the sliding piece moves with two
>>>>>>table lookups...
>>>>>
>>>>>Hmmm. I do table lookups all over my program, and none of them seem to be
>>>>>generating any moves...
>>>>>The fact is that you DO need to loop to generate moves in a bitboard program.
>>>>>Maybe it's not the same loop, but it's still a loop.
>>>>>
>>>>>-Tom
>>>>
>>>>
>>>>Who says so? Ask the Dark Thought guys.
>>>>Or Slate/Atkin. You only need to loop if you want to take the attack bitmap
>>>>and turn it into a list of moves. This is not the way _all_ programs operate
>>>>(chess 4.x, Dark Thought, others, any of which generate a few moves at a time,
>>>>then take one and search it, without enumerating the other moves.)
>>>>
>>>>So loops are something you do (with bitmaps) if you want to, not because you
>>>>have to.
>>>>
>>>>As far as your table lookups not generating any moves, that is a programming
>>>>issue. Mine do. :)
>>>
>>>Maybe your makemove() function can take bitboards as input (i.e., here is a set
>>>of squares that my pieces can move to) but mine sure can't.
>>>-Tom
>>
>>
>>You are missing the point. A move generator _can_ emit a single move, which
>>can be fed into MakeMove(). Read "Chess Skill in Man and Machine", the chess
>>4.x section. They explain this pretty well. It takes zero loops to emit a
>>single chess move. You pick the source square. You do two table lookups for
>>bishops (say) and you have all the target squares it can move to. A single
>>FirstOne() and you have a <to> square, which is all you need to make the move,
>>and recursively call Search().
>
>So you end up having to call gen() a mess of times. I don't see how that isn't a
>loop.
>-Tom
As I understand he says that in order to generate one move he doesn't have to
loop. That's what James explains in another post.
With 0x88 or 16x you have to loop thru empty squares, he says with bitboards you
don't have to. For each rank, file or diagonal in any configuration (by
configuration I mean set of empty squares in this rank/file/diagonal), you can
have precomputed arrays that instantly give you the set of squares (a bitboard)
a sliding piece can move to.
Not that I support his point of view about bitboards. I prefer to "loop thru
empty squares" in my L1 cache rather than clobbering the same cache with
bitboards. And anyway, the time required to extract the rank/file/diagonal from
the "occupied" bitboard and the time required to process the resulting set of
"can move to" squares is not required in 0x88 or 16x. And for non-sliding pieces
(which represent in average half of the pieces present on the board), the method
does not apply.
Christophe
Subject: Re: Dabbabas clock has a ghost at midnight!
From: Christophe Theron
E-mail: ctheron@outremer.com
Message Number: 19642
Date: May 31, 1998 at 19:32:48
In Reply to: Dabbabas clock has a ghost at midnight!
Message ID: 19599
Posted by: Jens Baek Nielsen
At: jensbaek@silkeborg.bib.dk
On: May 31, 1998 at 12:13:28
On May 31, 1998 at 12:13:28, Jens Baek Nielsen wrote:
>
>My chessprogram Dabbaba uses this code to get the time:
>
>double get_the_time()
>// returns the number of 1/100 seconds since the program started
>{return (double)(100*(clock())/CLK_TCK);}
>
>It works fine except at midnight, where strange numbers suddenly appears
>- suddenly white has used more than 8 million seconds etc.!
>
>Is it only me who has encountered this problem?
>Is there a better way to measure the time?
>
>I consider to estimate the time from the number of nodes searched at
>this midnightevent, but it is rather silly code to have in your program.
>
>I use a Borland Turbo C++ 3.0 compiler.
>
>Greetings Jens
The problem comes from a problem with the PC BIOS and the way DOS
handles the clock.
I have the same problem with Tiger compiled with BC3.1 or GnuC.
To fix the problem, you have to do the following:
Your function get_the_time should store the latest value returned by
clock(). When, suddenly, clock() returns a value which is less than the
last value (midnight!), you should store this value and use it as an
offset in any subsequent call to get_the_time.
I have to say that a tester told me recently that he had the midnight
bug one time with Tiger (even with the above mentionned fix). We were
unable to reproduce it, but it happened...
So now I'm considering using the code given by Don in the other reply to
your message...
Christophe
ED-->
===========================================================================
Subject: Re: Q. about Rebel extensions
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 52186
Date: May 19, 1999 at 02:32:31
In Reply to: Q. about Rebel extensions
Message ID: 52090
Posted by: Rémi Coulom
At: Remi.Coulom@imag.fr
On: May 18, 1999 at 03:56:14
>Posted by Rémi Coulom on May 18, 1999 at 03:56:14:
>>Extensions (checks) : 77.979 (13%)
>>Extensions (captures) : 5.807 (1%)
>>Extensions (king safety) : 1.180 (0%)
>>Extensions (on depth) : 7.594 (1%)
>>Extensions (remaining) : 1.094 (0%)
>>Extensions (total) : 93.654 (16%)
>>
>
>Could you explain what "king safety", "on depth" and "remaining" extensions
>consist in ?
Extensions (King Safety): when one of the kings is in danger an extra
ply is taken.
Extensions (on depth): on depth means the ply before Q-Search. Various
extensions (extra plies) are tried to avoid a horizon effect. To name a few:
#1 if the last move attacks 2 pieces.
#2 if the king is in check.
#3 if the last move is capture that gains material (static evaluation).
#4 cases like bba2 wrb3 wrf7
#5 piece attacks like h2-h3 attacking the black knight on g4.
#6 moves that escape from (#5) such as Nf6, Nh6, Ne5
#7 certain types of mate threats recognized by the evaluation function.
All of this is safe-guarded with several forward prune techniques to
avoid the tree to explode. Next, extensions on depth is limited to take
2 or 3 of such extra plies also to avoid the tree to explode.
Extensions (remaining): A number of the list of "Extensions on depth"
is also tried in the tree. Here I use fractional increments of 1/4 ply. One
idea is to push the hash table entries of best lines. In other words, if
the current move is from the hash table and the move of the previous
ply too then the depth is increased with 1/4 ply. Also some promotion
extensions are tried which increment may vary on their importance.
Ed Schroder
Subject: Re: How to order moves
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 104011
Date: March 31, 2000 at 00:52:55
In Reply to: Re: How to order moves
Message ID: 104009
Posted by: James Robertson
At: jrobertson@newmail.net
On: March 31, 2000 at 00:25:23
On March 31, 2000 at 00:25:23, James Robertson wrote:
>On March 30, 2000 at 18:32:40, Robert Hyatt wrote:
>
>>On March 30, 2000 at 15:04:09, Inmann Werner wrote:
>>
>>>On March 30, 2000 at 11:07:16, Robert Hyatt wrote:
>>>
>>>
>>>>Here is mine:
>>>>
>>>>1. hash table move.
>>>>2. captures that don't appear to lose material using a SEE procdedure,
>>>>ordered from biggest gain to equal exchanges.
>>>>3. 2 killer moves.
>>>>4. up to 4 history ordered moves (history heuristic)
>>>>5. rest of the moves.
>>>
>>>question to 5)
>>>here is the rest of the non capturing moves and the "loosing capture" moves.
>>>Which of them should be searched first?
>>>
>>>IMHO the non capturing moves.
>>>
>>>Werner
>>
>>
>>In my case, losing captures come first, but only because that is the way they
>>appear in the list. IE I generate captures, sift the good ones to the top, and
>>leave the lemons at the bottom. Later I generate the rest of the moves and add
>>to the list, which places them after the lemons...
>
>Have you tested to see if the move ordering could be improved? In my case I
>search:
>Hash move
>Winning captures
Third in Rebel is Queen promotions.
>Equal captures
Remaining promotions.
Ed
>2 Killer Moves
>Noncaptures ordered by the history table
>All captures (even the ones we already searched) ordered by the history table
>
>James
Subject: How to create a set of random integers for hashing?
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 29817
Date: October 18, 1998 at 05:46:50
Since ages I use the following formula for creating a set of random
integers for hashing at program start:
#define LENGTH 64*12
int random [LENGTH];
int a,b,c,d,x;
srand(9); // initialize prime number
for (x=0; x<LENGTGH; x++)
{ a=rand(); b=rand(); if (b & 1) a=a | 0x8000;
c=rand(); d=rand(); if (d & 1) c=c | 0x8000;
random[x]=(a<<16)+c;
}
I wonder how good such a system is and how others do it.
- Ed -
Subject: Re: Tell me about computers learning....
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 30627
Date: October 26, 1998 at 13:43:18
In Reply to: Tell me about computers learning....
Message ID: 30608
Posted by: mike cooter
At: mcooter@sprintmail.com
On: October 26, 1998 at 10:37:52
>Can someone explain to me the different learning functions among the top
>contenders? book learning? How do each work and which method is most effective?
>-Rebel 10(esp interested in this)
>-MChess
>-Fritz/Junior
>-Crafty
>-Genius
>Thanks in advance
The main principle in Rebel is "weights". When losing a game then lower
the weight. When a game is won increase the weight. All Rebel book moves
have a "weight" value which serves 2 purposes:
1) the weight value is used to play book moves random.
2) the weight value is a strong indication to favor a move or not.
The effect is that Rebel will avoid lost book lines and repeat the book
lines it has won.
- Ed -
Subject: Re: Hash Table: Different moves with different table sizes??
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 100040
Date: March 03, 2000 at 11:47:42
In Reply to: Hash Table: Different moves with different table sizes??
Message ID: 100035
Posted by: Brian Richardson
At: brian.richardson@metagroup.com
On: March 03, 2000 at 11:35:22
On March 03, 2000 at 11:35:22, Brian Richardson wrote:
>Looking for suggestions with a hash table "problem". Running
>
>8/8/7k/8/4p1K1/8/5P2/8 b - - bm e3; id "Fine position 16";
>
>Tinker likes e3 with some hash table sizes (usually at around ply 16), but Kg6
>at other sizes. Even stranger is that e3 is picked at some smaller hash sizes,
>and with very large sizes, but not for "medium" size hash tables.
>
>Of course, I may just have a _nasty_ bug in my hash table code.
>
>Or, it may be something subtle. It _may_ have something to do with move
>ordering--if there are two branches that happen to have the same score at the
>same depth, in one case one position is hashed and it never "sees" the other
>one?
>
>Have others run into this?
>
>Any suggestions welcomed.
>Thanks.
Never trust your hash table code, that is right. On the other hand don't
bother too much about it as the behaviour you describe is quite natural.
You are dealing with pruning based on scores, extensions which can cause
different depths. My rule is to count the plies a move must been seen by
search and then add 1 ply as a limit search should see the move to be
found.
Good luck with the problem.
Ed
Subject: Re: Hash collisions and a little maths
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 44421
Date: February 24, 1999 at 13:06:33
In Reply to: Re: Hash collisions and a little maths
Message ID: 44413
Posted by: Vincent Diepeveen
At: diep@xs4all.nl
On: February 24, 1999 at 11:53:39
>Posted by Vincent Diepeveen on February 24, 1999 at 11:53:39:
>>>I know however that i must have had wrong collisions, probably the fact
>>>that i don't store true values hides collision probs from me, as i
>>>cannot have true values in my program; if a score is true then alfa
>>>gets improved and then score is again <= alfa, so i use only 1 bit
>>>to see whether it's >= beta or <= alfa.
>>
>>I don't understand the above. You say, "i cannot have true values in
>>my program" and then "if a score is true then..." which I interpret as
>>you use true score after all?
>>
>>My best guess is you only use alpha (and not beta) to mark the
>>score in the hash table. Correct view?
>>
>>Can you tell why Diep can't use "true scores" in the hash table?
>
>This is something theoretical Ed,
>ASSUME we have true scores in search.
>Now try to prove that to false.
>
>We assume that we have true scores.
>then alfa becomes the true score,
>however score <= alfa, so
>conclusion is falsum.
>
>so the score is <= alfa, which is a bound.
>therefore i only store using 1 bit in hashtable.
>a score is either <= alfa or >= beta, but never alfa < score < beta,
>that cannot happen in DIEP as i improve alfa with the result of the search.
Here is how I do things. As far as I know it should work for every program.
Store_in_Hash:
flag=REAL;
if (score >= beta) flag = UPPER;
if (score <= alpha) flag = LOWER;
Store flag in hash table
Search_in_Hash:
if (flag==REAL) return 1; // transposition
if (flag==LOWER && score <= alpha) return 1;
if (flag==UPPER && score >= beta) return 1;
return 0; // no transposition
Ed
Subject: Re: Forced moves
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 62947
Date: July 31, 1999 at 03:08:42
In Reply to: Re: Forced moves
Message ID: 62937
Posted by: Robert Hyatt
At: hyatt@crafty.cis.uab.edu
On: July 30, 1999 at 23:54:28
>This is easy to test.
>
>My hypothesis: simple search is not good enough to discover that all moves
>but one lead to mate, in any positions except for those near the point where a
>game is already over (one side is mating the other).
>
>Ed's: A simple search is good enough to discern forcing moves.
>
>How about someone looking for positions where all moves but one lead to a
>forced mate... IE one move must _not_ get mated, while all the rest do.
>Then we decide whether the short search of Rebel can see this or not.
>
>Then we decide how often this kind of position occurs, and how often (when it
>does) is a shallow search enough to recognize the forced nature.
>
>I don't think (a) it will work very well; (b) that it is worth the effort to
>search with alpha=-inf, beta=+inf for every root move; (c) that by the time
>this might have a chance of identifying a forcing move, the game is already
>over and saving time is pointless...
>
>My opinion, of course...
How about going one step further. Some years ago I did an experiment.
Search the first iteration without A/B, then:
if (best_score - second_best_score > margin_one) limit time control.
if (best_score - second_best_score > margin_two) limit time control even more.
etc.
Also I tried this for the second iteration as well. Results were not bad at all
as it also catches forced moves that aren't recaptures and escapes from
checks. Moves sequences like 1..g5 2.Bg3 were also discovered and
2.Bg3 was played very fast. I also remember a case 1.a7 Ra8 preventing
the pawn to promote. Since 1..Ra8 was the only move 1..Ra8 was played
instantly.
Note that Q-search in Rebel's first and second iteration were limited to 6 and
8 plies to prevent the search to explode when A/B is not active. I also do
check extensions in Q-search to discover mates which catches the most
important ones but not all of course.
Ed Schroder
Subject: Re: Interesting mate test for hashing
From: Ed Schröder
E-mail: rebchess@xs4all.nl
Message Number: 68190
Date: September 11, 1999 at 01:43:12
In Reply to: Re: Interesting mate test for hashing
Message ID: 68177
Posted by: Robert Hyatt
At: hyatt@crafty.cis.uab.edu
On: September 11, 1999 at 00:44:19
On September 11, 1999 at 00:44:19, Robert Hyatt wrote:
>On September 10, 1999 at 22:50:17, Dave Gomboc wrote:
>
>>On September 10, 1999 at 17:40:45, Robert Hyatt wrote:
>>
>>>On September 10, 1999 at 17:01:58, jonathon smith wrote:
>>>
>>>>On September 10, 1999 at 16:45:59, Robert Hyatt wrote:
>>>>
>>>>>On September 10, 1999 at 16:21:48, Alessandro Damiani wrote:
>>>>>
>>>>>>On September 10, 1999 at 15:58:45, Ed Schröder wrote:
>>>>>>
>>>>>>>On September 10, 1999 at 13:17:57, Robert Hyatt wrote:
>>>>>>>
>>>>>>>>On September 10, 1999 at 11:29:04, Alessandro Damiani wrote:
>>>>>>>>
>>>>>>>>>On September 10, 1999 at 09:36:51, Robert Hyatt wrote:
>>>>>>>>>
>>>>>>>>>>On September 10, 1999 at 08:01:35, Alessandro Damiani wrote:
>>>>>>>>>>
>>>>>>>>>>>On September 10, 1999 at 07:48:44, Ed Schröder wrote:
>>>>>>>>>>>
>>>>>>>>>>>>On September 10, 1999 at 00:19:37, Robert Hyatt wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>>Here is an interesting position given to me by Steffen Jakob:
>>>>>>>>>>>>>
>>>>>>>>>>>>> /p/P5p/7p/7P/4kpK/// w
>>>>>>>>>>>>>
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 8 | | | | | | | | |
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 7 | *P| | | | | | | |
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 6 | P | | | | | | *P| |
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 5 | | | | | | | | *P|
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 4 | | | | | | | | P |
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 3 | | | | | *K| *P| K | |
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 2 | | | | | | | | |
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> 1 | | | | | | | | |
>>>>>>>>>>>>> +---+---+---+---+---+---+---+---+
>>>>>>>>>>>>> a b c d e f g h
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>Obviously black is getting crushed. He has one move, Kh3, which leads to a
>>>>>>>>>>>>>mate in 6. Steffen asked me to try this and Crafty found a mate in 4, which
>>>>>>>>>>>>>doesn't exist. I spent the entire day debugging this thing and here is what
>>>>>>>>>>>>>I found:
>>>>>>>>>>>>>
>>>>>>>>>>>>>If you recall the discussion here a couple of weeks ago, I reported that I store
>>>>>>>>>>>>>absolute mate scores (EXACT scores) in the hash table, and that I adjust them
>>>>>>>>>>>>>so that they are always stored as "mate in N from the current position". This
>>>>>>>>>>>>>has always worked flawlessly for me, and still does.
>>>>>>>>>>>>>
>>>>>>>>>>>>>For bounds, I once tried adjusting the bounds as well, but found quirks, and
>>>>>>>>>>>>>left them alone. Wrong answer. To fix this mate in 4 problem, I decided to
>>>>>>>>>>>>>adjust the bounds as well, but I now set any bound value that is larger than
>>>>>>>>>>>>>MATE-300, by reducing it to exactly MATE-300, but still using the "LOWER"
>>>>>>>>>>>>>flag to say that this is the lowest value this position could have. For bound
>>>>>>>>>>>>>values < -MATE+300, I set them to exactly -MATE+300 and leave the flag as is.
>>>>>>>>>>>>>
>>>>>>>>>>>>>This position is cute. Because not only is it a mate in 6, but there are
>>>>>>>>>>>>>transpositions that lead to mate in 7, mate in 8, and there are shorter (but
>>>>>>>>>>>>>non-forced) mates in 4 and 5. And there are stalemates, and positions with
>>>>>>>>>>>>>1 legal move, and so forth.
>>>>>>>>>>>>>
>>>>>>>>>>>>>You ought to find the following variation as one mate in 6:
>>>>>>>>>>>>>
>>>>>>>>>>>>>Kh3, f2, Kg2, Ke2, Kg3, f1=Q, Kh2, g5, hg, Kf3, g6, Qg2#
>>>>>>>>>>>>>
>>>>>>>>>>>>>If you find a shorter mate, it is wrong. If you find a longer mate, you
>>>>>>>>>>>>>are probably just extending like mad on checks (crafty finds a mate in 8 at
>>>>>>>>>>>>>shallow depths (9 plies, 2 secs on my PII/300 notebook), and doesn't find the
>>>>>>>>>>>>>mate in 6 until depth 10, 3 seconds.
>>>>>>>>>>>>>
>>>>>>>>>>>>>It is a good test as the transpositions are real cute with white's king caught
>>>>>>>>>>>>>in a tiny box, but with several different moves that triangulate and transpose
>>>>>>>>>>>>>into other variations...
>>>>>>>>>>>>>
>>>>>>>>>>>>>If you get it right, you have either handled the bounds right, or else you are
>>>>>>>>>>>>>very lucky. IE Crafty 16.17 gets this dead right. But if I disable the eval,
>>>>>>>>>>>>>it goes bananas, yet the eval is not important when mate is possible.
>>>>>>>>>>>>>
>>>>>>>>>>>>>Have fun...
>>>>>>>>>>>>>
>>>>>>>>>>>>>I did... :)
>>>>>>>>>>>>
>>>>>>>>>>>>A simple solution: do not store a position in the hash table if there is
>>>>>>>>>>>>no best-move. It solves the mate-cases and also repetition cases. Also
>>>>>>>>>>>>there is no speed loss of the search.
>>>>>>>>>>>>
>>>>>>>>>>>>Ed
>>>>>>>>>>>
>>>>>>>>>>>Do you mean by "no best-move"
>>>>>>>>>>> bestmove == 0
>>>>>>>>>>>or
>>>>>>>>>>> best<=alpha, after having searched all moves (best: minimax score)?
>>>>>>>>>>>
>>>>>>>>>>>What I do:
>>>>>>>>>>> if bestmove == 0 then don't store anything, just return the score (mate or
>>>>>>>>>>> stalemate).
>>>>>>>>>>>
>>>>>>>>>>>Alessandro
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>that doesn't make sense to me. If _every_ move at one node in the tree returns
>>>>>>>>>>alpha for the score, which is the best move? And since you don't have one, you
>>>>>>>>>>don't store anything? That hurts performance, because the next time you
>>>>>>>>>>encounter this position, you get to search it again, while I discover that the
>>>>>>>>>>last time I searched it I returned alpha, so I can just do that now and not
>>>>>>>>>>search anything...
>>>>>>>>>
>>>>>>>>>No, no. My answer was misleading. What I mean is explained by the following code
>>>>>>>>>(the code is simpilied!). I have marked the important things by an "****". It is
>>>>>>>>>assumed that
>>>>>>>>> - when the king is removed from board its position is -1 ( < 0)
>>>>>>>>> - alpha, beta < INF
>>>>>>>>>
>>>>>>>>>Alessandro
>>>>>>>>>
>>>>>>>>>int AlphaBeta (int alpha, int beta, int depth) {
>>>>>>>>>
>>>>>>>>>//**************************************
>>>>>>>>>// legality check:
>>>>>>>>>
>>>>>>>>> if (myKingSquare<0) return -INF;
>>>>>>>>>
>>>>>>>>>//**************************************
>>>>>>>>>
>>>>>>>>> if (depth==0) return Quiescence(alpha,beta);
>>>>>>>>>
>>>>>>>>> // here use info from the transposition table
>>>>>>>>>
>>>>>>>>> best= -INF; bestmove= 0; startalpha= alpha;
>>>>>>>>> i= 0; n= GenMoves();
>>>>>>>>> while (i!=n && best<beta) {
>>>>>>>>> // m[i] is the current move
>>>>>>>>>
>>>>>>>>> make(m[i]);
>>>>>>>>> value= -AlphaBeta(-beta,-alpha,depth-1);
>>>>>>>>> unmake(m[i]);
>>>>>>>>>
>>>>>>>>> if (value>best) {
>>>>>>>>> best= value; bestmove= m[i];
>>>>>>>>> if (best>alpha) alpha= best;
>>>>>>>>> };
>>>>>>>>> i++;
>>>>>>>>> };
>>>>>>>>>
>>>>>>>>>//**********************************************
>>>>>>>>>// no best move => mate or stalemate
>>>>>>>>>
>>>>>>>>> if (bestmove==0) {
>>>>>>>>> if InCheck(Me) return -MATE+ply;
>>>>>>>>> return STALEMATE;
>>>>>>>>> };
>>>>>>>>>
>>>>>>>>>//**********************************************
>>>>>>>>>
>>>>>>>>> // here update the transposition table
>>>>>>>>>
>>>>>>>>> return best;
>>>>>>>>>}
>>>>>>>>
>>>>>>>>
>>>>>>>>Same question as before. The above simply doesn't work as you think it
>>>>>>>>does. Here is why.
>>>>>>>>
>>>>>>>>at ply=N you set best to -inf, and then step thru each move and do a search
>>>>>>>>after making it. And you pass that search a value for alpha and beta that is
>>>>>>>>used to terminate the search when it can prove that the score below that move
>>>>>>>>is >= beta (which at our ply=N node means the move we tried is <= alpha.)
>>>>>>>>
>>>>>>>>So lets assume that after we search the first move, we get a score back that
>>>>>>>>is obviously > -infinity, but < alpha. You remember that move as "best". But
>>>>>>>>the problem here is that the 'proof' search stopped as soon as it found a score
>>>>>>>>> beta. It didn't try _all_ moves to get the largest score > beta, just the
>>>>>>>>first score > beta... which is why we refer to the search as returning a bound.
>>>>>>>>At least as low, but maybe even lower.
>>>>>>>>
>>>>>>>>So you end up with a bunch of random bounds that are all <= alpha, and you take
>>>>>>>>the largest one and assume that is the best move and store that move in the hash
>>>>>>>>table? I will run some tests as this is easy to do, but when I tried this a few
>>>>>>>>years ago, my tree got _bigger_. And when I looked into why, I found myself
>>>>>>>>searching nonsense moves from the hash table _before_ I got to the winning
>>>>>>>>captures (the first of which was a move that would refute the move at the
>>>>>>>>previous ply.)
>>>>>>>>
>>>>>>>>Easy to test. I'll supply some data in a bit, just for fun...
>>>>>>>
>>>>>>>For one moment forget about alpha and beta, you are on the wrong track as
>>>>>>>alpha and beta are not a part at all of the code. You need an extra stack
>>>>>>>that is set to -INF at each ply. Then before you do A/B you do the bestmove
>>>>>>>calculation for that ply. Involved variables: SCORE and STACK, no alpha beta.
>>>>>>>
>>>>>>>Ed
>>>>>>
>>>>>>I think the best way to explain is to write a small piece of code in pseudo C,
>>>>>>else we talk around the point.
>>>>>>
>>>>>>Alessandro
>>>>>
>>>>>
>>>>>OK... here is what I did:
>>>>
>>>>Drunken code adjustment inserted ................
>>>>
>>>>
>>>>>
>>>>>Normal alpha/beta first:
>>>>
>>>>Drunken code added:
>>>>
>>>>>
>>>>>int Search(int alpha, int beta, etc...) {
>>>>> best=-infinity;
>>>> roughbest = -INFINITY;
>>>>> bestmove=0;
>>>> roughbestmove = 0;
>>>>> foreach (move in movelist) {
>>>>> MakeMove();
>>>> roughvalue = StaticEvaluate(-whatever,etc);
>>>>> value=-Search(-beta,-alpha,etc.)
>>>>> if (value > best) {
>>>>> best=value;
>>>>> bestmove=current.move;
>>>>> }
>>>>> if (value > alpha) {
>>>>> if (value >= beta) {
>>>>> return(value);
>>>>> }
>>>>> alpha=value;
>>>>> }
>>>> if (roughvalue > roughbest)
>>>> {
>>>> roughvalue = roughbest;
>>>> roughbestmove = current.move;
>>>> }
>>>>> }
>>>> if (THEREWASNTANEWALPHA)
>>>> HastStore(roughbestmove, etc...)
>>>> else
>>>>> HashStore(bestmove,alpha, etc...)
>>>>>}
>>>>>
>>>>>
>>>>>
>>>>>So what I did was to simply take the score for each search made after trying
>>>>>one of the moves at this ply, and remember the 'best' score and associated move.
>>>>
>>>>So what you needed to do was think about having an semi-accurate evaluation
>>>>function at each internal node, rather than a search based quiesence score.
>>>>
>>>>
>>>>>
>>>>>All I am saying is "this does not work". It is a characteristic of the alpha/
>>>>>beta search. It isn't a "it might work if ..." it simply won't work. Because
>>>>>the searches below this node (again, assuming this is a fail-low node where _no_
>>>>>move produces a score > alpha, which is the case where I claim there is never a
>>>>>best move to try here) return a bound on the value for that move. And I have no
>>>>>idea how to choose between a move with a bound <=200 and another move with a
>>>>>bound <= 150. Because the first could have a score well below 200. I simply
>>>>>don't know as I told the search below this node to stop whenever you find a
>>>>>score > X, where X is my negated alpha bound.
>>>>>
>>>>>Now, we have code. Did I misunderstand what you are saying? If not, then I
>>>>>can certainly explain further why that 'best' and 'bestmove' above are no good
>>>>>in this context. You can think of "best" as a random number that is <= alpha,
>>>>>nothing more. Which means "bestmove" is a random move chosen from the moves
>>>>>searched at this ply. And that is _not_ the move we want to try first when we
>>>>>get back to this position and it is suddenly not a fail-low position where all
>>>>>moves have to be tried, but rather it is a fail high position where the best
>>>>>move will let us cut off quickly...
>>>
>>>
>>>That is worthless. You are saying that you would try the best move suggested
>>>by your static evaluation there? I say you are wasting a bunch of time. And
>>>I don't think Ed uses his static eval as you suggest, although I could be wrong.
>>>
>>>I would _much_ prefer my simpler captures-first approach when I come back here,
>>>as that is much less expensive to compute than the static eval. And in most
>>>cases it would be more accurate, since most moves are refuted directly by a
>>>simple capture...
>>
>>Would the substitution of
>> roughvalue = StaticEvaluate(-whatever,etc);
>>with
>> roughvalue = Quiesce(-whatever, etc);
>>appease?
>>
>>Dave
>
>
>No. And here's why (this is the same reason that Chris's original idea
>is very ineffecient.)
>
>We are searching moves one by one. And each returns a score <=alpha,so we
>can't use that to reasonably pick the one that is best. So we either use
>the static eval (Chris) or else call Quiesce() (your idea) for each move to
>get some sort of score.
>
>OK, we have invested a _lot_ of cpu time to do either of those. And the
>probability that we will search this position again and use this suggested
>best move is only 1 in 10 during the middlegame (about 10% hash hits is what
>I normally see, roughly, in the middlegame).
>
>So we invest all that computer time to store a hash move that isn't used 90%
>of the time, anyway.
>
>Why not wait until we reach a position where the hash table has no suggested
>best move, and _then_ generate all the moves, and for each one either call
>Evaluate() (Chris) or Quiesce() (you) and _now_ order the moves based on this.
>Same amount of work. But only done 1/10th of the time.
>
>In chess, the credo is "never do today what you can put off until tomorrow,
>because tomorrow may _never_ come..."
>
>That was why I said the original "rough_best" idea from Chris was NFG,
>because there is another way to do the same thing and I'd hope that everyone
>agrees that using either eval or quiesce to order moves as I suggested would
>_really_ slow the program down... Far more than just forgetting the hash move
>and dropping into the best-capture-first move ordering.
>
>Was that understandable or too rambling? It is almost 12am here so it could
>be incomprehensible for all I know. :)
Do not underestimate the idea that in case there is no bestmove from the
hash table you do a full static evaluation of all nodes first and based
on that you pick the bestmove as being the first move you are going to
search for this (new) depth. The very early Rebel's (1981) worked that
way and I remember (although the system is very time consuming) it was
superior to all other systems I tried.
I later removed the system because hash tables + bestmove was more powerful
at least for Rebel. But I wouldn't exclude the possibility such a system
can have a positive effect on the speed of the search.
Actually I didn't remove the system but I replaced it with a faster one
that is:
- generate all legal moves;
- for all moves do a (very) quick evaluation;
- sort all moves based on the quick evaluation.
This (move ordering) system (for Rebel) is still superior.
Ed
===========================================================================
Hundreds more besides these. This is just a sampling collected at random.
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.