Author: Alessandro Damiani
Date: 09:36:54 09/11/99
Go up one level in this thread
On September 11, 1999 at 09:48:57, Robert Hyatt wrote:
>On September 11, 1999 at 05:27:21, Alessandro Damiani wrote:
>
>>On September 11, 1999 at 00:34:46, Robert Hyatt 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
>>>
>>>
>>>I assume this means that for UPPER positions, you are just storing a random
>>>move that you searched? Or are you using that "bestmove" trick to pick the
>>>one with the highest value (even though it is still <= alpha?)
>>>
>>>validity checking isn't unreasonable, although if you are using 64 bits, I
>>>don't think it is worth the effort. I _never_ get errors reported on such
>>>moves, unless I introduce a bug... That is the only reason I actually leave
>>>the "ValidateMove()" test in the code in fact...
>>
>>
>>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
>
>
>How do you use a 'random move' in singular extensions? I have played around
>with this from time to time, but haven't yet decided to try it 'in production'
>as I don't like how it behaves so far.
>
>However, I don't quite see how a random move would be very important (your
>words) for SE. If you aren't ready to discuss what you are doing, however,
>that is perfectly ok. I'll explain what I have been twiddling around with once
>I consider it 'working'...
The problem with SE is the definition of singularity: it is defined as a
function of search depth. One move can be singular with search depth 5 and not
with search depth 6. And again singular with search depth 7.
What happens:
We are on a PV-node and the score of move x is in (alpha, beta). You test move x
for singularity with search depth d, and the test is positive. You search it one
ply deeper, but now the score is <= alpha.
Two cases:
1. another move m has a score > alpha:
What information do we have? The singular move was losing. Currently I accept
the new best move and store it in the hashtable as usual. Although I am not
happy with that, since:
the singular move x is losing => all moves are losing (since x is singular)
But the problem is the definition that depends on search depth. :(
2. all other moves have scores <= alpha:
I keep the singular move as best and store it in the hashtable (as you tried to
make understand all the time, there is no best move at a fail-low, so we can put
in the table what move we want). The idea is to avoid all the problems the Deep
Thought team had with search anomalies. In the next iteration the move from the
hashtable was singular but with an upper bound as score. The important
information is that it was singular, so now it will be extended again.
With this method the current Fortress finds in the following WAC position the
mate at iteration number 6 (very quickly!):
r2r2k1/pb3ppp/1p1bp3/7q/3n2nP/PP1B2P1/1B1N1P2/RQ2NRK1 b - - 0 1
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.