Re: computer-go: Alpha-Beta Search

["Gary Boos" <gboos@xxxxxxx>]

As far as other programs not trying to solve the problems - I know of none
and I have spoken with D. Fotland a lot.
        Gary
---
---
-----Original Message-----
From: P.J.Leonard <P.J.Leonard@xxxxxxxxxxxxxxxxx>
To: computer-go@xxxxxxxxxxxxxxxxx <computer-go@xxxxxxxxxxxxxxxxx>
Date: Wednesday, November 17, 1999 8:31 AM
Subject: Re: computer-go: Alpha-Beta Search


>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