## Another tic-tac-toe game

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### Another tic-tac-toe game

Hi!

I'm trying to create a tic-tac-toe game. I have some questions rearding the algorithm.

I've decided to evalute the whole tree since it have will less than 9! leafs (360 000) which isn't that much.

This mean's that I will not have an evalute-function to check how good my parent position is.

So, I've been thinking. What should decide how good a tree is?
After some thinking I came up with this.

My code would work like this:

The leafs would return 1 (win), 0 or -1.
AX would then be set to a value which describes how good this path is.

A1 would be set to:
number_of_wins/(number_of_wins+number_of_loss) = 1/(1+0) = 1.

A2 would be set to:
number_of_wins/(number_of_wins+number_of_loss) = 2/(1+2) = 2/3.

A3 would be set to:
number_of_wins/(number_of_wins+number_of_loss) = since we have no wins I use this code

[syntax="cpp"]if (number_of_wins == 0 && number_of_loss >0)
return -10.0;
else if ((number_of_wins == 0 && number_of_loss == 0)
return 0.5;[/syntax]
A3 would therefor be set to -10.0

This makes A1 most attractive.

A problem with this thinking is that if we havetwo nodes with three leafs each. One of the nodes contains only wins and the other contains 1 win + 2 draws. This makes them equal good.

Please, give me a helping hand here.
Last edited by Safari on Tue Nov 22, 2005 12:29 pm, edited 1 time in total.

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

All other tree nodes can be set to -1, 0, or 1, just like the leaves. Think along the lines of winning and losing positions. A 'winning' position is a position where, if you use a perfect strategy, you can beat your opponent no matter what moves he makes. A 'losing' position is a position where, if your opponent plays perfectly, you will lose no matter what moves you make. Anything else is a 'drawing' position.

To calculate the node values, simply check if the node corresponds to the AI's turn. If it is, set its value to the maximum of its children (since the AI can always choose the best move from the moves available); otherwise, set it to the minimum of its children.

Beer Hunter

Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

You should read GameDev.net 's tutorial on the minimax algorithm; this is obviously what you need here.

t i l e x

Posts: 3604
Joined: Wed Dec 03, 2003 3:59 pm

I'll try to implement that.

edit: wait! Do ytou mean that if the human plays perfect the computer actually can loose? I thought there where tic-tac-toes that absolutely couldn't loose.

When I encounter a leaf that will lead to loss, I'll then kill the move that would lead to that possability.

Like this:

The computer makes a move that leads to B. From B, the human player can make the move to the red rectangle which is a symbol for his win/our loss. So instead I kill that patch

After killing all bad patches, I'll then calculate how many win/draw-leafs a patch will give me. The one with the biggest number will be my next move.

But, what if a the next move makes the computer (1) win. And another (2) move leads to a big tree.
Clearly (2) will have more winning possibilities than (1). So instead of just checking number of possible win-leafs I will check this (in this order)

1. This move makes the computer win: Then do it
2. This move make the computer loose: Don't make it
3. Check number of win-leafs and go with the one that have the highest rate.

Ofcours this makes the computer offensive. I could also choose a defensive tactic = go with the route that has less number of loss-leafs. This will not be hard to change.

How does this sound?

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

You seem like you have your wits about you when it comes to trees/searching, so would you like to see my tic-tac-toe engine code? It is very short and very easy to understand. I can post it here if you like... ?
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

One thing I would love to do is to play against it. And maybe hook it into mine and check 1000 games (or so) and see what happens. I allways thought one could make unbreakable tic-tac-toes. And I'm not only talking in practice but also in theory.

I hope you haven't done any windows app. since I'm under FBSD (since I don't have wine I don't know another way of running .exe-files).

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

Safari wrote:One thing I would love to do is to play against it. And maybe hook it into mine and check 1000 games (or so) and see what happens. I allways thought one could make unbreakable tic-tac-toes. And I'm not only talking in practice but also in theory.

I hope you haven't done any windows app. since I'm under FBSD (since I don't have wine I don't know another way of running .exe-files).

In theory, a player can only win at TTT if the other player makes a mistake (by not playing the best move). It is 100% impossible to win against this engine. Enter your moves in the format, x y, where x and y have limits 0 and 2 (0 0 would be the top-left square, etc.).

I hope you like it!

ttt.h
[syntax="cpp"]#ifndef _TTT_H_
#define _TTT_H_

enum Player {
O=1, X=2, empty=4
};

enum {
PLAYING=1, C_WIN=2, H_WIN=4, DRAW=8
};

//I use these values to detect
//if a side won on their turn.
static const int lines[8*3] = {
0,1,2, 3,4,5, 6,7,8, 0,3,6,
1,4,7, 2,5,8, 0,4,8, 2,4,6
};

struct Board {
//the game board is stored
//as an array of 9 elements.
Player board[9];

Board() {
for(int i=0;i<9;++i)
board[i]=empty;
}

bool check_for_win(Player p) {
for(int i=1,d=0;i<=24;++i) {
if(board[lines[i-1]]&p) {
if(!(++d%3))
return true;
} else d=0;
if(!(i%3))
d=0;
} return false;
}

//this function is used by `minimax()' to
//determine the current state of play.
int state() {
if(check_for_win(X))
return C_WIN; //computer won!
if(check_for_win(O))
return H_WIN; //human won!
for(int i=0;i<9;++i)
if(board[i]&empty)
return PLAYING;
return DRAW;
}

//this function is what kicks off the
//tree generating process.
int think(int depth,Player p) {
int best=-100,m;

for(int i=0;i<9;++i) {
if(board[i]&empty) {
board[i]=p;
int val=-minimax(depth-1,p&O?X:O);
board[i]=empty;
if(val>best) {
best=val;
m=i;
}
}
}

return m;
}

//this is the tree generating function.
//it is very similiar to `think()' by
//definition, but it is different enough
//that it is best to keep them seperate.
int minimax(int depth,Player p) {
switch(state()) {
case C_WIN:
return p&O?-100:+100;
case H_WIN:
return p&O?+100:-100;
case DRAW:
return 0;
}

if(depth<=0)
return 0;

int best=-100;

for(int i=0;i<9;++i) {
if(board[i]&empty) {
board[i]=p;
int val=-minimax(depth-1,p&O?X:O);
board[i]=empty;
if(val>best)
best=val;
}
}

return best;
}
};

#endif[/syntax]

main.cpp
[syntax="cpp"]#include "ttt.h"
#include <cstdio>

void printBoard(Board const &b) {
for(int i=0;i<9;++i) {
printf("%c "," OX -"[b.board[i]]);
if(!((i+1)%3))
putchar('\n');
}
}

int main() {
printf("Tic Tac Toe - by Tom Cant\n\n");

Board b; //everything happens from here
int h_x,h_y; //human move information

while(b.state()&PLAYING) {
printBoard(b);
scanf("%d %d",&h_x,&h_y);
if(h_x>=0 && h_x<=2 && h_y>=0 && h_y<=2) {
if(b.board[h_x*3+h_y]&empty) {
b.board[h_x*3+h_y]=O;
printf("\n");
if(b.state()&PLAYING)
b.board[b.think(7,X)]=X;
} else printf("\nInvalid move!\n");
} else printf("\nInvalid move!\n");
printf("\n");
}

//print the final game position
printBoard(b);
getchar();
getchar();
}[/syntax]
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Am I blind or what? Why doesn't it work? Mine looks almost like that

[syntax="cpp"]void bestMove (Player ** players, int computer) {
int best = -2;
int x = 0, y = 0;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (!emptySpot(players, j, i))
continue;
players [computer] -> addPiece (j, i);
int chance = -winChance(players, computer, int(!computer));
undoMove (players, computer, j, i);
if (chance > best) {
best = chance;
x = j;
y = i;
}
}
}
players [computer] -> addPiece (x, y);
}

int winChance (Player ** players, int computer, int turn) {
int node_value = (turn == computer ? -1: 1);
if (hasWon (players [computer])) { //compuer wins
return 1;
}
if (hasWon (players [int(!computer)])) { // human wins
return -1;
}
if (~(players [0] -> getBoard() | players [1] -> getBoard())) { //checks if there's still empty spots left
for (int j = 1; j <= 3; j++) {
for (int i = 1; i <= 3; i++) {
if (!emptySpot(players, j, i))
continue;
players [turn] -> addPiece (j, i);
int data = -winChance (players, computer, int(!turn));
undoMove (players, turn, j, i);
if (turn == computer && data > node_value)
node_value = data;
else if (turn != computer && data < node_value)
node_value = data;
}
}
}
else {
return 0; //draw
}
return node_value;
}[/syntax]

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

If you post your complete code I will make it work for you... (I will try, anyway!).

: I just noticed a problem. Take a look at this:
Code: Select all
`if (turn == computer && data > node_value)   node_value = data; else if (turn != computer && data < node_value)   node_value = data;`

That is an un-necessary bit of code. If you did this, then you wouldn't need to negate the return value in `bestMove()'. Replace it with this:
Code: Select all
`if(data>node_value)  node_value=data;`

I am not saying this will make it all work, as there could well be other problems, but I am in college at the moment, so theres not a lot more I can do right now.

Post your code anyway, and I'll take a look.
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Here comes my code. (it's a bit messy)

board.cpp

[syntax="cpp"]# include "board.h"
# include <iostream>

Board :: Board () {
board = 0;
}

int Board :: at (int x, int y) {
return (board & (1<<(5-x)<<5*(3-y)));
}

void Board :: clear () {
board = 0;
}

void Board :: add (int x, int y) {
board |= (1<<(5-x)<<5*(3-y));
}

void Board :: remove (int x, int y) {
board &= ~(1<<(5-x)<<5*(3-y));
}
[/syntax]

board.h
[syntax="cpp"]#ifndef BOARD_H_
#define BOARD_H_

class Board {
private :
int board;
public :
Board ();
int at (int, int);
void clear ();
void add (int, int);
void remove (int, int);
int getBoard () { return board; }
};
#endif

[/syntax]

player.cpp

[syntax="cpp"]# include "player.h"
# include <iostream>

Player :: Player () {
board = new Board ();
}

void Player :: addPiece (int x, int y) {
board -> add (y, x);
}

void Player :: removePiece (int x, int y) {
board -> remove (y, x);
}

bool Player :: hasPiece (int x, int y) {
return board -> at (y, x) != 0;
}

void Player :: clear () {
delete board;
board = new Board ();
}

Player :: ~Player () {
delete board;
}
[/syntax]

player.h
[syntax="cpp"]# ifndef PLAYER_H_
# define PLAYER_H_
# include "board.h"

class Player {
private:
Board * board;
public:
Player ();
void addPiece (int, int);
void removePiece(int, int);
bool hasPiece (int, int);
int getBoard () { return board -> getBoard (); }
void clear ();
~Player ();
};
# endif
[/syntax]

tictactoe.cpp

[syntax="cpp"]# include <iostream>
# include <string>
# include <exception>
# include <cstdio>
# include <stdexcept>
# include "board.h"
# include "player.h"

bool hasWon (Player *);
void printBoard (Player **);
bool emptySpot (Player **, int, int);
void resetGame (Player **);
void bestMove (Player **, int);
void undoMove (Player **, int, int, int);
int winChance (Player **, int, int);
bool computerPlay (Player ** players, int turn);
bool humanPlay (Player ** players, int turn);
int evalute (Player **, int);

int main () {
Player * players[2];
players [0] = new Player ();
players [1] = new Player ();

std :: cout << "Enter \"1\" to become player 1: ";
int numOfemptySlots = 9;
int n, turn = 1;
std :: cin >> n;
if (n != 1)
turn = 0;
bool cont = true;
while (true) {
std :: cout << "Enter: (q = quit) (xy)" << std :: endl;
if (!cont)
break;
if (numOfemptySlots == 0) {
std :: string n;
std :: cout << "Game Over. It was a Tie! Enter: (q = quit) (else: a new game will be started)";
std :: cin >> n;
if (n == "q")
break;
resetGame(players);
numOfemptySlots = 9;
}
if (turn == 0)
cont = humanPlay (players, 0);
else
cont = computerPlay (players, 1);
system ("clear");
printBoard (players);

if (hasWon (players [turn])) {
std :: cout << "You " << (turn == 0 ? "win!" : "loose!");
std :: cout << " Press q to quit (or start a new game): ";
std :: string n;
getline (std :: cin, n);
if (n == "q")
break;
resetGame(players);
turn = 0;
numOfemptySlots = 9;
continue;
}
numOfemptySlots--;
turn ^= 1;
}
delete players[0];
delete players[1];
return 0;
}

bool computerPlay (Player ** players, int turn) {
bestMove (players, turn);
//players [turn] -> addPiece (move/10, move%10);
return true;
}

bool humanPlay (Player ** players, int turn) {
std :: string input;
int x, y;
std :: cin >> input;
if (input == "q")
return false;
x = atoi (input.substr(0,1).c_str());
y = atoi (input.substr(1).c_str());
//A non-empty spot was entered
if (!emptySpot(players, y, x)) {
while (!emptySpot(players, x, y)) {
std :: cout << "Enter an empty spot: ";
std :: cin >> input;
if (input == "q")
return false;
x = atoi (input.substr(0,1).c_str());
y = atoi (input.substr(1).c_str());
}
}
players [turn] -> addPiece (x, y);
return true;
}

//Checks if a player has won
bool hasWon (Player * p) {
int v = p -> getBoard (), l = p -> getBoard (), d1 = p -> getBoard (), d2 = p -> getBoard ();
v &= v << 1; v &= v << 1;
l &= l << 5; l &= l << 5;
d1 &= d1 << 4; d1 &= d1 << 4;
d2 &= d2 << 6; d2 &= d2 << 6;
return (v | l | d1 | d2) != 0;
}

//Writes the board
void printBoard (Player ** players) {
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
std :: cout << " XO"[int(players [0] ->hasPiece(j,i)) + 2*int(players [1] ->hasPiece(j,i))] << " | ";
}
std :: cout << std :: endl;
}

}

//Checks a spot and returns true if it's empty
bool emptySpot (Player ** players, int x, int y) {
return (players [0] -> hasPiece(x,y) != true && players [1] -> hasPiece(x, y) != true);
}

void resetGame (Player ** players) {
players [0] -> clear ();
players [1] -> clear ();
}

void bestMove (Player ** players, int computer) {
int best = -2;
int x = 0, y = 0;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (!emptySpot(players, j, i))
continue;
players [computer] -> addPiece (j, i);
int chance = -winChance(players, computer, int(!computer));
undoMove (players, computer, j, i);
if (chance > best) {
best = chance;
x = j;
y = i;
}
}
}
players [computer] -> addPiece (x, y);
}

void undoMove (Player ** players, int player, int x, int y) {
players [player] -> removePiece (x, y);
}

int winChance (Player ** players, int computer, int turn) {
int node_value = (turn == computer ? -1: 1);
if (hasWon (players [computer])) { //compuer wins
return 1;
}
if (hasWon (players [int(!computer)])) { // human wins
return -1;
}
if (~(players [0] -> getBoard() | players [1] -> getBoard())) { //checks if there's still empty spots left
for (int j = 1; j <= 3; j++) {
for (int i = 1; i <= 3; i++) {
if (!emptySpot(players, j, i))
continue;
players [turn] -> addPiece (j, i);
int data = -winChance (players, computer, int(!turn));
undoMove (players, turn, j, i);
if (data > node_value)
node_value = data;
/*else if (turn != computer && data < node_value)
node_value = data;*/
}
}
}
else {
return 0; //draw
}
return node_value;
}

[/syntax]

You enter "xy"

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

This one is smarter, I think. Well, atleast it starts with the center square...

[syntax="cpp"]void bestMove (Player ** players, int computer) {
int best = 2;
int x = 0, y = 0;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (!emptySpot(players, j, i))
continue;
players [computer] -> addPiece (j, i);
int chance = winChance(players, computer, int(!computer));
undoMove (players, computer, j, i);
//std :: cout << chance << " ";
if (chance < best) {
best = chance;
x = j;
y = i;
}
}
}
/*std :: cin.get ();
std :: cin.get ();*/
players [computer] -> addPiece (x, y);
}

void undoMove (Player ** players, int player, int x, int y) {
players [player] -> removePiece (x, y);
}

int winChance (Player ** players, int computer, int turn) {
int node_value = (turn != computer ? -1: 1);
if (hasWon (players [computer])) { //compuer wins
return 1;
}
if (hasWon (players [int(!computer)])) { // human wins
return -1;
}
if (~(players [0] -> getBoard() | players [1] -> getBoard())) { //checks if there's still empty spots left
for (int j = 1; j <= 3; j++) {
for (int i = 1; i <= 3; i++) {
if (!emptySpot(players, j, i))
continue;
players [turn] -> addPiece (j, i);
int data = winChance (players, computer, int(!turn));
undoMove (players, turn, j, i);
if (turn == computer && data < node_value) {
node_value = data;
}
else if (turn != computer && data > node_value)
node_value = data;
}
}
}
else {
return 0; //draw
}
return node_value;
}[/syntax]

tomcant, I guess this

[syntax="cpp"]if (turn == computer && data > node_value)
node_value = data;
else if (turn != computer && data < node_value)
node_value = data;[/syntax]

is your version of

[syntax="cpp"]switch(state()) {
case C_WIN:
return p&O?-100:+100;
case H_WIN:
return p&O?+100:-100;
case DRAW:
return 0;
}[/syntax]

This is crazy.. I don't see the problem in the code

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

Anyone? I'm honestly not able to understand why it isn't working.

Everything is finished except the thing that made me try to make this gaim: learn how to search trees.

Safari

Posts: 1362
Joined: Sun Sep 19, 2004 11:07 am

Sorry Safari, I havn't had a lot of time just lately (I have a huge computing coursework project to do!).

I don't think it helps you to store each players pieces in two seperate objects. If you look at mine (above), I keep it very simple by using a single array to store the game position. If I were you, I would give that a go, since it makes the code easier to understand/maintain.
If it wasn't for C, we would be using BASI, PASAL and OBOL.

tomcant

Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Though checking for the probability of winning, taking a mean of the values or the like of the successor states is attractive, it's not good practice cause it'll force you to evaluate each node which will prevent you from using alpha-beta pruning - something that can cut your branching factor down to the square root, in the best case.

For adversial search in games, chess and the like especially:
http://www.seanet.com/~brucemo/topics/topics.htm

If you use the probability for winning, then if there's no win for one node, the prob should be 0, not -10.0.

For your later code, you should use the terms utility or the like instead of "winChance" - which it obviously isn't considering you have negative values.

int winChance (Player ** players, int computer, int turn) {
int node_value = (turn != computer ? -1: 1);
if (hasWon (players [computer])) { //compuer wins
return 1;
}
if (hasWon (players [int(!computer)])) { // human wins
return -1;
}

Why do you have Both a computer and a turn? It should simply be reduced to who has the iniative. Furthermore, I believe you should implement an Evaluation function (which is what 'winChance' here represents + a minimax search). A simple evaluation function, such as this, needs only one thing: the current state of the game. It should then return a value representing how it goes in the battle between the two sides, having one positive and one negative for say. The minimax will then Use the evaluation function to determine which side is the best, but only at leaf nodes.
It'll be a bit easier for you to use a negamax algorithm, since you don't have to separate the two players then. What it does is to consider the utility positive for the user with iniative, this includes negating the return of the evaluation function if you're the wrong player and switching the value when you pass it up to the ancestors. (read about it on the above mentioned page).

Your above mentioned winChance function seems a bit odd as, if it's the computer to move, he plays somewhere and then calls winChance again, sttill with the same value of computer, which means, if he has won, it will return 1.0. But the return is negated, making it ~1.0, so in this case, though i ahven't read it all, the computer will actually try to tplay bad.

Fuso

Posts: 19
Joined: Wed Jul 06, 2005 3:44 am
Location: Sweden