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]

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