Re: computer-go: Programming the capturing game

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

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