# basic ai without tree structure (min-max)

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

## 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 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 on other sites
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 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 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 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 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 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 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 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 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....

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 10
• 9
• 34
• 16
• ### Forum Statistics

• Total Topics
634125
• Total Posts
3015668
×