[computer-go] Example for Morphys law in Evaluation

[Yizao Wang]

Magnus Persson wrote:

> 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.

I think I understand now. You want to compare static evaluation by 
tactical heuristiques/go knowledge with MC evaluation, right?

>>> 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.

In fact this is also every often in MoGo's experiments. Probably after 
another 20 seconds it will change to C or back to A, finding that B is a 
bad one. The problem is, in real games, like on CGOS, MoGo's time is 
somehow limited. This does matter a lot when situation is too close.

>
>>>
>>> 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.

Exactly.

>
> 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.

Sorry but MoGo is not that clever yet :-) Since black can not win the 
game anyway, it is rare for him to find the best local move here (in 
which case it will lose the game too surely).

MoGo preferred J3 most of the time during the first 200000 simulations. 
Then it seems to me that he was going to play G3 ultimately. I stopped 
it after 700000 simulations.
However, E1 is never among its 5 most tested moves.

>
> 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
>>
Just one suggestion. I think it would be better if you gave the number 
of simulations instead of time used, as the speed depends a lot on the 
programming techniques and machines. All the comparisons between 
different MoGos (:-)) are based on the same number of simulations for 
each move.

>>> 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.
>
Yes, it is clear for me now. I did not realize that you were comparing 
MC with AB sometimes.

> 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

Sorry but I'm a little confused. You said before that "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.", what is the difference then between Viking5 and this to be 
implemented AB-search with MC-eval in Valkyria?

> Valkyria: UCT-search that builds a tree in memory, by playing pseudo 
> random
> games from terminal positions found by applying UCT. 9x9

Valkyria_UCT is very similar to MoGo from what you described here. Their 
levels are also very close :-)

Yizao

>
> -Magnus
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>