Sign in to follow this  

AI in a dynamic Tic-Tac-Toe Game

This topic is 3581 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

Hi there, first of all, I tried using the search function but it didn't help me much (maybe I didn't use it properly, anyway...). First I explain what I mean by saying "dynamic" Tic-Tac-Toe: The grid of the game can be determined before the game starts, for instance the normal grid is 3 by 3. And can be 4 by 3 or what eer you might imagine. I already wrote a tic-tac-toe game with an AI, but it used the normal grid size and the AI was as basic as checking every possibility. Since the grid is dynamic I can't do that anymore, also the former AI wasn't really satisfying too much code for such a simple task. I began to think about implementing weights. I was inspired by some "tutorial" (more theoretic) about such a tic-tac-toe AI. It uses 2 Map, one called "friend" and the other "block"... Before I begin explaining all of this myself, I just link it... http://edais.mvps.org/Tutorials/TTTAI/index.html there are also two examples. Although there is the code (in VB, I am using c++) I can't really get through the code to know how this works. Also I've come to think that it might be a little difficult to do such maps for larger grid sizes. But so far this is the only idea that I have. I don't really want someone giving me the code, but more like giving me something like a general idea of how to accomplish that.... like helping me to help myself. After all, it is I who wants to lern stuff, and I want to think for myself, if possible, and not just copy & paste stuff. thank you in advance Qudeid [Edited by - Qudeid on February 10, 2008 2:05:04 PM]

Share this post


Link to post
Share on other sites
Yeah, I know about that, now...
But honestly, I consider myself stupid now -.-, I have not at all an idea of how to implement that in my game. I can't even begin to imagine how I get this to work. It is not that I don't understand the concept behind it, behind both, Alpha-Beta-Pruning and Minimax Algorithms... I just have no I idea to go on :-/

Any hints possible?

Share this post


Link to post
Share on other sites
Well, first, don't bother with alpha-beta pruning. It won't provide a noticeable performance increase here.

The basis of minmax is a set of mutually recursive functions, and if you haven't already, you absolutely need to wrap your brain around recursion in order to understand this stuff. Each function pretends it's a player, and decides, given a board position (that is, an arrangement of several Xes and Os on the board), what the best move is for that board position. To do that, it figures out what will happen if it makes each legal move, and picks the one that will give the best result for that player.


pair<Move, Result> XMove(BoardPosition bp)
{
if(O has won)
{
return (None, OWins);
}
else
{
Result bestResultForXSoFar= OWins; // worst possible result for X
Move bestMoveForXSoFar = None;
for(each possible move m)
{
(thisMove, thisResult) = OMove(bp augmented with m);
if(thisResult is better for X than bestResultForXSoFar)
{
bestMoveForXSoFar = thisMove;
bestResultForXSoFar = thisResult;
}
}
return (bestMoveForXSoFar, bestResultForXSoFar);
}
}
pair<Move, Result> OMove(BoardPosition bp)
{
// Looks exactly like the above function, with all Xes changed to Os, and vice versa
}

Share this post


Link to post
Share on other sites
@Sneftel: I will definitely look into recursion. Thank you for clearance.
But abotu Alpha-Beta-pruning. Since my grid size is variable, I thought that adding even one layer (4 by 4) extends the amount of possible moves a good deal. At least mathematically.

@chuck22: I don't know what you mean. Are you telling me that I shouldn't let the player chose width and height, and rather tie them together, that I have always a square?


PS: @Sneftel: To my shock, I just remembered that I didn'T even specify when someone has won the game. All that stands is the structure of the grid, also being variable, Player input and from the player class an inherited AI class. Since there is no logic so far only thing the AI can do is play randomly.

Actually, it seems like I'm totally blocked in my head now, because I can't solve the problem of determining who wins... Theoretically is it easy, 3 of X or O in a row column or diagonally. As with AI in the old version this was easy because I knew every single way of how one can win, this time it isn't the case, obviously.

My basic idea was to determine if to the left of right of one position is the same Marker.... Actually, I've come to an idea right now... check from every single position if there is the same marker left or right above or below or diagonally. So checking all immediate neighbors.... Only problem....since it is a table, I don't want the program to check spaces that aren'T there. for example left of 0,0 etc..... Do you think I could kill that problem with catching the exception? like "Hey, there is an exception that it is out of range, ignore it and continue"?

Share this post


Link to post
Share on other sites
let's say it's a 4x4 grid

----
----
----
----

----
-X--
----
----

----
-XO-
----
----

----
-XO-
--X-
----

----
-XO-
--X-
---O

X---
-XO-
--X-
---O

i'm saying that even in a 4x4 grid whoever moves first still gets their 3 X's or 3 O's in a row. once you figure out how to solve your current problem then come up with a basic formula that relates grid size to how many pieces in a row.

you may also find that you won't need anymore than 4 or 5 in a row, or else games will last forever or games will always end in a tie.

again, solve your current problem first, worry about this later. the number of pieces in a row is simply one variable you have to change.

Share this post


Link to post
Share on other sites
Quote:
Original post by Qudeid
But abotu Alpha-Beta-pruning. Since my grid size is variable, I thought that adding even one layer (4 by 4) extends the amount of possible moves a good deal. At least mathematically.

Oh, it does. But computers these days are ridiculously fast. Even without alpha-beta pruning, you'll likely get more than acceptable results up to 5x5 or 6x6. For larger boards, you can always add alpha-beta in later.

Share this post


Link to post
Share on other sites
Quote:
Original post by Qudeid
Actually, it seems like I'm totally blocked in my head now, because I can't solve the problem of determining who wins... Theoretically is it easy, 3 of X or O in a row column or diagonally. As with AI in the old version this was easy because I knew every single way of how one can win, this time it isn't the case, obviously.

Determining wins in tic-tac-toe isn't difficult, just annoying. Count consecutive Xes in each row; count consecutive Xes in each column; count consecutive Xes in each diagonal. Do the same for Os.

Share this post


Link to post
Share on other sites
I solved the victory problem a little differently than you suggested.
Actually as I previously described, but without needing the exception catching.

I just made sure, that the border isn't checked so that the vector might be out of range. And it works nicely!

Quite funny, the former victory function of the static grid was 30 lines and just checked each of the eight possibilities. Now it is dynamic and it is almost the exact same quantity of lines. :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by Qudeid
Actually, it seems like I'm totally blocked in my head now, because I can't solve the problem of determining who wins... Theoretically is it easy, 3 of X or O in a row column or diagonally. As with AI in the old version this was easy because I knew every single way of how one can win, this time it isn't the case, obviously.

Determining wins in tic-tac-toe isn't difficult, just annoying. Count consecutive Xes in each row; count consecutive Xes in each column; count consecutive Xes in each diagonal. Do the same for Os.


Actually, just checking the row, column & diagonals of the last move will be fine...

Share this post


Link to post
Share on other sites
Quote:
Original post by Atridas
Actually, just checking the row, column & diagonals of the last move will be fine...
Isn't that great? It's one of the best examples of "solve the right problem" that everyone falls prey to once in a while. That should be in a freakin' text book or something. Or a hiring exam. It's so obvious that a lot of people shoot from the hip and miss.

Share this post


Link to post
Share on other sites
Hi there,

back again.
The "victory check" is up and running.

I've now done some to the AI, but the problem I am experiencing is... well the AI just puts its marker on 0/0... that's it.. each and everytime, even overriding my own choice :-/

And using the debugger is quite a bit... difficult to do, especially to follow this many steps down etc.


Oh oh oh.. stop.. Update!
It now doesn't override anymore and it doesn't set its marker only on 0/0. But unfortunately it just goes like this

0/0, 1/0, 2/0... etc.
If that way is "blocked" it will just jump to the next free position

Another Update...
I've gotten so far that it tries to win, only problem is... it wants to win, no matter what.

[Edited by - Qudeid on February 19, 2008 5:17:58 PM]

Share this post


Link to post
Share on other sites
When debugging recursion like this, work backwards from the endgame. Start with a board with only one space available, just as a sanity check. Then try a board with two spaces available: one should be a win, the other should be a draw. See if it chooses the win space. Then try a board with two spaces available: one should lead to a draw, the other should lead to a loss. Starting from an empty board is not going to be a useful way to debug.

Share this post


Link to post
Share on other sites
big thanks to you, Sneftel!
I think I've got it now. It doesn't place its marker in the middle, if it is available (for example in the beginning when the computer begins.) but beside that, it is quite cool.

About performance, the first move takes quite some time to calculate. Not super much time, but still noticable, very noticable. I will either try Alpha Beta, or I just implement a depth. But that's another story.

Thanky ou very much for your help!

Share this post


Link to post
Share on other sites

This topic is 3581 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this