• C

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

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!!!
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Kent OlsenDBACommented:

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!

benjambbAuthor Commented:
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.
Kent OlsenDBACommented:

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.



Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Choose an Exciting Career in Cybersecurity

Help prevent cyber-threats and provide solutions to safeguard our global digital economy. Earn your MS in Cybersecurity. WGU’s MSCSIA degree program was designed in collaboration with national intelligence organizations and IT industry leaders.

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)
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).
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.
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.
Kent OlsenDBACommented:

Hi Paul,

That's pure evil.  ;)

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.
      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-
I'm still intersted and would be happy with an even split.
Kent OlsenDBACommented:

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

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


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.

It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.