Author: Alessandro Damiani
Date: 02:31:18 09/11/99
Go up one level in this thread
On September 10, 1999 at 21:49:16, Bas Hamstra wrote:
>On September 10, 1999 at 17:57:38, Alessandro Damiani wrote:
>
>>On September 10, 1999 at 17:38:31, Robert Hyatt wrote:
>>
>>>On September 10, 1999 at 17:05:33, Alessandro Damiani wrote:
>>>
>>>>[..]
>>>>>>>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:
>>>>>
>>>>>Normal alpha/beta first:
>>>>>
>>>>>int Search(int alpha, int beta, etc...) {
>>>>> best=-infinity;
>>>>> bestmove=0;
>>>>> foreach (move in movelist) {
>>>>> MakeMove();
>>>>> value=-Search(-beta,-alpha,etc.)
>>>>> if (value > best) {
>>>>> best=value;
>>>>> bestmove=current.move;
>>>>> }
>>>>> if (value > alpha) {
>>>>> if (value >= beta) {
>>>>> return(value);
>>>>> }
>>>>> alpha=value;
>>>>> }
>>>>> }
>>>>> 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.
>>>>>
>>>>>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...
>>>>
>>>>I never said something against that. When I read Ed's answers I see what you
>>>>say: fail-soft AlphaBeta. What you say is what I think all the time:
>>>>
>>>>best: score of the position after all moves are searched.
>>>>
>>>>best<=alpha => the real score of the position is <=best. There is no information
>>>>about the best move.
>>>>
>>>>bestmove==0 => best==-INF (after searching all moves)
>>>>
>>>>I think, Ed should write down a small piece of code.
>>>>
>>>>Alessandro
>>>
>>>
>>>There are only three choices here.
>>>
>>>(1) best <= alpha. We don't know anything about any of the moves. Yet I
>>>believe Ed (and I thought you as well) said that if you take this 'best'
>>>move and store it in the hash, it works well. In my test, it didn't.
>>>
>>>(2) alpha < best < beta. This is a move with an _exact_ score that is
>>>correct. Also known as a PV-candidate move normally.
>>>
>>>(3) alpha < beta < best. This is a fail high move. It is better than the
>>>best that is allowable. It is _not_ the best move at this level however, it is
>>>just good enough to produce a score >= beta and terminate the search early.
>>>This is the case that feeds (1) above at the previous ply. If we try _another_
>>>move here we might get an even _bigger_ score here, and back up an even worse
>>>score to the previous ply. But alpha/beta makes us stop _now_.
>>
>>This is the postcondition of AlphaBeta. In all three cases I store the best move
>>in the transposition table. BUT (I wrote that somewhere in an answer!) I don't
>>use that move in the case the score belonging to that move was an upper bound.
>>The code in Fortress:
>>
>>[[
>>precondition: depth>0 && (height, bound, wasSingular) is the information from
>> the transposition table.
>>
>> // there is no best move when the score was an upper bound.
>> // But we need the move for Singular Extensions, if it was singular
>> if (height>0 && bound==UPPER && !wasSingular) HashMove[ply]= 0;
>>
>> here: code for move ordering.
>>]]
>>
>>Conclusion: I do the same thing as you do, Bob.
>>
>>I store the best move to have an additional check to avoid hash errors, when the
>>hashtable is looked up (move must be pseudo-legal).
>>
>>I don't understand what Ed says.
>>
>>Alessandro
>
>So you *do* retrieve a LOWERBOUND type of move from the hashtable and use that
>as a bestmove? Then you do it not exactly like Bob, I think, who uses only EXACT
>moves as bestmoves. Does it work?
>
>Most informative discussion. I see I have to change things.
>
>
>Regards,
>
>Bas Hamstra.
Yes, I store a random move at UPPER positions, but I don't use this move for
move ordering. I need it for two reasons:
1. Singular Extensions. This is very important!
2. To check for hash errors (I am able to store only 52 bit of the hashcode, so
I use the check for legality of the move to "add some bits")
Alessandro
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.