Help with Minimax Alpha-Beta pruning

Can somebody please take a look at my code???

Page 1 of 1

1 Replies - 1076 Views - Last Post: 10 October 2010 - 05:16 PM Rate Topic: -----

#1 SymphonyX   User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • Posts: 27
  • Joined: 05-March 09

Help with Minimax Alpha-Beta pruning

Posted 10 October 2010 - 11:39 AM

Hey everyone,
I'm trying to make tic-tac-toe game using alpha-beta pruning, but whenever I run my code and it is the pc's turn I go into an infinite loop or something like that (not sure what it is tho).
If somebody could take a look at the code and help me figure out what Im doing wrong I would really appreciate it.
//Board to evaluate.
// 1 for playerO, 0 for empty, -1 for playerX
#define PLAYER_O			1
#define PLAYER_X			-1
#define EMPTY				0
#define TOTAL_CHILD_NODES	9
#define DRAW				0
#define MAX_DEPTH			9


struct Node {
	int board [9];
};

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

int current_depth = 0;
Node *current_board = new Node();

//lines to be checked//
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}
					};
int gameOver = 0;

//Game over?//
int checkPlayerWin(int player, Node *board)
{
	
	int count = 0;
	for(int i = 0; i < 8; ++i) {
		for(int j = 0; j < 3; ++j) {
			if(board->board[lines[i][j]] == player)
				count++;
			if(count == 3) {
				return player;
				gameOver = 1;
			}
			
		}
	count = 0;
	}
	
	return 0;
}

//Empty cells in board?//
int checkBoard(Node *board)
{
	for(int i =0; i < 9; ++i)
		if(board->board[i] == EMPTY) return EMPTY;

	return 1; 
	
}

//Make next move//
//Compute a score for current configuration//
int makeMove(int player, Node *new_board)
{
	int score, max=0;;
	for(int i=0; i < 9; ++i)
		if(new_board->board[i] == EMPTY) {
			new_board->board[i]=player;
		}
	
		for(int j=0; j < 8; ++j) {
			score = 1;
			for(int h=0; h < 3; ++h) {
				if(new_board->board[lines[j][h]] == player) 
					score *= 10;
				else if(new_board->board[lines[j][h]] == -player)
					score = 0;
				else
					score *= 1;
			}
			if(score >= max)
				max = score;
			
		}
		return max;
}


//Evaluate current score for each of the players//

//evaluates human move and returns a score//
//sets current board to the board last analyzed//
int evaluateHumanMove(Node *board, int depth, int alpha, int beta)
{
	int value;
	Node* new_board = new Node();
	int min=10001;
	int evaluateComputerMove(Node *, int, int, int);

	if(checkPlayerWin(PLAYER_O, board) == 1) return 10000;
	for(int i=0; i < TOTAL_CHILD_NODES-depth; ++i) {
		if(checkBoard(board) == EMPTY) {
			new_board = board;
			value = makeMove(PLAYER_X, new_board); 
			evaluateComputerMove(new_board, depth+1, alpha, beta);
			if(value < min) {
				min = value;
			}
			if(value < beta) beta = value;
			if(alpha >= beta) return beta;
		}
		if(min == 10001)
			return DRAW;
	}
	
	current_board = board;
	return min;
}

//evaluates computer move and returns a score//
//sets current board to the board last analyzed//
int evaluateComputerMove(Node *board, int depth, int alpha, int beta)
{
	int value;
	Node* new_board = new Node();
	int max = -10001;

	if(checkPlayerWin(PLAYER_X, board) == -1) return -10000;
	for(int i = 0; i < TOTAL_CHILD_NODES-depth; ++i){
		if(checkBoard(board) == EMPTY) {
			new_board = board;
			value = makeMove(PLAYER_O, new_board);
			evaluateHumanMove(new_board, depth+1, alpha, beta);
			if(value > max) {
				max = value;
				
			}
			if(value > alpha) alpha = value;
			if(alpha >= beta) return alpha;
		}
	}

	if(max == -10001) return DRAW;
	current_board = board;
	return max;
}


//Initialize alpha-beta algorithm//
//Computer player evaluate game tree, human player makes his move//
void AlphaBetaPruning(Node *board, int player, int depth)
{

	int move;
	while(gameOver==0){

	if(player==PLAYER_O) {
		evaluateHumanMove(board, depth, 0, 0);
		current_depth++;
		AlphaBetaPruning(current_board, PLAYER_X, current_depth);
	}
	else if(player == PLAYER_X) {
		cout << "enter position (0-8):\n";
		cin >> move;
		
		if(current_board->board[move] ==0) {
			current_board->board[move] = -1;
			current_depth++;
			
		}
		else {
			cout << "Invalid move, try again\n";
			AlphaBetaPruning(board, PLAYER_X, depth);
		}
		AlphaBetaPruning(current_board, PLAYER_O , current_depth++);	
	  }	
	}
}


int main()
{
	
	for(int i=0; i < 9; ++i)
	current_board->board[i] = 0;

	AlphaBetaPruning(current_board, -1, current_depth);
		

	

	return 0;

}



Thank you in advance
SymphonyX

This post has been edited by SymphonyX: 10 October 2010 - 11:40 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Help with Minimax Alpha-Beta pruning

#2 JackOfAllTrades   User is offline

  • Saucy!
  • member icon

Reputation: 6248
  • View blog
  • Posts: 24,015
  • Joined: 23-August 08

Re: Help with Minimax Alpha-Beta pruning

Posted 10 October 2010 - 05:16 PM

Duplicate topic closed. Refer to the topic in C/C++.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1