1

I'm developing a simple noughts & crosses game where the player plays against the computer.

Obviously, I use the Randomize function of the language, however, the final stage of refinement is to try to get the computer to block my winning move (as you normally would in a real game). This, of course, requires more intelligence on the part of the computer.

So far, I've just thought up of all the permutations one could have and built this into a large selection structure. This, as you can imagine, sees a lot of if / case statements.

Is there a smarter way of creating a noughts & crosses AI than simply outlining all the possible winning moves?

Thanks.

  • 2
    Google for "strategy tic tac toe". That will give you tons of simple strategies (there ar not so many to choose from).. E.g. quora.com/Is-there-a-way-to-never-lose-at-Tic-Tac-Toe – qwerty_so Nov 14 '16 at 9:48
  • You don't need AI for this, unless you're building AI for theoretical interest. Tic tac toe is easy to enumerate all the possibilities. There are articles in historic issues of "Popular Mechanics" that show how to make a Tic Tac Toe automated machine without any transistors or silicon, but I'll answer a smart strategy below. – Brad Thomas Nov 15 '16 at 18:36
  • 1
    The minimax algorithm is a potential algorithm for this – Richard Tingle Nov 15 '16 at 22:30
1

My naïve approach would be something like a priority order. You can detect winning moves by pretty simple pattern matching, ie check each row and column and diagonal for two of the same and an empty space. Once you have identified any or the lack thereof:

1) If winning move for you, make winning move. 2) Else If winning move for opponent, block winning move. 3) Else If row/column/diagonal with one of your pieces and two open spaces, fill in space. 4) Else fill in random r/c/d with 3 open spaces

The obvious problem here is defending against moves that create a no win situation two moves ahead (ie corner as opening move needs to be countered by center or opposite corner or you lose) and also utilizing them.

Doing a full search of all possible future states is a possibility given how small the space is, but it is also a strategy that doesn't scale to more complex games.

1

Is there a smarter way of creating a noughts & crosses AI than simply outlining all the possible winning moves?

Well, the 'smarter' the AI gets, the requisite information becomes the outlining of more and more possible moves. As the depth of possible moves increases, the AI can get so smart that you will never beat it. I've worked on such an implementation using the minimax algorithm with alpha beta pruning for a class using C++. All from the command line. If you're interested: https://github.com/JMeyer0101/AI_Project

0

Here's a strategy, but it's not really complex enough to qualify as "AI", go through these rules and play at the first one that works. Note better strategies may be possible, but this plays a reasonable game.

  1. Check to see if a win is possible - if so play there.
  2. Check to see if opponent can win - if so play there.
  3. Play in the center if possible
  4. Play in a corner if possible
  5. Play anywhere else

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.