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