Re: computer-go: Alpha-Beta Search

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 11:32 AM 11/17/99 +0000, you wrote:
>Hi,

> Alpha-beta is a value based search method. In my limited
>experience with alpha-beta (or at least what I programmed
>thinking it was alpha-beta) I found the main limitation 
>was that the search does not take into account the effort
>required to search a given area of a tree.
> Given the choice between two branches both of which
>could contian the best move no account is taken of the
>number of opponent responces to be visited to attempt to refute the 
>move. This can lead alpha-beta into areas of vast complexity and it
>is too stupid to realize that another branch could be proven quicker
>because the opponent has only a few reasonable responces. 

> As far as I understand alpha-beta gets around these problems
>by 
>
> 1. Limiting the depth of the search so complex situations 
>eventually exaust themselves. This is not so good if the search
>requires long forcing sequences with little branching. (Typical
>of GO)
>
> 2. Using good move ordering. So you are most likely to visit 
>the best move first.
>
>
> Alpha - beta is problably best for openning moves which has
>a very wide tree but only requires limited depth and you have 
>a good global evaluation function because stones are relatively
>stable.
>
>  When the board is unstable global evaluation depends on 
>a horrific problem which involves reading out many unstable
>local problems which can interact. The hope is to explore
>the tree to find a stable position which you can evaluate.
>The problems are:
>
>  - Detecting instable strings (not so hard).
>
>  - Deciding which local situations to focus on.
>
>  -- Estimating the worth of strengthing instable groups (very hard).
>  -- Looking for moves which are forcing in one local situation but
>    strength another situation.
>  -- Avoiding moves which strengthen the oponent.
>   
>  - How to explore 2 or more interacting branches of a search tree.
>  -- What are our objectives ?
>
> etc :-)
>
>  It is my belief that at present even the strongest go programs
>do not attempt to tackle these problems? Instead of focused local
>reading they use good heuristics based on shape (patterns).  
>In my opinion these heuristics should be applied to local
>objectives which in turn form part of a larger plan. However
>alpha-beta is not a good search method for this problem.
>
> Please note that these are only my opinions and they may be 
>wrong because I have not done much work on alpha-beta.
>
> In my opininion we should be looking at Proof Number based searching.
>I know some people have done so for local battles but I am not aware
>of any work done on using this scheme for resolving many interacting
>local situations, please shout if you have done so I would be interested
>in any results or opinions.

After proof number search, some started working at conspiracy number
search. 

I'm not very impressed by either proof number search nor conspiracy number
search.

Sure the ideas are good, but a very simple form of searching already
kicks hell out of them. 

The quality of the search in both algorithms is heavily dependant
upon the quality of the evaluation. So if the evaluation evaluates a
certain consequence very well, then it searches that branch further
and comes to the right conclusion.

However it already did recognize it as an important branch, so
it's questionable whether it was needed to search further.

I experimented quite some years with heavily selective searching 
(but still bigtime deplimited to not miss too much and not go too
deep certain branches), and i found it play positionally a lot
worse.

In GO currently it's very questionable whether nullmove+alfabeta will
bring a lot. Sure alfabeta PRUNING can be used correctly, yet
whether the depthlimitation with nullmove bring it, is questionable.

I find nullmove+alfabeta working very well in chess only at bigger depths.

Nullmove in combination with alfabeta is however a very human way
of seeing things.

I can imagine that making a quiescencesearch in GO which does a lot more
than just getting to quiet positions, so more likely adding a selective
search, is gonna work very well together with alfabeta and nullmove.

So then we talk about next algorithm with for nullmove reduction
factor R, which will be most likely 2 at most in GO.

doing a n ply search using PVS and alfabetapruning and nullmove:
  alfabeta(-infinite,infinite,n);

int alfabeta(int alfa,int beta,int depth ) {
  if( depth <= 0 )
    return(selectivesearch(-beta,-alfa));
 
  // nullmove
  if( depth-1-R > 0 )
    score = -alfabeta(-beta,-beta+1,n-1-R);
  else
    score = -selectivesearch(-beta,-beta+1);
   
  if( score >= beta )
    return(score);

  // Principal Variation Search or PVS
  makemove(firstmove); // make the first best move
  best = -alfabeta(-beta,-alfa,n-1);

  if( best >= beta )
    return(best);

  for all other moves {
    score = -alfabeta(-alfa-1,alfa,n-1);
    if( score > alfa && score < beta ) // research
      score = -alfabeta(-beta,-alfa,n-1);
    if( score > best ) {
      if( score >= beta )
        return(score);
      best = score;
      if( score > alfa )
        alfa = score;
  }
  return(best);    
}

Nullmove is very selective!

Now how to make the selectivesearch?
That will remain a good question.

Perhaps use 2 stages in it:
  first a few ply a selectivesearch that 'gambles' a few moves
  to be tried, but DEMANDS a move to be made (or passing of course)

  secondly after this what we call a quiescencesearch in which one
  side tries to optimize his score but first applying beta pruning 
  after evaluating.

This framework roughly describes already a very selective form of 
searching which skips big bunches of nonsense.

The better your evaluation and move ordering, the less nonsense it
will search!

Greetings,
Vincent

>   cheers Paul.
> 
>
>
>
>
>
>
>  
>
>  
>
> 2. Putting a lot of effort into ordering the moves so
>
>
Vincent Diepeveen
diep@xxxxxxxxxxxxxxxxx

---
... en verder ben ik van ben ik van mening dat Dap het gesticht in moet