[computer-go] Monte-Carlo for Tactical Search

[Harri Salakoski]

>Some monte carlo programs have started using patterns.   Local search is no
>doubt helpful for specific things and I think some monte carlo programs
>do a little of that.
Maybe you could even formulate that.

N is list of legal moves.
A is pattern/heuristic answers question "is point p sure good"
B is pattern/heuristic answers question "is point p sure bad"
C heuristic answers (fast) if A and B then something?

Each heuristic should affect propabilities what positions are selected for 
global search.

A can answer question using some amout of time t.
Which then  slows search t * N per ply.
Faster is better.
Also if pattern can be pre-classified to be used only some phases of 
game(where those are most useful) that
kind of makes pattern better as it don't waste resources points of game it 
is not needed.

If B gives 50% of bad points and newer gives any good points as a bad it is 
worth of using even quite slow.
if A gives 100% of good points and also some bad points it is ok.

If you have 1000/ or(X) such patterns/heuristics in use. It should be 
possible to measure and compare which pattern combinations
make it play best. Legal move and filling own eye heuristics are I think 
quite must.

I am planning to use GP/or other search techniques to fine tune those 
patterns but it is quite complex as whole after all so takes some time 
before bot is ready. So planning to use different search techniques in 
offline and online.

t. harri




----- Original Message ----- 
From: "Don Dailey" <drd at mit.edu>
To: "computer-go" <computer-go at computer-go.org>
Sent: Friday, September 01, 2006 4:11 PM
Subject: Re: [computer-go] Monte-Carlo for Tactical Search


>I was responding more to the general misconception than anything you
> said in particular.   You just reminded me of it with something you
> said.
>
> I think what will happen in the future of go programming is that all the
> techniques will gradually come together.  Monte Carlo programs started
> out purely random, now they have a "tree in memory" portion.   Some
> monte carlo programs have started using patterns.   Local search is no
> doubt helpful for specific things and I think some monte carlo programs
> do a little of that.   And now there is talk of adding a little monte
> carlo to a conventional program.
>
> It might be rather like mtd() in chess.  At one point there were all
> these different kinds of searches, PVS, scout, and top level aspiration
> and more - but mtd showed them all in a simple framework.  In a way they
> are all variations of each other.
>
> - Don
>
>
> On Fri, 2006-09-01 at 09:10 +0200, Benjamin Teuber wrote:
>> Hi Don,
>> I get the impression our little debate was rather based on a
>> misunderstanding than a real different view...
>>
>> Global search is fine, as long as it does something more than just
>> playing out games until the end - of course, even that might be a
>> misconception of mine.
>> And while others are working to improve the search in general, I'd like
>> to think about the things needed in an evaluation function, and how to
>> make use of MC for these things.
>> I also don't think the evaluation should replace MC by a 100% - they
>> should rather be concurrent sources of information, whose reliability
>> can be judged using probability theory.
>>
>> Benjamin
>>
>>
>> Don Dailey schrieb:
>> > Whenever I mention the phrase "global search" it's usually followed up
>> > with something like,  "that doesn't work" or "that's stupid."   So I'm
>> > on your side of this issue.   Most people assume I mean brute force
>> > stupid search but I envision something like what you are saying.
>> >
>>
>> > I don't know if monte carlo programs will every reign supreme - they
>> > seem to be doing ok on small boards and I think they will be improved
>> > tremendously - but the way they are done now they are basically global
>> > searchers.   The "monte carlo" part could be replaced with an 
>> > evaluation
>> > function.
>> >
>> >
>> >
>> >
>> >>> Also,  it's very clear that monte carlo is very scalable.  In
>> >>> real terms that means it will eventually "outrun" any
>> >>> technique that is not.
>> >>>
>> >> This is clearly a true statement, but it seems that you are assuming 
>> >> that
>> >> the existing strong programs use techniques that are not scalable. 
>> >> But
>> >> existing progrrams are scalable.  They are running on much stronger
>> >> processors today than they were 20 years ago, they use more time, and 
>> >> they
>> >> are stronger.
>> >>
>> >
>> > I'm only arguing for scalable methods, but I admit that I didn't 
>> > realize
>> > the best programs are scalable.  I should listen to the real programmer
>> > more - many others are very critical of using search "because it can't
>> > possibly produce a super grandmaster."
>> >
>> >
>> >
>> >
>> >> David
>> >>
>> >>
>> >>
>> >
>> > _______________________________________________
>> > computer-go mailing list
>> > computer-go at computer-go.org
>> > http://www.computer-go.org/mailman/listinfo/computer-go/
>> >
>> >
>> _______________________________________________
>> computer-go mailing list
>> computer-go at computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/