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;
}