Alpha beta, bounds and cutoffs, ....

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Alpha beta, bounds and cutoffs, ....

Postby crystalclear » 21 Feb 2012, 21:32

I've written a chess engine and I've been looking at how some of the parts in the search routine work,
or maybe why they don't - as my engine isn't playing too well.

I'd welcome some comments on the text below, for example
1. is there a standard terminology for the different ways of limiting the work done in the alpha beta search,
2. do some of the things I describe below work and others not,

Is there a good explanation somewhere of search instability?
I have a feeling that search instability might the reason that some imaginable improvements to a basic alpha beta search
don't work. Of the ideas described below, I think some work, and some don't, but because I haven't got my head around this
properly, I'll not say which of the ideas I think are flawed for fear of misleading people.

Also, what have I missed? It seems that search engines implement a mixture of improvements over a fairly simple loop in alpha beta searches
and I'd like to try to get as many as possible into my engine while limiting myself (of course) to just the ones that work.

When changing my chess engine once, I made what I thought was an improvement to the alpha beta search, which should have generated more cutoffs.
But when I looked at results, the node count had increased. I presume the explanation was that different moves were evaluated
in the process of attempting to find a superior score and so there were less hits on the transposition table.
It would be better to find a TT entry equivalent to search 100,000 nodes, then to actually search 1,000.
But I don't have the faintest idea what techniques one uses to try to steer alpha beta searches towards finding TT entries
rather than going down a fresh path.


BITS OF CODE IN ALPHA BETA SEARCHES
------------------------------------------------

alpha narrowing
The transposition tables say that the lower bound for the evaluation of the position is greater than alpha,
so raise the value of alpha to the table value.

beta narrowing
The transposition tables say that the upper bound for the evaluation of the position is less than beta,
so lower the value of beta to the table value.

beta stopping
If beta is an upper bound for the evaluation, then stop when it is found, eg when searching with iterative deepening at depth 3 ply
we can stop if a mate in 2 is found, as there cannot be a better move (mate in 1).
(If there were a mate in 1, we'd have found it when we searched at depth 1 ply.)

zero window narrowing
Do a zero window search to determine whether the next move considered is better than the best move found so far.
If the ZW search scores it better (score s say), just search in the range s to beta, rather than in the range
alpha to beta or best-so-far to beta.

zero window cutoff exiting
Do a zero window search to determine whether the next move considered is better than the best move found so far.
If the ZW search scores (s) is better than beta, stop the search immediately, returning s.

lower bound greater than beta exiting
If the tranposition tables say the lower bound value is greater than beta, dont even search.
Just return the lower bound.

beta blocking
Return beta (or beta+1 depending on how inequalities work in the search program) when a beta cutoff occurs.
Some chess programs do this, and I temporarily understood why. Now I have forgotten.
crystalclear
 
Posts: 91
Joined: 22 Sep 2011, 14:19

Re: Alpha beta, bounds and cutoffs, ....

Postby Gerd Isenberg » 25 Feb 2012, 12:11

In PVS, adjusting bounds aka Alpha and Beta narrowing at PV-Nodes (> null window) is avoided in many engines due to search instability issues. Some engines even don't exit from hash at PV-nodes at all.
Gerd Isenberg
 
Posts: 285
Joined: 31 Jan 2005, 20:31
Location: Hattingen, Germany


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Majestic-12 [Bot] and 3 guests

cron