AI in a dynamic Tic-Tac-Toe Game

Google for "min-max". That should be everything you need.

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?

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}

i hope that as your grid size gets bigger the number of spaces in a row increases also. otherwise the first person to move wins every time.

@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"?

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.

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.

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.

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

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...

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.

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]

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.

d'oh...
sounds more than sane (while you were talking about sanity).

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!