Jump to content
  • Advertisement
Sign in to follow this  
GJ

Tic-Tac-Toe AI

This topic is 4094 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I started making a two player tic-tac-toe (naughts and crosses or what ever its called) about 2 days ago, as my first attempt at making something "worthwhile" in c++. Now I have finished, I was thinking of adding in an AI opponent, and I came here for a bit of guidance. The only way I can think of coding an opponent, is to use lots of if statements or something to that effect, to give a "priority" to every square, and then have it choose the highest priority square. My "grid" is stored as a single vector or int's. Is there a more efficient/straight forward way than all those if statements and would it be easier/better if my grid was stored as three vectors in another vector? Thanks for any help you might give.

Share this post


Link to post
Share on other sites
Advertisement
Using a single vector would be the best way really, its more efficient and not exactly difficult to use.

If I remember correctly tic tac toe is one of those games where if you're clever enough then you can never lose at it, only draw or win. As a result a computer could easily be made to never lose which would (for this game atleast) be utterly unfun.

To be honest I think that you could achieve the illusion of a worthy opponent simply by randomly choosing one of the free squares. You could continually pick squares at random until you find a free one or have a list of available squares (which may scale better) and just pick one.

Share this post


Link to post
Share on other sites
Choosing a random square is simpler for sure, but it's not artificial intelligence. There's actually a simple algorithm that is used for the AI in many games, from tic-tac-toe to chess and beyond. It's called minimax. Wikipedia has a good description of the algorithm, along with some pseudocode:

http://en.wikipedia.org/wiki/Minimax

Then, when you get that working you could try using the alpha-beta pruning algorithm, which will make your minimax code more efficient.

[Edited by - pkfx on September 27, 2007 12:45:58 AM]

Share this post


Link to post
Share on other sites
The first and most important thing - the thing the player notices the most if you don't get it right - is that if the AI can make a winning move, it probably should. So that's the first thing the AI can do, is look for winning moves it could make, and if it finds one, make it.

The second thing, if there are no moves that would cause an immediate win, is to look for moves the other player could make that would be a win. If one is found, make it yourself to block their win. (If there are multiple, then pick any; the AI's lost anyway at that point).

Once those are out of the way, it's a bit less clear what kind of move should be made. The center square can be used in 4 winning lines, the diagonals each in 3, and the laterals each in 2, so you should probably prioritize the squares accordingly.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!