game AI algorithms 

So far this week I've implemented 3 for a that @netzzz devised.

1. randomly pick moves. keep track of the best valid move found. repeat until time limit.

2. methodical exhaustive search of moves ordered by increasing complexity. keep best valid move. continue until time limit.

3. use fancy heuristics to cascade through the space of neighbouring submoves. if time limit is reached give the best valid move found so far.

Algorithm 2 easily beats algorithm 1 with the same time limit.

Algorithm 3 is quite competitive and uses vastly much less CPU time (less than 0.1 seconds for a whole match, while I had the other algorithms using several seconds wall-clock time per move (albeit probably overkill); the algorithms are all parallelized).

If I reduce the time allowance for Algorithm 2 to match Algorithm 3's speed, Algorithm 3 wins very comfortably.

The algorithms are not perfect yet, they can still miss some complex moves in the end game with many flips.

· · Web · 0 · 0 · 1
Sign in to participate in the conversation

Welcome to, an instance for discussions around cultural freedom, experimental, new media art, net and computational culture, and things like that.