• Advertisement
Sign in to follow this  

basic ai without tree structure (min-max)

This topic is 2339 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I wrote a simple tic-tac-toe game. Although not practical, I use a picturebox for each game 'space' that can be occupied. When clicked, it changes to the appropriate 'x' or 'o' image and setting the tag to the 'owner' or player. I have been able to determine the winner by comparing the tags in correct orders...

I'm now trying to implement the most basic of ai's, using 2 checks and a fallback:
If ai can win, ai owns that space
Else If player can win, ai owns that space
Else choose random space from non owned spaces

However, I would normally just start coding it and "if'ng" every single possible combination inside each of those checks (resulting in way too many nested if's and repeating if's, etc)...

I'm wondering how might be a good way to go about this process?

I was thinking of something like this, but as you can see it can soon get out of hand...:

//check for win
for 1 to 9 // 9 spaces
if spacei has 'o' //owned by ai
if i = 1 //check +1,+2,+3,+4,+6,+8
if spacei+1 has 'o' //owned by ai
spacei+2 = 'o' //ai win
next
//check for blocking

//pick random

Share this post


Link to post
Share on other sites
Advertisement
Recursively processing the game states in some form of data structure is pretty much the canonical way to do this. Is there a particular reason you're trying to avoid that approach?

Share this post


Link to post
Share on other sites
I thought the recursive way was to ensure the 'always' draw or best move approach? I was trying to get a semi approach to the beginnings of an ai where it doesn't always find the 'best' move unless it can win or block a win.

Can the minimax stuff be set up to ensure a 'random' picking after the initial win/block checks? And since I didn't set up the board as a class or an array[,], how would be the best approach to recursively loop through the checks of the 'images' that make up the board?

Share this post


Link to post
Share on other sites
A recursive search through game states can be organized to look for any condition you want, it doesn't have to be a minimax-style optimization.

I still don't understand how your game board is actually set up. Do you mean that you don't have any representation of the game state besides the UI controls? If so, you're going to want to change that...

Share this post


Link to post
Share on other sites
[color=#1C2837][size=2]I still don't understand how your game board is actually set up. Do you mean that you don't have any representation of the game state besides the UI controls? If so, you're going to want to change that... [/quote]


I just keep a state for each picturebox (picturebox.tag) depending on who clicked it. blank = not occupied, x=player1 occupied, o=ai or player2 occupied. Even with this, shouldn't the ai function stuff be relatively the same?

Share this post


Link to post
Share on other sites
You want to separate your game logic (a structure representing the board position, a function that detects the end of the game and who won, a function that returns a list of valid moves, a function that performs a move on the board, perhaps one that undoes the move...) from the GUI representation. The implementation of the AI should be completely independent of whether you have pictureboxes or just a command-line interface.

Share this post


Link to post
Share on other sites
You can program the way you're doing it, and even get a working result; but using control tag properties to store game state is just adding a lot of rigidity and inflexibility where you really don't need that. As alvaro says, you want to separate those things. This isn't just an idealistic thing either; in your case, it'll be the difference between a massive hard-coded glob of nested if() statements and a really compact, elegant algorithm.

Share this post


Link to post
Share on other sites
Hmm, so what's the difference between looping through and checking array indexes compared to checking the tags? I'm not trying to be snickety about it, so apologies if I come off that way...

On second thought, let's forget the gui components for the moment...


The recursive function then should be set up relatively the same, something along the lines of passing in a space and who occupies it, and looping the other spaces checking if it's valid, then after all checks, pick a space...

Oh well, guess I'll just start coding and see what comes up...

Share this post


Link to post
Share on other sites
There is a bit-twiddling hack for this that is really neat, but perhaps you should write a more mundane solution first. I would just write one function with a bunch of `if' statements to determine if the current position is a win for a particular player.

bool is_won(Board const &b, int player) {
if (b[0]==player && b[1]==player && b[2]==player) return true;
if (b[3]==player && b[4]==player && b[5]==player) return true;
if (b[6]==player && b[7]==player && b[8]==player) return true;
if (b[0]==player && b[3]==player && b[6]==player) return true;
//...

return false;
}


Then write code that checks for each free square whether moving there is a win for yourself and whether it's a win for the opponent. Assign a score to each move that measures its priority, and pick the maximum.
int pick_move(Board b, int player) {
int best_move = 0;
int best_score = -1000000;

for (int move=0; move<9; ++move) {
if (b[move] != 0)
continue;
int score = std::rand() % 1000;
b[move] = player;
if (is_won(b, player))
score = 5000;
else {
b[move] = opponent(player);
if (is_won(b, opponent(player))
score = 4000;
}
b[move] = 0;

if (score > best_score) {
best_score = score;
best_move = move;
}
}

return best_move;
}

Share this post


Link to post
Share on other sites

Hmm, so what's the difference between looping through and checking array indexes compared to checking the tags?


You don't have to hardcode the control names into the array based version. It's just board[x][y] versus BoardControl3.Tag and BoardControl4.Tag and....

Share this post


Link to post
Share on other sites
[color=#1C2837][size=2]You don't have to hardcode the control names into the array based version. It's just board[x][y] versus BoardControl3.Tag and BoardControl4.Tag and.... [/quote]


That sounds a lot better suited code wise in reading and writing...


alvaro - Thanks for the examples, will prove helpful in re-fining the logic I'm going through!

Share this post


Link to post
Share on other sites
If you are interested, I have a Tic Tac Toe game I made for a friend a while back written in .NET. It also has a computer player with several levels of difficulty and uses a negamax search to find the best moves. I would be glad to send the source code to you. I made it for a friend who was trying to learn C#.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement