Kevin Vance - Expertly beaten by my own AI. Right now it's a bit slow…

Entries | Archive | Friends | Friends' Friends | User Info

05:20 pm

Saturday, October 28th, 2006
Previous Entry Share Next Entry

HexxagonDS photo

Expertly beaten by my own AI.

Right now it's a bit slow implementation-wise, but algorithmically I think it's good. The game tree is searched using NegaScout, with the moves reordered by inserting them into a balanced BST (Andersson tree). There's a lot I can optimize, like all the extra information getting passed around every negascout recursion.

It can do a full search to depth 2 in in 0.5 to 2.5 seconds, which is perfectly adequate for opponents like me. I'd like to have a full depth 3 search, but the middle game search times can get over 60 seconds per move. I doubt I'll be able to optimize away that much time. Also, it TROUNCES me looking three moves ahead. Way more embarrassing than the previous screenshot:

An embarassing defeat
Link )Reply )

(Deleted comment)
[User Picture]From: kvance
2006-10-28 09:44 pm (UTC)
Andersson trees have a simpler implementation, and I like to keep it simple. A more impressive excuse would be that the smaller code size will have more instruction cache hits (the ARM9 has a "mere" 8KB).
(Reply) (Parent) (Thread)