Solved

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

Posted on 2003-11-04
16
1,426 Views
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!!!
0
Comment
Question by:benjambb
  • 4
  • 4
  • 2
  • +3
16 Comments
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

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!

Kent
0
 

Author Comment

by:benjambb
Comment Utility
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.
0
 
LVL 45

Accepted Solution

by:
Kdo earned 168 total points
Comment Utility

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.


Kent

0
 
LVL 45

Expert Comment

by:sunnycoder
Comment Utility
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 !

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

Assisted Solution

by:imladris
imladris earned 166 total points
Comment Utility
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).
0
 
LVL 16

Assisted Solution

by:PaulCaswell
PaulCaswell earned 166 total points
Comment Utility
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.
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 16

Expert Comment

by:PaulCaswell
Comment Utility
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.
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

Hi Paul,

That's pure evil.  ;)

0
 
LVL 16

Expert Comment

by:imladris
Comment Utility
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.
0
 

Expert Comment

by:Fluffy_Checkers
Comment Utility
Hi,
      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-
0
 
LVL 16

Expert Comment

by:PaulCaswell
Comment Utility
I'm still intersted and would be happy with an even split.
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

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

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

0
 
LVL 16

Expert Comment

by:PaulCaswell
Comment Utility
Sunnycoder,

I'm fine with that.

Kent,

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.

Paul
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
reading tzdatabase for timezone definitions 5 122
Adjust Mfcapp 29 154
Coverting 24 hour time to 12 hour in C++ 15 162
Problem to ASCII 1 148
Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
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…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.

762 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

13 Experts available now in Live!

Get 1:1 Help Now