Author: jonathon smith
Date: 14:01:58 09/10/99
Go up one level in this thread
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...
This page took 0.01 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.