1

I know about alpha-beta pruning and the minimax algorithm.
What other algorithms would you suggest?

Is it possible if we use negascout?

Pops
  • 30,199
  • 37
  • 136
  • 151
ckd1914
  • 11
  • 2
  • 7
    Just parse http://xkcd.com/832/ and store in a moves database. :) – cherouvim Feb 02 '11 at 11:15
  • http://xkcd.com/832/ But seriously, what's wrong with alpha-beta pruning, has it proven too slow? If not, you should try it first and see if it suits you. There's no point in implementing an elaborate algorithm where a simple one will do. Unless of course you're trying to research the algorithm itself. – biziclop Feb 02 '11 at 11:17
  • "a strange game. The only winning move is not to play." – anno Feb 02 '11 at 11:31
  • @biziclop alpha-beta pruning is widely used. and we are looking for an algorithm that can surpass alphabeta pruning and minimax. – ckd1914 Feb 02 '11 at 12:59
  • @ckd1914 Are we talking about an extended tic-tac-toe game here? Because you don't need any of these algorithms for the 3x3 version. You can just store the winning moves. – biziclop Feb 02 '11 at 13:15
  • 1
    You might find the discussion here useful too http://stackoverflow.com/questions/125557/what-algorithm-for-a-tic-tac-toe-game-can-i-use-to-determine-the-best-move-for – Robb Feb 02 '11 at 14:06

2 Answers2

8

Considering the simplicity of the game the optimum moves can be simply stored.

Relevant XKCD-

Community
  • 1
  • 1
Robb
  • 3,801
  • 1
  • 34
  • 37
0

Tic-Tac-Toe's entire game tree can be represented in memory, so you can just generate that and backtrack winning moves. There are less than 363k legal configurations.

Svante
  • 50,694
  • 11
  • 78
  • 122
Eugene Talagrand
  • 2,214
  • 1
  • 14
  • 16