A tic tac toe - that will make one move given an input

Question

Assume computer is playing as C and the opponent is playing as O. The bot must be intelligent enough to win when provided an opportunity. X represents a cell that is not taken. Also assume that computer made the first move

for eg:

Input1
CCX
XOX
OXX

Output1
CCC
XOX
OXX

What i want to know is how to approach this problem. Is there a specific algorithm to follow?. If yes please clarify it to me!

Have you seen http://xkcd.com/832/ ? This shows that in principle you can make a large table mapping positions to next best moves. Of course _generating_ that table would require an algorithm.... — Ray Toal, Aug 28 '13 at 05:58
Possible duplicate of [What algorithm for a tic-tac-toe game can I use to determine the “best move” for the AI?](http://stackoverflow.com/questions/125557/what-algorithm-for-a-tic-tac-toe-game-can-i-use-to-determine-the-best-move-for) — Bernhard Barker, Aug 28 '13 at 06:01
See this [answer][1] to the same question. [1]: http://stackoverflow.com/questions/9388474/how-to-code-simple-ai-for-a-windows-phone-board-game/9388582#9388582 — Novak, Aug 30 '13 at 11:33

score 3 · Accepted Answer · answered Aug 28 '13 at 05:59

Use the minimax algorithm.

Once that is implemented, define a simple heuristic, or evaluation function. It could go something like this:

function scoreBoard(board) {
  if(board.isWin()) {
    return 1;
  }
  else if(board.isTie()) {
    return 0;
  }
  else {
    return -1;
  }
}

score 2 · Answer 2 · answered Aug 29 '13 at 09:08

What you are looking for is the Minimax Algorithm. You can find details here: http://en.wikipedia.org/wiki/Minimax

The idea behind the algorithm is to generate all possible states, assume that the computer is intelligent and chooses the best move(maximizing its gain). Your move should minimize the gain of the computer.

A tic tac toe - that will make one move given an input

2 Answers2