Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

How to create AI in games like suduko/snake and ladder/tic-tac-toe in general board games where computer is a another opponent.

share|improve this question
2  
Basically this boils down to 'how can I implement an AI for a board game'. There is no AI in snakes and ladders. There is no ai in sudoko either. –  The Communist Duck Feb 3 '11 at 19:07
1  
There is AI in sudoku. It's a boring uninformed search with constraints, but that's still a traditional AI domain. (Somewhat famously, norvig.com/sudoku.html.) Otherwise I agree, this is far too general. –  user744 Feb 3 '11 at 20:59
2  
@Joe: I think Duck meant to say there here isn't a competing AI in 2 of the 3 games mentioned. Suduko is single player, snakes and ladders doesn't allow the player to make decisions. Furthermore, Tic-Tac-Toe is so trivial as to not need AI, 20-40 LOC to play perfectly. –  deft_code Feb 4 '11 at 0:44
    
You don't have to take the ladder in snakes and ladders so some decisions are left to the players. –  John Jan 15 '13 at 0:14

4 Answers 4

This is a really general question, so you're probably only going to get overly-general answers until you post a new, more specific question.

It's also going to differ pretty significantly depending on the style of game. For example, the algorithms used to implement Sudoku solvers differ from those used to solve tic-tac-toe, chess, or Go (game trees / alpha-beta pruning). And I'm not sure what kind of AI is necessary for Snake -- generally it tends to be mostly random.

Alpha-beta pruning is probably the most common search technique for most of the class of board games you're thinking of (at least as far as I know, but I'm admittedly not terribly familiar with AI). There's also Negascout and whatever this is (these last two links aren't that great, if you spend more time sifting through the Google search results you can probably find better since you presumably have a more detailed idea of what you're really looking for).

share|improve this answer

The question is a bit vague, so I'll give a primer on the subject.

To make an AI opponent, you'll need to create a sub-routine that considers the current state of the board and chooses a move, just like the player would. For example, in Tic-Tac-Toe, the subroutine would look at the state of the nine positions of the board, and choose where to place its own mark.

Now, how does this subroutine choose what move to make? In a simple game like Tic-Tac-Toe, each optimal move is obvious from the rules of the game (try to make three in a row and don't leave open lines to the player). For more complex games like chess, that depend on strategies beyond one move, you start looking into AI.

AI is basically "guessing for computers" - algorithms that calculate not the best move, but a move that -could be- good. AI algorithms involve, among others:

  • Searching through all possible moves (for this turn, two turns, etc) and calculating which one is "better" (through mathematical formulas called 'heuristics')
  • Predicting what the player character will do and trying to minimize damage;
  • Memorising track of what strategies worked in the past and reusing them.

From here it's a matter of studying AI algorithms, discovering which ones work best for your specific game, and implementing the math in code.

A more indepth look at all the steps of AI programming for games can be found at Programming Game AI by Example, by Mat Buckland (http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782)

share|improve this answer

I would suggest trying to write down how you yourself would think step-by-step when considering what move to make in a game. Once you define small-enough steps, all you need to do is put them into algorithm.

Most likely it will not be a small program. I would suggest to start from preparing a very general idea and a very basic principle how moves will be determined. Most likely it will appear not good enough at first and you will need to add more and more code to compensate bad decisions. At some point you will reach what you want. At least this is how I did it in my TicTacToe website. Try yourself - http://www.xo-play.com.

share|improve this answer

What you could do is do like the old computers did when solving board game: Have the computer play through the game many times (> a couple thousand, not so hard to do if you remove player input). Each time it gets to a decision, choose randomly, but have it mark that it made that decision. Then have it analyze based on the other games where that same exact decision was made, and compare the results of those to the ones where the opposite choice was made.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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