What algorithm for a tic-tac-toe game can I use to determine the “best move” for the AI?

by

The strategy from Wikipedia for playing a perfect game (win or tie every time) seems like straightforward pseudo-code:

Quote from Wikipedia (Tic Tac Toe#Strategy)

A player can play a perfect game of Tic-tac-toe (to win or, at least, draw) if they choose the first available move from the following list, each turn, as used in Newell and Simon’s 1972 tic-tac-toe program.[6]

  1. Win: If you have two in a row, play the third to get three in a row.

  2. Block: If the opponent has two in a row, play the third to block them.

  3. Fork: Create an opportunity where you can win in two ways.

  4. Block Opponent’s Fork:

    Option 1: Create two in a row to force
    the opponent into defending, as long
    as it doesn’t result in them creating
    a fork or winning. For example, if “X”
    has a corner, “O” has the center, and
    “X” has the opposite corner as well,
    “O” must not play a corner in order to
    win. (Playing a corner in this
    scenario creates a fork for “X” to
    win.)

    Option 2: If there is a configuration
    where the opponent can fork, block
    that fork.

  5. Center: Play the center.

  6. Opposite Corner: If the opponent is in the corner, play the opposite
    corner.

  7. Empty Corner: Play an empty corner.

  8. Empty Side: Play an empty side.

Recognizing what a “fork” situation looks like could be done in a brute-force manner as suggested.

Note: A “perfect” opponent is a nice exercise but ultimately not worth ‘playing’ against. You could, however, alter the priorities above to give characteristic weaknesses to opponent personalities.

More Related Contents:

  1. What is the optimal algorithm for the game 2048?
  2. Algorithm for Determining Tic Tac Toe Game Over
  3. Unsupervised clustering with unknown number of clusters
  4. What are good examples of genetic algorithms/genetic programming solutions? [closed]
  5. How does Dijkstra’s Algorithm and A-Star compare?
  6. How do 20 questions AI algorithms work?
  7. Clustering Algorithm for Mapping Application
  8. Unique (non-repeating) random numbers in O(1)?
  9. How do I create a URL shortener? [closed]
  10. How do I calculate a point on a circle’s circumference?
  11. Algorithm for Additive Color Mixing for RGB Values
  12. Algorithm to generate all possible permutations of a list?
  13. Fast permutation -> number -> permutation mapping algorithms
  14. Algorithm to detect intersection of two rectangles?
  15. An efficient compression algorithm for short text strings [closed]
  16. Generating the partitions of a number
  17. How to detect the BPM of a song in php [closed]
  18. Find the shortest path in a graph which visits certain nodes
  19. Algorithm to separate items of the same type
  20. how to calculate binary search complexity
  21. What string similarity algorithms are there?
  22. Combined area of overlapping circles
  23. Quick Sort Vs Merge Sort [duplicate]
  24. Algorithm to find the maximum sum in a sequence of overlapping intervals
  25. Iterating over a Binary Tree with O(1) Auxiliary Space
  26. “Rounding” colour values to the nearest of a small set of colours
  27. What algorithm can calculate the power set of a given set?
  28. Color gradient algorithm
  29. What are the pitfalls in implementing binary search? [closed]
  30. Can a Fibonacci function be written to execute in O(1) time?

Leave a Comment