Skip to content

Notes on an evil algorithm

Jump to bottom
Ian Carroll edited this page Nov 26, 2016 · 2 revisions

A few notes on your ultimate destruction.

Just something to let you know I'm thinking about you...

First Idea:

The algorithm could be unbeatable if it is able to:

  1. Win: Check if there is an opportunity to win next move.
  2. Don't let you win: If none, then check to see if it can keep you from winning next move.
  3. Fork for the win: If none, find a way to set itelf up for a win in two moves by creating a "fork" so no matter what you do next, it still wins.
  4. Don't let you fork for the win: If none, prevent you from making said "fork". Don't let you fork.
  • by distracting you with an emergency elsewhere on the board.
  • by occupying the one spot you need to make a fork.
  1. Hold the center: Otherwise, take the center square.
  2. Occupy the early fork: If the center is taken, and you took a corner, take the opposite corner from you.
  3. Establish a stronghold: If the center square is taken, take a corner square.
  4. Whatever: If the center and all the corner squares are taken, take whatever remains. (sides are undesirable)

These strategies should work regardless of whether it plays first or second. I don't know how these strategies will hold in the context of other board dimensions.

Second Idea:

On the other hand, there may be another way to do it by using a series of 48 board states to test against, and returning the propper response to each. That is how the tinkertoy tic-tac-toe worked. Reproducing that in software would not be too hard, though could be less elegant than another method.

Not to mention it's more brittle. What would I do if I wanted to play any m,n,k-game?

Third Idea:

On the third hand, There may be a CS way. I am only vaguely aware of this, but noughts and crosses is a game tree that can be searched using a minimax method with unlimited depth. The trick is that perfect games end in a tie, how would you go about finding the optimal way to tie? That's heavy on theory, and I have not the foggiest clue right now of how to turn that into actual code. More research required for that...

There might be limits to brute forcing the entire game tree. I'm not sure what the wait times will be when it starts getting to larger games.

Clone this wiki locally