[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] Learning : was Chess programs versus go programs

Interesting.  I wonder to what degree if any these searchers are integrated.

David Fotland wrote: 
Searching is clearly the key to strong go play.  Many Faces has three
searchers in it.

A fast alpha-beta searcher for local tactics that decides if a block can be
captured or
get 5 liberties/two eyes to escape.

A full board alpha-beta searcher.

A best-first search life and death module.
When is the best-first life and death module used vs. the local tactics deciding if a block can be captured or can escape.  Are these results similar?
Neither alpha-beta searcher uses iterative deepening since the search depths
are so irregular.

The tactician looks typically 5 ply and up to 80 ply deep, with a budget of
a few hundred nodes
per search.  It has a transposition table, and it remembers the best move at
the root from move
to move, along with a list of board points that invalidate the search, to
reduce re-searching time.

The full board search looks 1 to 30 ply deep, with a budget of a few hundred
nodes.  The tree near
the root is taken from patterns or joseki library, and can be 1 to 20 or so
ply deep.  Then comes
a local quiescence search, then a global quiescence search.
Your node count budget seems very low, which implies you must do extreme pruning and look at only very few moves from the move generators.  Is there a reason you can't let it be a bit more free to search broader with todays hardware?

Have you ever considered combining tactical and full board, for example, the full board searcher using local tactical move sequence results from the tactical searcher (acting as a move generator) as its "nodes" to expand and search on? This would be one example of what I would call a multi-level search.
I don't use null move because the evaluation and move generators understand
threats already.

The best first search is similar to PN search except that it uses
probability of success from
the move generator rather than number of generated moves to pick a node to
expand.

Most of my time goes into tuning the move generators.
Are the move generators using hand-tunded pattern recognition and some kind move-ordering?
Maybe the move generators are hindering the searches ability to find appropriate tactical sequences in some situations.
Regards,

David

  
-----Original Message-----
From: computer-go-bounces@xxxxxxxxxxxxxxxxx 
[mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Matt Gokey
Sent: Tuesday, December 07, 2004 11:10 PM
To: computer-go
Subject: Re: [computer-go] Learning : was Chess programs 
versus go programs


Vincent, I don't necessarily disagree with you (about 
search).  As you recall in my message, I summarized my point 
like this:

    
There is little question in my mind that searching is a key to 
computer-go just as it was in chess.  It may not be the 
        
same kind of 
    
search (muti-level for example), and the evaluations 
        
(including life 
    
and death) may not be as easy but I think its the most promising 
direction to pursue in combination with pattern based concepts for 
move generation and help in evaluation.
        
So, the search technique is primary, of course paired with 
other things including solid evaluation.  Pattern or rule 
based module components could be hand coded, or auto 
generated/learned, or even coded by a 1000 monkeys as long as 
they work reasonably well.  But I've done enough hand tuning 
to know that intuition after a few iterations is as often 
wrong as it is right.  There is a lot of trial and error and 
guessing, albeit educated guessing. Each method has its pros 
and cons.  I'm well aware that you don't see value in 
automated learning or pattern harvesting.  And I certainly 
don't expect any learning system to "beat" human learning 
capacity.  That's not the goal or the expectation, however.   
There is something appealing about the objective and 
statistical nature of the pattern harvesting technique that 
Frank has developed over the ad-hoc and "expert" tuned 
pattern/rule sets commonly used.  I would not discount it as 
a useful part of a go-playing program.  As Frank has said 
it's designed to be a better Joseki/Fuseki database, not the 
holy grail.  There is nothing preventing combining it with 
other modules using other techniques for handling some 
tactical issues, local search, ladders, ko fights, life/death 
analysis, etc.

You seem to have a tendency to try to frame things as black 
and white only, then attack the extreme case, when no-one is 
really talking about the extreme case.

Regards,

Matt


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx 
http://www.computer-go.org/mailman/listinfo/computer-go/

    


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/

  
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/