-1

i have totally no idea regarding making artificial intelligence in a game (i am going to apply it on a simple Tic Tac Toe game)

my current idea is to make an array of possible options to win the game (like 3 X in row 1 = win or something) and then makes the computer try to fill the grid with one of the arrays, but how to choose the most appropriate option from others, and how to make it smart/stupid (difficulties) if possible i need an algorithm to use, and if possible a book that fills the gap in my brain =P

Best Regards

SAFAD
  • 774
  • 3
  • 14
  • 37
  • I read about some solution for the Tic Tac Toe AI that was based on Alpha/Beta-Search. Unfortunately I don't remember where I read this. – Nobody moving away from SE Jul 07 '11 at 20:26
  • and can you explain what the heck is alpha/beta search ? i'm self-educated and mathematics isn't a problem for me, but the level i am at doesn't allow me to understand such thing (if it is mathematical anyway =P) – SAFAD Jul 07 '11 at 20:28
  • Google is your friend: http://en.wikipedia.org/wiki/Alpha-beta_pruning – Charlie Martin Jul 07 '11 at 20:30
  • Well sorry for that but I am not good in educating others :) But you should follow the link to minimax search @Lirik gave,which employs alpha/beta-search. – Nobody moving away from SE Jul 07 '11 at 20:32
  • 2
    Trouble with Tic/Tac/Toe the game space is so small you can actually pre-compute every possible game (most games are a simple rotation of another game). Here is the solution: http://xkcd.com/832/ – Martin York Jul 07 '11 at 20:35

6 Answers6

4

Check out the wikipedia page on Game trees, tic-tac-toe is actually used as an example.

Andrew Clark
  • 202,379
  • 35
  • 273
  • 306
4

Here's the complete solution for you:

enter image description here

courtesy: xkcd

sehe
  • 374,641
  • 47
  • 450
  • 633
  • +1 just for the xkcd reference; the first thing that entered my mind when reading the question and then I scrolled down and saw it here :-) – Fredrik Pihl Jul 07 '11 at 21:30
3

Tic-Tac-Toe is a type of Zero-sum game and the "common" approach to such games is the Minimax algorithm. It's very efficient and fast, especially when combined with a good heuristic function.

There are some good C++ implementation of Minimax for Tic-Tac-Toe.

Update

Despite the fact that search algorithms such as Minimax fall under the AI algorithms category, I don't really consider them to be AI algorithms. I consider Minimax to be efficient search algorithms, so if you want an actual AI algorithm I would recommend looking into machine learning concepts such as: support vector machines, neural networks, genetic algorithms, genetic programming, etc. However, nearly all of the machine learning algorithms are going to be an overkill for the purposes of making a Tic-Tac-Toe agent/bot.

Kiril
  • 39,672
  • 31
  • 167
  • 226
  • [Negamax](https://secure.wikimedia.org/wikipedia/en/wiki/Negamax) is slightly better for zero-sum games than full minimax. – Fred Foo Jul 07 '11 at 20:38
  • Lirik: They most certainly are artificial intelligence algorithms. What makes you think that search algorithms don't fall under the category of AI algorithms. What algorithm do you think Deep Blue used to beat the reigning world chess champion? I think your point of confusion is that you grouped ML and AI together as if they are synonymous. All the algorithms you listed are ML, and search algorithms are not ML, but AI certainly includes many other things besides just ML algorithms. – Jeremy Salwen Jul 07 '11 at 21:42
  • @Jeremy, you're right, so I've clarified my answer. Minimax is considered to be an AI algorithm, but I feel like there should be a bigger distinction between search algorithms and AI algorithms. That's my personal view on the matter. – Kiril Jul 07 '11 at 22:02
  • Okay, so tell us what is an AI algorithm that's NOT a search algorithm. – Charlie Martin Jul 07 '11 at 22:18
  • @Charlie, they're still search algorithms, but I think ML algorithms better simulate intelligence because they are more flexible when it comes to getting out of local maximums/minimums and are generally non-deterministic. In ML, the same input can result in different algorithms. This "behavior" gives the impression of creativity and intelligence, whereas a search algorithm like Minimax is pretty much guaranteed to give the exact same output for the same input. – Kiril Jul 08 '11 at 00:11
  • @Lirik I think it all boils down to what you mean by intelligence. I certainly agree with you that a large part of intelligence is the ability to learn or adapt. But I still think there is room for static intelligence. I think chess champion with anterograde amnesia still deserves to be called intelligent to some degree. I think it would be ridiculous to ignore learning algorithms from "AI", but I think it would also be an equal mistake to ignore non-learning algorithms when exploring AI. Also, I think it's good to point out that as our AI gets better, we start to define fewer things as AI – Jeremy Salwen Jul 08 '11 at 00:48
2

The Tic Tac Toe game is a "solved" game in Game Theory. That means there is an ability to say is one or another game situation win or lose.

I think this link might help you.

Community
  • 1
  • 1
Microfed
  • 2,832
  • 22
  • 25
1

One possibility for simple games like tic-tac-toe would be brute force. If you have a winning move make it; otherwise if your opponent would have a winning move block that; otherwise consider every possible move recursively.

Charles
  • 11,269
  • 13
  • 67
  • 105
  • thought about that and its my idea, if tic tac toe won't make me learn AI i'll move over – SAFAD Jul 07 '11 at 20:29
1

Look, pretty much every AI issue comes down to some sort of search. In the case of tic-tac-toe, you're searching among all the possible board positions. There are 9 cells, and 3 values, so there aer only 39 possible boards. If you generate them at the start, your search is very straightforward: start with you current position, look at all the pathways that result in a win for your side, and pick that.

Charlie Martin
  • 110,348
  • 25
  • 193
  • 263