1

From Wikipedia:

Connect Four has since been solved with brute force methods beginning with John Tromp's work in compiling an 8-ply database[4][8] (Feb 4, 1995). The artificial intelligence algorithms able to strongly solve Connect Four are minimax or negamax, with optimizations that include alpha-beta pruning, dynamic history ordering of game player moves, and transposition tables. The code for solving Connect Four with these methods is also the basis for the Fhourstones integer performance benchmark.

I've been trying to speed up my Connect 4 algorithm, which currently uses Minimax along with Alpha-Beta pruning and a transposition table. I want to make it faster so decided to add in "dynamic history ordering of game player moves".

What exactly is "dynamic history ordering of game player moves"? I googled it but didn't find any resources that explained it. Could someone explain the concept, and if possible, tell mehow much of a speed boost I should expect?

dfg
  • 777
  • 1
  • 8
  • 24

1 Answers1

1

See this Answer: Dynamic move ordering. Transposition tables are used to do Dynamic move ordering:

Dynamic move ordering uses information from previous searches, either because you transpose into the same position again, or you have already reached the position in a previous less thorough search.

ConnectFour can benefit greatly from such a method since there will be a large number of repeat positions in its search trees, as opposed to a game with captures.

(PS - If your code is in Java, you can try it out on my Java game page, though it currently has an extremely simple algorithm.)

Community
  • 1
  • 1
Ari
  • 1,974
  • 19
  • 30