[Computer-go] News on Tromp-Cook ?

[valkyria at phmp.se]

I think first program who really used "3x3" patterns and other  
heuristics to make the simulations heavy was Viking 5. Unfortunately  
Viking5 was based on on Viking4 which was not designed for MC-search  
at all. I also had a completely different search method. Alpha-Beta  
search with Lazy MC-evaluation. This worked as follows. Instead of a  
normal evaluation function, something like 1000 simulations was run  
for a leaf position. When moves were evaluated safely below the alpha  
value it would stop search after 50 simulation. Similar for beta  
cutoffs (this is why I called it Lazy MC-evaluation).

It worked quite well. But when Mogo came around it quickly became  
stronger than Viking 5. And thus I started programming Valkyria. See  
my log for Viking5 here:

http://senseis.xmp.net/?Viking

I never published any papers about my programs, but I think I at least  
have made it clear to people reading this list that it is possible to  
use a lot of knowledge in playouts and benefit from which I guess all  
programs do.

-Best
Magnus

Quoting Fuming Wang <fumingw85 at gmail.com>:

> This is certainly a good time to sit back and look at what got us here. The
> following key ideas have been mentioned so far: UCB, MCTS, RAVE, Pattern and
> Go knowledge during MC simulation.These ideas are all essential to a strong
> MC based Go program.If we want to pick the most important idea that got us
> here, I would say it is the realization that adding Go Pattern and Go
> Knowledge to MC simulation can significantly improve the quality of board
> evaluation. This is amount to the important sampling concept in MC
> integration, which is very import for Monte Carlo applications in many
> fields. MC simulation with importance sampling give us for the first time a
> reasonablly accurate evaluation function for Go. UCB, MCTS, RAVE are
> certainly very important, however, it is still possible that new approaches
> that can achieve good results with just importantly samples MC simulation.
> So, I think MoGo is the most important break-through.
>
> Happy New Year, everyone!
> Fuming
>
>
>
> On Fri, Dec 31, 2010 at 9:20 AM, Aja <ajahuang at gmail.com> wrote:
>
>> Hi Jeff,
>>
>> When, do you think, did Mogo "started dominating all the KGS computer
>> events and CGOS, and also was the first to extend that dominance from 9x9 to
>> 19x19."?
>>
>> In Computer Olympiad 2007, Steenvreter was gold medal on 9x9. At the final
>> match of 19x19, it's easily to see that Mogo and Crazy Stone were close
>> (finally Mogo 1st and CS 2ed). But, at the end of 2007, Crazy Stone defeated
>> Mogo and won the UEC Cup (19x19). Afterwards, Many Faces won 9x9 and 19x19
>> on 2008. Zen and Erica won 2009 and 2010, both continuing Crazy Stone
>> thread.
>>
>> Mogo's biggest contributions, so far, in my view, are
>> 1.Applied UCT to computer Go, and such application came from the idea
>> "MCTS" that proposed in 2006 by Remi Coulom. Crazy Stone was using MCTS to
>> win 9x9 in 2006 Computer Olympiad.
>> 2.See 3x3 patterns around the previous move.
>> 3.RAVE (strictly speaking, it is invented by David Silver).
>>
>> UCT and RAVE are for both for the tree search. I think Crazy tone's
>> contribution for the playout is of same/or more important, because the
>> quality of simulations decide the playing strength much. From this view, we
>> should give Crazy Stone more and more credit.
>>
>> I don't mean to raise any debate. Mogo does has important contributions,
>> but it's not so hard to assign credit to Crazy Stone. By the way, we should
>> not forget Fuego and MyGoFriend. Anyway, I think SenSei's description is
>> out-of-date.
>>
>> Aja
>>
>>
>> -----????----- From: Jeff Nowakowski
>> Sent: Friday, December 31, 2010 5:43 AM
>> To: computer-go at computer-go.org
>>
>> Subject: Re: [Computer-go] News on Tromp-Cook ?
>>
>> On 12/30/2010 01:58 PM, David Fotland wrote:
>>
>>> You should also give more credit to CrazyStone as an early strong program
>>> that contributed many ideas, comparable to Mogo.  Remi is Aja's advisor,
>>> so
>>> Erica continues the CrazyStone thread.
>>>
>>
>> I did mention CrazyStone, and the Sensei's page lists it first as the
>> program that "started the new wave of MCTS programs by winning the 9x9
>> gold medal at the ICGA Computer Olympiad, in 2006."  Like I said in my
>> first message, though, it's hard to assign credit, and I don't mean to
>> slight other programs.
>>
>> However, MoGo was the program that really got people to sit up and take
>> notice, because it started dominating all the KGS computer events and
>> CGOS, and also was the first to extend that dominance from 9x9 to 19x19.
>> I believe the biggest breakthroughs were made with MoGo (building, of
>> course, on earlier ideas). This is easily verified by going back to the
>> archives and seeing how many people patterned their program after MoGo.
>>
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>
>