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

Posted on 2003-11-04
Medium Priority
Last Modified: 2010-04-15
I want to use the method of backtracking and assigning a (1=winning move, 0=draw move, -1=losing move) to a series of trees.  I am also intrested in pruning the trees so I don't have to do an exhaustive search.  

I have a made another user function that will provide me with a board structure and the users last move.  My computer move function I am going to define like:

board *play_turn_computer(board *b,type t,char *player_last_move)

I dont know exactly how to make a tree of boards with every possible move and search it for which move will be most likely to win.  I have never tried backtracking before, but everyone I've asked personally says that will be the best way to implement an AI computer player.

Any examples to get me started would be great!!!
Question by:benjambb
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 4
  • 2
  • +3
LVL 46

Expert Comment

by:Kent Olsen
ID: 9681134

You want to build your search as a recursive function.

int Board[5][5];

int ExamineBoard (Board)
  /*  Make a move  */

  ExamineBoard (Board);

  /*  Unmake move  */

The tricky part comes in determining which moves are winning, losing, or "building" moves.  And which moves are better than others.

And once you've determined that a move is a winning move, then what?  You're several levels into the recursive process and one of the moves that got you there might result in losing on the next turn.

Each turn must be evaluted on it's own merit.  This means studying the logic of the game and determining the result of each possible move and what makes it better or worse than any other move.  It will take quite a knowledge of the logic of the game and the ability to translate that logic into C code.

Good Luck!


Author Comment

ID: 9681467
First off I want to thank you for the speed of your response Kent.

I guess I need to explain what route I'm taking better.  I believe the final function will be a recursive one, however, I would never go down a tree of game boards to get to a move that would win the game if one of the moves got me there would result in a loss, because that would make that whole tree have a value of -1 at the very first branch.  The only subtree that wouldn't have a -1 if I could lose on the next turn would be the case in which I would choose the space to block the win.  Of course then upon recieving the next board and user move, I would need to rebuild all possible game trees and evalute which subtree has the highest value (best chance to win).

My problem is I'm really good at knowing what I want done, I just dont know how to translate it into code.  I need a function that will produce subtrees for all possibilities with a opt out of maybe 3 levels down so I don't spend an enormous amount of time doing an exhaustive search, and then somehow (i assume through returning and recursion) send the best case value (hopefully a 1 or 0) back up to my function telling me which subtree had the best result, therefore letting me know which space to fill with my game piece.

Hope this helps, cause I'm very frustrated that I stink at programming, even though I seem to know what I want to do.
LVL 46

Accepted Solution

Kent Olsen earned 672 total points
ID: 9683231

Taking on a recursive task is a heck of a challenge for someone that doesn't believe in his own programming skills.  Still....

I can give you a shell of the function that you'll need for evaluating all of the combinations.

Let's go over the rules:  The board is 5x5.  How are moves to be made?  In true tic-tac-toe you can move to any open square.  In a board game very similar to tic-tac-toe that also uses a 5x5 board, your play must occupy the lowest open square in whatever column you choose.  How many aligned tokens does it take to win?

Also, no play is an automatic loser.  Playing a token can NOT give the opponent the required alignment until the opponent plays so we have no such thing as a losing move.  Moves may result in a loss, but are not by themselves losers.

OK.  On to the function.

int AddPiece (int Board[5][5], int WhosTurn)
  int x, y;

   We want to add a piece to the board and test the outcome.
   We can do this with two for() loops, or to add randomness we
   can randomly pick open spots.  For now, use the for() loops.

  for (x = 0; x < 5; x++)
    for (y = 0; y < 5; y++)
      if (Board[x][y] == 0)  /* This position is "free"  */
        Board[x][y] = WhosTurn;
        EvaluateBoard (Board, WhosTurn);  /*  You'll want to save the returned value  */
        AddPiece (Board, WhosTurn ^ 3);
        Board[x][y] = 0;   /*  Restore board to the "real" current value;

This is overly simplistic.  No provision has been made to determine how to judge a position, to save the value of the position, or to compare it to another position.  But it will march through the entire board and look at all possible combinations of moves.

The two players are numbered 1 and 2.  If Board[x][y] is zero, no player has a piece there.  WhosTurn^3 toggles WhosTurn between 1 and 2.

Well, there's lots of work to do, but this is a start.


Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

LVL 45

Expert Comment

ID: 9686441
I have posted some helpful theory regarding this problem in your other question. As far as implementation of this problem goes:::

1. write clearly what you want ... you should have no problems doing that
2. figure out a method how to do it
3. write that method in sordid details, step by step, crystal clear fashion
4. recognize that you have states
5. devise data structures to represent a state
6. devise representation for your search space
7. you have everything written in plain english ... all you need to do is translate it into C :o)

the problem sounds formidable but is not that difficult if you divide it into small parts rather than getting intimidated by it...

The amount of efforts required for coding the entire problem is enough to discourage experts here from writing the entire code... you will have to believe in yourself and take the lead... we are right behind you and will help you out whenever you are stuck... I have given you suggestions for approaching the problem while Kent has given you ample hints to get started... Give it a shot

Good Luck !

Congrats... Let me pick up some loose ends at work and I'll revert to you :o)
LVL 16

Assisted Solution

imladris earned 664 total points
ID: 9687679
You say

>if one of the moves got me there would result in a loss, because that would make that whole tree have a value of -1 at the very first branch

However, the difficulty is that you usually cannot determine the value of a move in such a definitive fashion. In fact, you can't evaluate a "move" at all. What you can evaluate is a board *position*. The value of a "move" might be the difference between the value of the position before the move, minus the value of the position after the move.

But that's not the way it is normally done. It has so far been consistently shown that the best strategy for a computer game program is one variation or another of generating a tree of as many moves as it can, and evaluating the final positions (at the leafs of the tree). The position evaluation routine is the heart of the program, where the bulk of the intelligence and quality of its play resides.

The rest is geared towards generating the deepest tree it can in the time allowed. The amount of the tree to consider can be optimised with alpha beta pruning (that is based on the evaluation of the board position down one branch, it may become clear that investigating the rest of that branch is indeed pointless).
LVL 16

Assisted Solution

PaulCaswell earned 664 total points
ID: 9687793
I did this once in Pascal as a personal exercise to brush up on my Pascal coding. Here are a few tips that worked for me.

Use 0 for a position without a piece +1 for one player and -1 for the other. In this way you can evaluate a position by adding up all the values of all possible lines on the board. In your case, if any line sums to +/-5 then call this board a win for one or other player.

Dont pass the whole board up the recursion tree. Pass a pointer to it and, at each level, make the move, evaluate the board then unmake the move. Athough you are using a 5x5 board and are therefore limited to a maximum of 25 recursion levels the board structure itself can be a bit big and the code ends up spending more time copying the whole board onto the stack than actually thinking about the position.

Once you've got it to never loose, try changing it to win as often as possible. It's a very interesting exercise.

Dont get too upset when the final result beats you every time. Remember, if you manage to beat it then the algorithm is wrong.
LVL 16

Expert Comment

ID: 9688262
PS This struck me as amusing:

#define f(X,g,p,N,M)M{return X?a&b?a&b&1<<i&&m(b,a^1<<i,9)>8?i:M:0:9;}main(){\
int a=511,b=a,i=4;for(;X;b^=1<<N)a^=1<<g-'1',g,p(N+'1'),p('\n')}     /* 123 */
f(i--&&b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b  /* John Rickard   */ /* 456 */
&273&&b&84,getchar(),putchar,m(b,a,9),m(a,b,i)) /* xxx@xxxx.xx.xx */ /* 789 */

It plays 3x3 ttt. Run it and enter your move as per the comments.
LVL 46

Expert Comment

by:Kent Olsen
ID: 9689161

Hi Paul,

That's pure evil.  ;)

LVL 16

Expert Comment

ID: 9702243
Did any of those answers help?

If so, it is now time to choose one and grade it.

If not, perhaps a clarifying question would help.

Expert Comment

ID: 9784524
      I was just browsing and had some brief thoughts to add to Paul's comment on using +1 and -1's. I would have used incremental numbers for each turn adding the next highest number to the board each time. That way all odd numbers are one person and all even numbers are for the other. This also means that you can do full retracement back to the beginning of the game by removing numbers in reverse order. Winning could be determined by checking the lines around the last move (and you already know if the last moves was by the odd or the even player) and seeing if for each of the 5 elements for each of the lines you are checking if they are all appropriately odd or even. =)

-Fluffy Checkers-
LVL 16

Expert Comment

ID: 10392668
I'm still intersted and would be happy with an even split.
LVL 46

Expert Comment

by:Kent Olsen
ID: 10392689

A split seems quite fair, though I WOULD penalize Paul for that macro.

I still believe that it's pure evil....    ;)

LVL 16

Expert Comment

ID: 10523342

I'm fine with that.


I'll try to hunt down 'John Rickard' who was the proud originator and berate him with a beer or two as penalty.

John Rickard,

If you ever come across this conversation, contact me somehow, it seems I owe you a beer.


Featured Post


Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

719 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