Author: Robert Hyatt
Date: 14:38:31 09/10/99
Go up one level in this thread
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 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.