Solved

5x5 tic tac toe problem using backtracking to make the computer's move (using C)

Posted on 2003-11-04
7
16,699 Views
Last Modified: 2013-12-26
I need some example source code to figure out how to make a intelligent computer move using backtracking.  I want to make a tic tac toe problem only use a larger (5x5) grid so its not always guaranteed a draw playing a smart user.

I have made code to make a random move, but to make the game competitive I want to use the bactracking/tree method so that the user has to think about how to beat the computer opponent.

 
0
Comment
Question by:benjambb
  • 2
  • 2
7 Comments
 
LVL 5

Accepted Solution

by:
SethHoyt earned 250 total points
ID: 9684676
What you want is a function that estimates the value of a board state. This value might represent the likelyhood of the computer winning from that state. Thus, the function might return 1 for a winning state, 0 for a losing state, and 0.5 for a draw state.

For other cases, this function either needs to make an estimate using some kind of heuristic (such as the least number of moves required to win) or by trying different moves and returning the value for the best move for whoever's turn it is. Thus, if it is the opponent's turn, the function would call itself recursively for different boards that result from different moves, then return the minimum of the values returned, since the opponent would choose the move with the worst result for the computer. For boards that represent the computer's turn, the function would return the maximum of the values that result from different turns the computer could take.

Because of the alternating minimum and maximum, this is sometimes called a minimax or min-max search. Try searching google for minimax or try this link for more info and code examples:

http://ai-depot.com/LogicGames/MiniMax.html


-Seth
0
 
LVL 5

Expert Comment

by:SethHoyt
ID: 9684752
You may also want to take a look at this tic-tac-toe sourceforge project. It will do from 3x3 to 7x7 sizes:

http://ttt.sourceforge.net/


-Seth
0
 
LVL 45

Assisted Solution

by:sunnycoder
sunnycoder earned 250 total points
ID: 9685740
Hi benjambb,

First you need to identify and construct your search space... intially any move is possible and hence your search space would be the entire tree.

Next your main task would be to design a heuristic function... this function will analyze a move and tell the you how appropriate that move is... How smart your program will be depends entirely on how good your heuristic function will. A very simple heuristic function can be ::
check how close computer is to win or in other words how many more minimum number of moves will secure a win ( irrespective of opponents moves ) e.g. consider this board position

               0 | X | 0 | X | X
               X | 0 | 0 |    | X
                  |    |    |    |
                  | X |    | 0 |
                  |    |    |    |

computer is playing with 0 and human with X and its computers turn
In such situation, our heuristic will tell us that (3,3) and (5,5) are the two best moves as both of them will leave us just one step away from winning. On a scale of 1 to 5, these moves would be rated 4. All other moves will leave us farther from victory than these. However, if board is positioned like this

               0 |    | 0 | X | X
               X |    | 0 |    | X
                  |    | 0 |    |  
                  |    |    | 0 | X
                  |    |    |    | X

our heuristic will tell us that (3,4) and (3,5) are the best moves. Though they bring us closer to win, but that win will never materialize as opponent will win before we can. This happened because our heuristic function was not "smart" enough to take into consideration the opponents moves. (Never underestimate your enemy ;o) )

So we have to move on to some smarter heuristic like::
check how close computer is to a win and how far opponent is from a win... we use the same logic as before "how many more minimum number of moves will secure a win " but we add to it "how many more minimum number of moves hence will give victory to the opponent". The difference between the two is our guiding light

Clearly with the new heuristic, we would get to play (5,3) in the second board position...

As you would have observed, the smarter the heuristic, the better the play.

If you search through the entire tree, you would like to select a move which maximizes your gain and minimizes the opponents game at every alternate level. This is minimax search.
Minimax is a game-playing algorithm which is used to search a game tree. In games where opponents alternate taking turns which affect a board position (chess, checkers, etc...), a given position can be thought of as a node on a tree. All positions reachable from a given position are, therefore, children nodes on the game tree. Minimax recursively evaluates positions on a tree with the intent of selecting the best move for a given player in a given position. In order for a minimax routine to work a function that maps a board position into a ``score'' is needed. In two-player games often this evaluation function returns real values between -1 and 1.
definition from : http://www.darkridge.com/~jpr5/archive/alg/node181.html

there is wealth of information on the web regarding minimax search... explore it... if you have any queries feel free to ask...

Hope that helps

Cheers
Sunny:o)
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9835205
it has to be a split between me and SethHoyt .... 250:250 ?
0
 
LVL 84

Expert Comment

by:ozo
ID: 9934700
How many X's or O's in a row do you need to win?
If 5, the game is a guaranteed a draw playing a smart user,
If 3, the game is a win for the firsr player.

As a heuristic, I would number of plays on each row, column, and the diagonals
If both players occupy a row or column, that row or column is useless for a win,
otherwise, each row or column could be ranked according to how close it is to a win, you could then play on the square with the highest combined row and column scores
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Recently, in one of the tech-blogs I usually read, I saw a post about the best-selling video games through history. The first place in the list is for the classic, extremely addictive Tetris. Well, a long time ago, in a galaxy far far away, I was…
Polish reports in Access so they look terrific. Take yourself to another level. Equations, Back Color, Alternate Back Color. Write easy VBA Code. Tighten space to use less pages. Launch report from a menu, considering criteria only when it is filled…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…

759 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now