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

Re: computer-go: Programming the capturing game



In go, a good heuristic for sorting is to try the best enemy response
next.  This works very well in Many Faces' tactical analyzer, and
I think Thomas Wolf uses it in Gotools.  It might do better than
the tradition killer heuristic from chess.

- David Fotland

At 11:53 AM 2/6/2002 +0100, Erik van der Werf wrote:
Tristan Cazenave wrote:
>
> great!
>
> I also used iterative deepening and transposition tables,
> but I did not use the history heuristic and the killer
> moves.
> I will try with these heuristics in both alpha beta and
> AGPS and see how they compare...
> Do you have other move ordering heuristics ?
> (I start with the liberties of the string that has the
> less liberties...)

This is what I use for the move ordering:
1  Transposition move
2  First Killer move
3  Second killer move
4- Moves ordered by history heuristic (single table for both sides)

History heuristic and the killer moves each gave me about between 80%
and 90% node reductions for solving 5x5. I was thinking of also putting
in countermoves, but it didn't seem to improve the performance. I don't
use use the liberties for move ordering, currently the effective
branching factor is already below 3.5, so I don't think that using the
liberties will have much effect.

> You wrote your solution is depth 15, and the shortest one
> I found was depth 17... I am quite interested in seeing
> your solution...

Initial setup:
(3 3)-(3 4)
(4 4)-(4 3)
-----------
PV:
1 (2,3)-(3,5)
3 (4,5)-(5,5)
5 (5,3)-(4,2)
7 (5,4)-(4,6)
9 (5,2)-(3,6)
11 (3,2)-(2,4)
13 (3,1)-(4,1)
15 (5,1)


> So the next challenge is solving the empty 6x6 board ?

Well yes, although at the moment I'm not really working on it. I think
it may be done by using the board symetries and itterative widening. A
PN search might also do the trick. Unfortunately I don't have much time
at the moment, maybe I'll look in to it later...

> Is it harder than the 8x8 board with a cross cut ?

From what I can see the 8x8 with a cross cut looks significantly harder,
however I can only be sure when I know how deep the search actually
needs to go..

Erik
David Fotland