# Help with Minimax Alpha-Beta pruning

Page 1 of 1

## 1 Replies - 1076 Views - Last Post: 10 October 2010 - 05:16 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=194367&amp;s=578a99cd65319161080b4cdf9c651b78&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 SymphonyX

Reputation: -3
• 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;

}

```

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

• Saucy!

Reputation: 6248
• 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++.