[computer-go] Example for Morphys law in Evaluation

[Magnus Persson]

Quoting Wang Yizao <yizao.wang at polytechnique.edu>:

> Magnus Persson wrote:

>> I see monte carlo evaluation as something that not yet has reached its full
>> potential.
>>
>> With static full board evaluation one needs a complete and correct
>> implementation of all possible situations that are likely to arise on a go
>> board. If there is limits in the evaluation then I think search will not be
>> able to compensate for this.
>>
> Probably I didn't well understand what you mean by 'search' here. 
> Could you explain a little more it?

With search I mean using alfa-beta search with iterative deepening and use an
evaluation function at terminal postions. I am probably confusing you by not
clearly distinguishing between AB-search and MC-search.

>> With MC evaluation one can add some simple local knowledge which 
>> improves the
>> evaluation in most situations, and search work quite well in removing those
>> moves that evaluated too high early in search.
>
> Do you mean pruning by search here?

No I just mean that after 2 seconds move A is best but after 20 seconds B is
best.

>>
>> I attach a very nice 9x9 test position (from a real game on CGOS) I 
>> have used
>> during the development of Valkyria as an example of what MC-eval + a litlle
>> knowledge can do. White plays first and should try to live but Black 
>> has some
>> really nice tesujis to keep white from living but white can connect 
>> all stones
>> and win. There is also a very nice sequence where black kills white if white
>> makes the obvious response.
>>
>> The nice thing about this position is that black can keep attacking 
>> white to for
>> about 11 ply which Valkyria now can see in a few minutes with very selective
>> UCT-search.
>
> What do you mean by selective UCT-search here?

I mean just UCT. I just wanted to point out that UCT often spend most 
effort on
just a few moves and produces very deep good looking principal variations. In
this sense alfabeta is selective too, but until I have implemented an 
efficient
Alfabeta search with MC-eval in Valkyria it is hard to do a fair comparison.

UCT (as implemented in Valkyria) searches deeper because it does not 
try to find
the best winning move, it just keeps exploring good winning moves until it has
been refuted.

Note that this behavior might be extreme for Valkyria. I have not yet 
done some
proper experiments to test how strong the program becomes, when it searched
wider or more selective. I just a picked a value for the UCT calculation that
appears to work well.


> I ran MoGo to solve the problem, and it is always happy to play the white.
> The worse is, even I could not see this nice sequence of black that 
> kills the white...
>
> MoGo proposed E1 D2 H4 very quickly and I can't see how to kill the 
> white after.
> What is the tesuji for black then?

MoGO is too strong. There are two winning moves (I think). If H4 is 
played first
then it may become interesting. Valkyria never liked E1 so it it sticks to H4
and proves that it wins. You might try to play H4 first and then let black try
to find the best move. Black cannot kill white but if black plays G3 and white
replies with G4 then Black has a nice counter. But I guess that MoGo will play
E1 which is the correct move in this situation. Still even after E1 black can
play a lot of forced moves the could be easy to overlook.

So perhaps this is not that good as a test position after all, unless you test
it with a weak enoguh program.

>>
>> When I started working on Valkyria it would sometimes not even get the first
>> move right in 10 minutes of thinking time, but with some basic go 
>> knowledge it
>> now can go very deep. I think this positions is special in the sense that it
>> can be searched very deep quickly, but the forcing moves that has to 
>> played for
>> the first 6-7 ply are not trivial.
>>
>> If your static evaluation is good then you might not need to search 
>> deeper than
>> 6-7 ply to see that white is alive or connected, but if the evaluation makes
>> errors then this might be really hard for traditional full board search.
>
> Here are you talking about the 19x19 board of the 9x9 one? I think 
> UCT works already pretty well for the 9x9 and it is not easy to 
> overpass it by adding static evaluations (since it is often not that 
> good).

I am talking about 9x9, but whenever I talk about static evaluation I 
talk about
traditional alfabeta search. My point is that MC-evaluation on 9x9 can become
very effective with very little programming effort. My speculation is that
traditional AB-search with static evaluation may either be to slow or produce
too many severe evaluation bugs such that the search become ineffective. There
are some good programs that do search with an evaluation function but the
question is if they will be able to improve it beyond the current level or if
they have reached a plateau where additional programming effort gives very
little back. It is possible that MC-programs may also reach a point 
were adding
more complex knowledge will slow the MC-search too much.

I know my latest posts have been a little confusing, maybe because I have been
writing about 3 different programs:

Viking4: 1ply full board search with complex static evaluation for 
19x19 (I also
experimented with selective alfa beta full board search on 9x9).
Viking5: alfa-beta search with MC-evaluation 9x9 but can play 19x19 with
aggressive pattern based pruning
Valkyria: UCT-search that builds a tree in memory, by playing pseudo random
games from terminal positions found by applying UCT. 9x9

-Magnus