Tic Tac Toe with Minimax Algorithm

[louisdinh]

I wrote the tic tac toe with minimax algorithm. However, there are some bugs that i cannot figure out why the computer cannot win the human. Please help me to fix it. Thanks.

I upload a zip of all files for you to check it easier. I guarantee that it doesn't contain virus.

http://www.mediafire.com/?9t3q7ae3pkn7n7k

Thanks for helping

/*
 * File:   Board.h
 * Author: louisdinh
 *
 * Created on July 27, 2010, 1:56 AM
 */

#ifndef _BOARD_H
#define	_BOARD_H

class Board {
public:
    char board[9];
    Board();
    virtual ~Board();
    // display the current board
    void display_board();
    // update the current board position
    void update_board(int pos, char symbol);
    // get the current board


};

#endif	/* _BOARD_H */

/*
 * File:   Board.cpp
 * Author: louisdinh
 *
 * Created on July 27, 2010, 1:56 AM
 */

#include "Board.h"
#include <iostream>
#include "Controller.h"
using namespace std;
Board::Board() {
    // Initialise the game board so all positions hold the value *.
    for (int i = 0; i < 9; i++) {
        board[i] = '\0';
    }
}

Board::~Board() {
}

void Board::display_board() {
    cout << std::endl;
    cout << " " << board[0] << " | " << board[1] << " | " << board[2] << endl;
    cout << "-----------" << std::endl;
    cout << " " << board[3] << " | " << board[4] << " | " << board[5] << endl;
    cout << "-----------" << std::endl;
    cout << " " << board[6] << " | " << board[7] << " | " << board[8] << endl;
    cout << endl;
}

void Board::update_board(int pos,char symbol) {
    board[pos] = symbol;
}

/*
 * File:   Player.h
 * Author: louisdinh
 *
 * Created on July 27, 2010, 2:02 AM
 */

#ifndef _PLAYER_H
#define	_PLAYER_H
#include <iostream>
using namespace std;

class Player {
public:

    // Player Class Constructor.
    Player() {}
    Player(string name, char symbol) : playerName(name), playerSymbol(symbol),win(false) {}

    // Get the player number

    char getPlayerSymbol() {
        return playerSymbol;
    }

    // Get the players name.

    string getPlayerName() {
        return playerName;
    };

    // player is win or not

    bool is_win() {
        return win;
    }

    // set win for player

    void setWin(bool sWin) {
        win = sWin;
    }

    // player is turn or not

    bool is_turn() {
        return isTurn;
    }

    // set win for player

    void setTurn(bool sTurn) {
        isTurn = sTurn;
    }

    // Get the player's board position choice and place the players marker on the game board.
    // deconstructs into two standard (col/row) gameboard positions (0-2)(0-2),
    void set_move(int pos ) {

        move = pos;

    }



    int get_move() { return move;}

private:

    string playerName; // The name of the player.
    char playerSymbol; // the player number
    bool win;
    bool isTurn;

    int move;

};

#endif	/* _PLAYER_H */

/*
 * File:   Human.h
 * Author: louisdinh
 *
 * Created on July 27, 2010, 2:03 AM
 */

#ifndef _HUMAN_H
#define	_HUMAN_H
#include "Player.h"

class Human : public Player {
public:
    Human(){}
    Human(std::string name, char symbol = 'X') : Player(name, symbol) {}

    // ---------------------------------------------------------------
    // Name: ask move()
    // Desc: Prompt the player to enter gameboard location choice.
    //---------------------------------------------------------------

    int ask_move();

};

#endif	/* _HUMAN_H */

/*
 * File:   Human.cpp
 * Author: louisdinh
 *
 * Created on July 27, 2010, 2:03 AM
 */

#include "Human.h"
#include <iostream>

using namespace std;

int Human::ask_move() {
    int pos = -1;
    cout << "Which position (1-9) do you want to take, " << getPlayerName() << "? ";
    cin >> pos;

    if(!cin.good()) {

        cin.clear();

        cin.sync();

    }
    pos--;
    return pos;
}

/*
 * File:   Computer.h
 * Author: louisdinh
 *
 * Created on July 27, 2010, 2:08 AM
 */

#ifndef _COMPUTER_H
#define	_COMPUTER_H
#include <iostream>
#include "Player.h"
class Computer : public Player {
public:
    Computer(){}
    Computer(std::string name, char symbol = 'O') : Player(name, symbol) {
    }
};

#endif	/* _COMPUTER_H */

#ifndef _CONTROLLER_H_
#define _CONTROLLER_H_

#include "Board.h"
#include "Computer.h"
#include "Human.h"
class Controller {

    public:
        enum {
            START, PLAYING, QUIT, OWIN, XWIN, DRAW
        } state;
        Controller() {}
        Controller(Human _player,Computer _comp) {
            player = _player;
            comp = _comp;
            gameboard.display_board();
            state = PLAYING;
        }
        void update();
        void make_move(); // gets move for the current player
        bool verify_move(int pos);                 // verifies if the current move is legal
        void find_winner();                 // this function finds the winner once the agme has ended
        void display_result();		    // display the final result of the game on the screen
        void check_game_state(char _board[]); // check game state
        int evaluate_position(char _board[], char playerSymbol);  // evaluates the current board position
        int get_state() { return state;}
    private:
        Human player;
        Computer comp;
        Board gameboard;
        char current_symbol;

};


#endif // CONTROLLER_H_INCLUDED

#include <iostream>
#include "Controller.h"
#include "Minimax.h"
using namespace std;

void Controller::make_move()
{
    if (player.is_turn()) {
        int pos = player.ask_move();
        while (!verify_move(pos)) {
            pos = player.ask_move();
        }
        gameboard.update_board(pos,player.getPlayerSymbol());
        current_symbol = player.getPlayerSymbol();
        player.setTurn(false);
        comp.setTurn(true);
    } else {
        Minimax minimax;
        int pos = minimax.MiniMax(gameboard.board);
        cout << "Computer move" << pos << endl;
        gameboard.update_board(pos,comp.getPlayerSymbol());
        current_symbol = comp.getPlayerSymbol();
        comp.setTurn(false);
        player.setTurn(true);
    }
    state = PLAYING;
}

//---------------------------------------------------------------
// Name: verify move
// Desc: Checks to make sure the choice is empty and valid,
//       e.g. within the range of 0 and 9
//       and does not allready contain a O or X.
//---------------------------------------------------------------
bool Controller::verify_move(int pos)
{
    if (gameboard.board[pos] != '\0' || (pos < 0) || (pos > 9)) {
        cout << "Invalid move" << endl;
        return false;
    }
    return true;
}

void Controller::check_game_state(char _board[]) {

    if ((_board[0] == current_symbol && _board[1] == current_symbol && _board[2] == current_symbol) ||
		(_board[3] == current_symbol && _board[4] == current_symbol && _board[5] == current_symbol) ||
		(_board[6] == current_symbol && _board[7] == current_symbol && _board[8] == current_symbol) ||
		(_board[0] == current_symbol && _board[3] == current_symbol && _board[6] == current_symbol) ||
		(_board[1] == current_symbol && _board[4] == current_symbol && _board[7] == current_symbol) ||
		(_board[2] == current_symbol && _board[5] == current_symbol && _board[8] == current_symbol) ||
		(_board[0] == current_symbol && _board[4] == current_symbol && _board[8] == current_symbol) ||
		(_board[2] == current_symbol && _board[4] == current_symbol && _board[6] == current_symbol))
	{
        if (current_symbol == 'X')
        {
            state = XWIN;
        }
        else if (current_symbol == 'O')
        {
            state = OWIN;
        }
	}
	else
	{
	    // Check to see if there are positions available on the _board
	    state = DRAW;
		for(int i = 0; i < 9; ++i) {
			if(_board[i] == 0) {
				state = PLAYING;
				break;
			}
		}
	}
}

void Controller::find_winner(){
    if (state == XWIN) {
        player.setWin(true);
    } else if (state == OWIN) {
        comp.setWin(true);
    }
}

void Controller::display_result() {
    if(player.is_win()) {
		cout << player.getPlayerName() << " has won the game!" << endl;
	} else if(comp.is_win()) {
		cout << comp.getPlayerName() << " has won the game!" << endl;
	} else {
		cout << "no winner, this game is a draw." << endl;
	}
	state = QUIT;
}

void Controller::update() {
    gameboard.display_board();
    check_game_state(gameboard.board);
}

/*
 * File:   Minimax.h
 * Author: louisdinh
 *
 * Created on July 27, 2010, 4:47 AM
 */

#ifndef _MINIMAX_H
#define	_MINIMAX_H

#include <list>
#include <stdlib.h>
#include "Controller.h"
class Minimax {
public:
    // evaluates the current board position
    Minimax(){}
    std::list<int> generate_moves(char _board[]);

    int evaluate_board(char _board[]);
    int MiniMax(char _board[]);
    int MinMove(char _board[]);
    int MaxMove(char _board[]);
private:
    static const int INFINITY = 10000;
    Controller control;
};

#endif	/* _MINIMAX_H */

/*
 * File:   Minimax.cpp

 * Author: louisdin*

 * Created on July 27, 2010, 4:47 AM
 */


#include "Minimax.h"

#include "Controller.h"

#include <vector>


// generates all the possible moves for the current board position


list<int> Minimax::generate_moves(char _board[]) {
    std::list<int> list;
   
	for (int i = 0; i < 9; ++i) {
   
		if (_board[i] == 0) {
        
			list.push_back(i);
       
		}
   
	}
	return list;

}

int Minimax::evaluate_board(char _board[]) {
    char symbol ='*';
    if ((_board[0] == _board[1] || _board[1] == _board[2]) && (_board[1] != '\0')) {
        symbol = _board[1];
    }
    if (((_board[3] == _board[4] || _board[4] == _board[5]) && (_board[4] != '\0')) ||
    ((_board[1] == _board[4] || _board[4] == _board[7]) && (_board[4] != '\0')) ||
    ((_board[0] == _board[4] || _board[4] == _board[8]) && (_board[4] != '\0')) ||
    ((_board[2] == _board[4] || _board[4] == _board[6]) && (_board[4] != '\0'))) {
        symbol = _board[4];
    }
    if ((_board[6] == _board[7] || _board[7] == _board[8]) && (_board[7] != '\0')) {
        symbol = _board[7];
    }
    if ((_board[0] == _board[3] || _board[3] == _board[6]) && (_board[3] != '\0')) {
        symbol = _board[3];
    }
    if ((_board[2] == _board[5] || _board[5] == _board[8]) && (_board[5] != '\0')) {
        symbol = _board[5];
    }
    if (symbol == 'X')
    {
        return INFINITY;
    }
    else if (symbol == 'O')
    {
        return -INFINITY;
	}
	else
	{
	    return 0;
	}
//    control.check_game_state(_board);
//    int nGameState = control.get_state();
//    //cout << "State: " << nGameState << endl;
//	if(nGameState == control.OWIN) return -INFINITY;
//	if(nGameState == control.XWIN) return INFINITY;
//	if(nGameState == control.DRAW) return 0;
    return -1;  //still playing
}

// returns best move for the current computer player
int Minimax::MiniMax(char _board[])
{
    int index = 0;
	int nBestScore = -INFINITY;  //stores the best score evaluated, initially set to the value associated with a human player win
	vector<int> nBestMoves; //list to store the moves yielding the nBestScore;

    list<int> nValidMoves;
	nValidMoves = generate_moves(_board); //valid moves for the board

	while(!(nValidMoves.empty())) //we're going to loop over all of the valid moves
	{
	    _board[nValidMoves.front()] = 'O'; //set the square associated with the first valid move to the computer's piece
		int nScore = MinMove(_board);  //call the int Min(board) function which ultimately will return a score based on the final board state
		if(nScore > nBestScore)
		{
			nBestScore = nScore;  //the score becomes our new best score
			nBestMoves.clear(); //we have a new best score, so our best moves are no longer the best, get rid of them
			nBestMoves.push_back(nValidMoves.front());  //add the move to the best moves container
		}
		else if (nScore == nBestScore)
		{
			nBestMoves.push_back(nValidMoves.front());  //add the move to the best moves container
		}
		_board[nValidMoves.front()] = 0; //return the square to its original state
		nValidMoves.pop_front();  //we're finally done with the move, discard it
	}

	index = nBestMoves.size();
	cout << "Index" << index << endl;
    if (index > 0) {
        index = rand() % index;
   }
	return (nBestMoves[index]);  //choose a random move from your best moves to add some variety
}

int Minimax::MinMove(char _board[])
{
	int nMoveScore = evaluate_board(_board);
	if(!(nMoveScore == -1))  return nMoveScore;  //if we're not still playing, the game is over so return the score;

	int nBestScore = INFINITY;  //Min is from the player's perspective, from which LARGE_INT represents a loss
	list<int> nValidMoves;
	nValidMoves = generate_moves(_board);

	while(!(nValidMoves.empty()))
	{
		_board[nValidMoves.front()] = 'X';  //set the square to the player piece

		int nScore = MaxMove(_board);  //we've made a move, so evaluate the board from the other player's perspective

		if(nScore < nBestScore) //if we found a better move for the human player
		{
			nBestScore = nScore;
		}
		_board[nValidMoves.front()] = 0;  //reset the square;
		nValidMoves.pop_front();
	}

	return nBestScore;
}

int Minimax::MaxMove(char _board[])
{
	int nMoveScore = evaluate_board(_board);
	if(!(nMoveScore == -1))  return nMoveScore;  //if we're not still playing, the game is over so return the score;

	int nBestScore = -INFINITY;  //Min is from the player's perspective, from which LARGE_INT represents a loss
	list<int> nValidMoves;
	nValidMoves = generate_moves(_board);

	while(!(nValidMoves.empty()))
	{
		_board[nValidMoves.front()] = 'O';  //set the square to the computer piece
		int nScore = MinMove(_board);  //we've made a move, so evaluate the board from the other player's perspective

		if(nScore > nBestScore) //if we found a better move for the human player
		{
			nBestScore = nScore;
		}
		_board[nValidMoves.front()] = 0;  //reset the square;
		nValidMoves.pop_front();
	}

	return nBestScore;
}

/*
 * File:   main.cpp
 * Author: louisdinh
 *
 * Created on July 27, 2010, 1:55 AM
 */


#include "Human.h"

#include "Computer.h"

#include "Controller.h"
#include <iostream>

using namespace std;

int main() {
    cout << endl;
    cout << "****************************" << endl;
    cout << "* TIC TAC TOE WITH MINIMAX *" << endl;
    cout << "****************************" << endl;
    string name;
    cout << endl;
    cout << "Please enter your name: ";
    cin >> name;
    Human player(name);
    Computer comp("COMPUTER");
    Controller control(player,comp);
    while (control.get_state() != control.QUIT) {
        while(control.get_state() == control.PLAYING) {
            control.make_move();
            control.update();
        }
        if (control.get_state()  == control.XWIN || control.get_state()  == control.OWIN || control.get_state()  == control.DRAW) {
            control.find_winner();
            control.display_result();
        }
    }
    return 0;
}

[Ancient Dragon]

computer won for me but I had to sort of force it to win. It appears to first check if it needs to block before it checks to see if it can win. Maybe you need to reverse those two checks. (I didn't look at the code, I just compiled and ran it)

I had to add #include <string> in each of the *.cpp files because my compiler, vc++ 2010 express, doesn't add it by default. Otherwise there were no other compiler errors or warnings -- Good Job :)

[louisdinh]

the computer only wins when we don't want to win. i check the game state in evaluation board method which was call in minmove and max move. i don't understand why it doesn't block the player :-s