Re: computer-go: Alpha-Beta Search

["P.J.Leonard" <P.J.Leonard@xxxxxxxxxx>]

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.

   cheers Paul.
 






  

  

 2. Putting a lot of effort into ordering the moves so