6
\$\begingroup\$

Does anyone have tips to improve the speed, clarity and accuracy of this non-recursive alpha-beta algorithm? It's my first program written in C.

// Tic-Tac-Toe - Iterative implementation of alpha beta tree search.

// Built with Microsoft Visual Studio Professional 2013.

#include "stdafx.h"
#include <windows.h>
#include <intrin.h>
#include <stdint.h>


#define INFINITY 9999
#define NO_MOVE 9
#define NO_EVAL 2
#define X 1
#define O -1
#define Empty 0


struct values
{
    int nodeMove;
    int nodeEval;
    int alpha;
    int beta;
    int player;
    int board[9];
};


struct values moves[9];


int bestMove;


int board_eval(int *b)
{
    // Rows.
    if (b[0] && b[0] == b[1] && b[1] == b[2]) return b[0];
    if (b[3] && b[3] == b[4] && b[4] == b[5]) return b[3];
    if (b[6] && b[6] == b[7] && b[7] == b[8]) return b[6];

    // Cols.
    if (b[0] && b[0] == b[3] && b[3] == b[6]) return b[0];
    if (b[1] && b[1] == b[4] && b[4] == b[7]) return b[1];
    if (b[2] && b[2] == b[5] && b[5] == b[8]) return b[2];

    // Center is empty.
    if (!b[4]) return 0;

    // Diags.
    if (b[0] == b[4] && b[4] == b[8]) return b[0];
    if (b[2] == b[4] && b[4] == b[6]) return b[2];

    return 0;
}


void displayboard(int depth)
{
    const char *t = "O X";

    printf("\n\t %c | %c | %c\t\t 0 | 1 | 2\n", t[moves[depth].board[0] + 1], t[moves[depth].board[1] + 1], t[moves[depth].board[2] + 1]);
    printf("\t---|---|---\t\t---|---|---\n");
    printf("\t %c | %c | %c\t\t 3 | 4 | 5\n", t[moves[depth].board[3] + 1], t[moves[depth].board[4] + 1], t[moves[depth].board[5] + 1]);
    printf("\t---|---|---\t\t---|---|---\n");
    printf("\t %c | %c | %c\t\t 6 | 7 | 8\n\n", t[moves[depth].board[6] + 1], t[moves[depth].board[7] + 1], t[moves[depth].board[8] + 1]);
}


int find_move(int *board_arr, int nodeMove)
{
    int i;

    // Speedup loop using nodeMove instead of 0.
    for (i = nodeMove; i < 9; i++) {
        if (board_arr[i] == Empty)
            return i;
    }

    return NO_MOVE;
}


int move_up_tree(int depth)
{
    depth--;

    if (depth == 0 && (moves[depth + 1].nodeEval > moves[depth].nodeEval))
    {
        bestMove = moves[depth].nodeMove;
    }

    if (moves[depth].player == X)
    {
        moves[depth].nodeEval = max(moves[depth].nodeEval, moves[depth + 1].nodeEval);
        moves[depth].alpha = max(moves[depth].alpha, moves[depth].nodeEval);
    }
    else
    {
        moves[depth].nodeEval = min(moves[depth].nodeEval, moves[depth + 1].nodeEval);
        moves[depth].beta = min(moves[depth].beta, moves[depth].nodeEval);
    }

    moves[depth].nodeMove++;
    moves[depth].nodeMove = find_move(moves[depth].board, moves[depth].nodeMove);

    return depth;
}


int move_down_tree(int depth)
{
    int eval, move;

    depth++;

    moves[depth] = moves[depth - 1];

    if (moves[depth].player == X)
    {
        moves[depth].board[moves[depth].nodeMove] = X;
        moves[depth].player = O;
        moves[depth].nodeEval = INFINITY;
    }
    else
    {
        moves[depth].board[moves[depth].nodeMove] = O;
        moves[depth].player = X;
        moves[depth].nodeEval = -INFINITY;
    }

    eval = board_eval(moves[depth].board);
    move = find_move(moves[depth].board, 0);

    //  Leaf node.
    if (eval || (move == NO_MOVE))
    {
        moves[depth].nodeEval = eval;
        moves[depth].nodeMove = NO_MOVE;
    }
    else
    {
        moves[depth].nodeMove = move;
    }

    return depth;
}


void computer_move()
{
    int depth = 0;
    uint64_t c1, c2;

    moves[0].nodeMove = find_move(moves[0].board, 0);
    moves[0].nodeEval = -INFINITY;
    moves[0].alpha = -INFINITY;
    moves[0].beta = INFINITY;
    moves[0].player = X;

    if (moves[0].nodeMove != NO_MOVE)
    {
        c1 = __rdtsc();

        while (TRUE)
        {
            if (moves[depth].nodeMove == NO_MOVE)
            {
                if (depth == 0) break;

                depth = move_up_tree(depth);
            }
            else if (moves[depth].alpha >= moves[depth].beta)
            {
                moves[depth].nodeMove = NO_MOVE;
            }
            else
            {
                depth = move_down_tree(depth);
            }
        }

        c2 = __rdtsc();

        moves[0].board[bestMove] = X;

        printf("Thinking Cycles......: %d\n", c2 - c1);
        printf("Computer : %d\n", bestMove);
    }
}


void init_board()
{
    moves[0].board[0] = Empty;
    moves[0].board[1] = Empty;
    moves[0].board[2] = Empty;
    moves[0].board[3] = Empty;
    moves[0].board[4] = Empty;
    moves[0].board[5] = Empty;
    moves[0].board[6] = Empty;
    moves[0].board[7] = Empty;
    moves[0].board[8] = Empty;
}


void human_move()
{
    int move;
    char *p, s[100];

    printf("Your move: ");
    while (fgets(s, sizeof(s), stdin)) {
        move = strtol(s, &p, 10);
        if (p == s || *p != '\n') {
            printf("Your move: ");
        }
        else break;
    }

    moves[0].board[move] = O;
}


int main(int argc, char **argv)
{
    init_board();
    displayboard(0);

    while (1)
    {
        human_move();
        computer_move();
        displayboard(0);

        if (board_eval(moves[0].board))
        {
            printf("Computer Wins! (-_-)\n");
            init_board();
            displayboard(0);
        }
        else if (find_move(moves[0].board, 0) == NO_MOVE)
        {
            printf("A draw! (*_*)\n");
            init_board();
            displayboard(0);
        }
    }

    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

Here are a few suggestions:

Add static to the declaration of bestMove and all functions but main(). This might allow your compiler to inline a few functions as it is a good rule to not export what doesn't need to be exported.

Rename Emtpy to EMTPY in order to keep consistency.

In board_eval() use loops for row and cols. This makes checking the code easier and the compiler will unroll the loops anyway, thus there is no performance lost.

Add comments. Use these to document what the functions do and what the return values mean.

\$\endgroup\$
  • \$\begingroup\$ Added most of your suggestions and the speed has increased. :) To further speed it up - in the WHILE loop, the code calls these functions: move_up_tree(); move_down_tree(); Is there a way to inline them without having to cut N paste the code in? \$\endgroup\$ – vengy Oct 8 '15 at 11:53
  • \$\begingroup\$ Is there a way to re-write board_eval(int *b) to make it faster? It's called each time a tree node is generated. Any speedup here would definitely help! \$\endgroup\$ – vengy Oct 8 '15 at 12:07
  • \$\begingroup\$ If you have declared your functions static, it is likely the compiler inlines them already when optimization is enabled. There are less than 20000 possible states. One way to speed-up board_eval (possibly) would be to hard code all those states in a table and then lookup the result rather than compute it. \$\endgroup\$ – Erwan Legrand Oct 14 '15 at 8:34
0
\$\begingroup\$

Faster board eval

This is in response to your question of how to make board_eval() faster. You can use a trick where you add the three values in a row and then check to see if the sum is either -3 or 3. So your function would look like this:

static int board_eval(const int *b)
{
    int sum;

    // Rows and columns.
    for (int colStart=0, rowStart=0; colStart<3; colStart++, rowStart += 3) {
        sum = b[rowStart] + b[rowStart+1] + b[rowStart+2];
        if (sum == 3 || sum == -3)
            return sum;
        sum = b[colStart] + b[colStart+3] + b[colStart+6];
        if (sum == 3 || sum == -3)
            return sum;
    }

    // Diagonals.
    sum = b[0] + b[4] + b[8];
    if (sum == 3 || sum == -3)
        return sum;
    sum = b[2] + b[4] + b[6];
    if (sum == 3 || sum == -3)
        return sum;
    return 0;
}

Note that this function returns -3 and 3 instead of -1 and 1, but it doesn't make a difference to your algorithm. I tested this on my machine it made your program about 30% faster, but your mileage may vary.

\$\endgroup\$
  • \$\begingroup\$ Wow ...nice ... I'll have to go thru code. It definitely is faster. I was able to speed things up too using a force inline as follows: __forceinline void move_down_tree() \$\endgroup\$ – vengy Oct 9 '15 at 0:42
  • \$\begingroup\$ With JS1 speed boost board eval: Your move: 8 Thinking Time......: 539984 Computer : 4 Using the slow version gave (release mode), the first human move to position 8 gave: Thinking Time......: 677924 \$\endgroup\$ – vengy Oct 9 '15 at 0:54
  • \$\begingroup\$ Is it better to assign a variable and use that multiple times instead of calculating it each time. For example, int myvar = moves[depth].nodeEval, moves[depth + 1].nodeEval , then use myvar! \$\endgroup\$ – vengy Oct 9 '15 at 1:06
  • \$\begingroup\$ @vengy A good compiler will probably optimize that for you. But it can't hurt to try it in case your compiler doesn't. \$\endgroup\$ – JS1 Oct 9 '15 at 2:10
  • \$\begingroup\$ I tried using just inline, but the disassembly shows it still did a CALL to the subroutine. Forcing it, the code was inserted inline. Also, I think the board eval could be enhanced using some bit twiddling tricks? maybe a !(sum%3) to test for a multiple of 3 etc.,...instead of the || (or) checks. \$\endgroup\$ – vengy Oct 9 '15 at 2:15
0
\$\begingroup\$

Thanks for the help...the final program is below. Please compare this to the original code to see the evolution of changes to improve the speed as suggested/proposed by the peer reviewers. It's a definite improvement! Thanks.

// Tic-Tac-Toe - Iterative implementation of alpha beta tree search.

// Built with Microsoft Visual Studio Professional 2013.

#include "stdafx.h"
#include <windows.h>
#include <intrin.h>
#include <stdint.h>


#define INFINITY 9999 // Arbitrary value to indicate worst position.
#define NO_MOVE 9     // Flag to indicate no moves available.
#define X 1           // Computer Player
#define O -1          // Human Player
#define EMPTY 0       // Empty board square


struct values
{
    int nodeMove;
    int nodeEval;
    int alpha;
    int beta;
    int player;
    int board[9];
    int moveList[10];
};


// Define the board positions.
struct values moves[9];


// Tracks the current best move for the computer.
static int bestMove;


// Used to indicate the tree depth.
static int depth;


// Fast version - suggested by JS1

static int board_eval(const int *b)
{
    int sum;

    // Rows and columns.
    for (int colStart = 0, rowStart = 0; colStart<3; colStart++, rowStart += 3) {
        sum = b[rowStart] + b[rowStart + 1] + b[rowStart + 2];
        if (sum == 3 || sum == -3)
            return sum;
        sum = b[colStart] + b[colStart + 3] + b[colStart + 6];
        if (sum == 3 || sum == -3)
            return sum;
    }

    // Diagonals.
    sum = b[0] + b[4] + b[8];
    if (sum == 3 || sum == -3)
        return sum;
    sum = b[2] + b[4] + b[6];
    if (sum == 3 || sum == -3)
        return sum;

    return 0;
}


void displayboard(int depth)
{
    const char *t = "O X";

    printf("\n\t %c | %c | %c\t\t 0 | 1 | 2\n", t[moves[depth].board[0] + 1], t[moves[depth].board[1] + 1], t[moves[depth].board[2] + 1]);
    printf("\t---|---|---\t\t---|---|---\n");
    printf("\t %c | %c | %c\t\t 3 | 4 | 5\n", t[moves[depth].board[3] + 1], t[moves[depth].board[4] + 1], t[moves[depth].board[5] + 1]);
    printf("\t---|---|---\t\t---|---|---\n");
    printf("\t %c | %c | %c\t\t 6 | 7 | 8\n\n", t[moves[depth].board[6] + 1], t[moves[depth].board[7] + 1], t[moves[depth].board[8] + 1]);
}


// Generate a list of valid moves from the current board position...

void find_moves(values *moves)
{
    int moveIndex = 0;

    for (int i = 0; i < 9; i++)
    {
        if (moves->board[i] == EMPTY)
        {
            moves->moveList[moveIndex++] = i;
        }
    }

    // To indicate the end of the move list, mark it with NO_MOVE.
    moves->moveList[moveIndex] = NO_MOVE;
}


__forceinline void move_up_tree()
{
    // Decrement the tree depth (a.k.a ply level)
    depth--;

    // If this is a root node (depth=0) and there is a better move found, then update "bestMove".
    if (depth == 0 && (moves[depth + 1].nodeEval > moves[depth].nodeEval))
    {
        bestMove = moves[depth].moveList[moves[depth].nodeMove];
    }

    // Player X is trying to maximize the board evaluation.
    if (moves[depth].player == X)
    {
        moves[depth].nodeEval = max(moves[depth].nodeEval, moves[depth + 1].nodeEval);
        moves[depth].alpha = max(moves[depth].alpha, moves[depth].nodeEval);
    }
    // Player O is trying to minimize the board evaluation.
    else
    {
        moves[depth].nodeEval = min(moves[depth].nodeEval, moves[depth + 1].nodeEval);
        moves[depth].beta = min(moves[depth].beta, moves[depth].nodeEval);
    }

    // Explore the next move...
    moves[depth].nodeMove++;
}


__forceinline void move_down_tree()
{
    static int eval;

    // Increment the tree depth (a.k.a ply level)
    depth++;

    // Copy the parent node values to the child.
    moves[depth] = moves[depth - 1];

    if (moves[depth].player == X)
    {
        // Make the X move on the child board.
        moves[depth].board[moves[depth].moveList[moves[depth].nodeMove]] = X;

        // Players O turn to move.
        moves[depth].player = O;

        // Set initial evaluation to the worst possible value (INFINITY),
        // since player O is trying to minimize the board evaluation,
        // its score can only get better.
        moves[depth].nodeEval = INFINITY;
    }
    else
    {
        // Make the O move on the child board.
        moves[depth].board[moves[depth].moveList[moves[depth].nodeMove]] = O;

        // Players X turn to move.
        moves[depth].player = X;

        // Set initial evaluation to the worst possible value (-INFINITY),
        // since player X is trying to maximize the board evaluation,
        // its score can only get better.
        moves[depth].nodeEval = -INFINITY;
    }

    // Calculate board evaluation...
    eval = board_eval(moves[depth].board);

    // Start at initial move.
    moves[depth].nodeMove = 0;

    //  Check leaf node win.
    if (eval)       
    {
        moves[depth].nodeEval = eval;
        moves[depth].moveList[0] = NO_MOVE;
    }
    else
    {
        find_moves(&moves[depth]);

        //  Check leaf node draw.
        if (moves[depth].moveList[0] == NO_MOVE)
        {
            moves[depth].nodeEval = eval;
        }
    }
}


void computer_move()
{
    static uint64_t c1, c2;

    depth = 0;

    find_moves(&moves[0]);

    moves[0].nodeMove = 0;
    moves[0].nodeEval = -INFINITY;
    moves[0].alpha = -INFINITY;
    moves[0].beta = INFINITY;
    moves[0].player = X;

    if (moves[0].moveList[moves[0].nodeMove] != NO_MOVE)
    {
        c1 = __rdtsc();

        while (TRUE)
        {
            if (moves[depth].moveList[moves[depth].nodeMove] == NO_MOVE)
            {
                if (depth == 0) break;

                move_up_tree();
            }
            else if (moves[depth].alpha >= moves[depth].beta)
            {
                // AlphaBeta pruning. No further move exploration needed from this tree node.  
                moves[depth].nodeMove = 0;
                moves[depth].moveList[moves[depth].nodeMove] = NO_MOVE;
            }
            else
            {
                move_down_tree();
            }
        }

        c2 = __rdtsc();

        // Make the best move the computer has found.
        moves[0].board[bestMove] = X;

        printf("Thinking Time......: %d\n", c2 - c1);
        printf("Computer : %d\n", bestMove);
    }
}


void init_board()
{
    moves[0].board[0] = EMPTY;
    moves[0].board[1] = EMPTY;
    moves[0].board[2] = EMPTY;
    moves[0].board[3] = EMPTY;
    moves[0].board[4] = EMPTY;
    moves[0].board[5] = EMPTY;
    moves[0].board[6] = EMPTY;
    moves[0].board[7] = EMPTY;
    moves[0].board[8] = EMPTY;
}


void human_move()
{
    int move;
    char *p, s[100];

    printf("Your move: ");
    while (fgets(s, sizeof(s), stdin)) {
        move = strtol(s, &p, 10);
        if (p == s || *p != '\n') {
            printf("Your move: ");
        }
        else break;
    }

    // Make human board move.
    moves[0].board[move] = O;
}


int main(int argc, char **argv)
{
    init_board();
    displayboard(0);

    while (1)
    {
        human_move();
        computer_move();
        displayboard(0);

        find_moves(&moves[0]);

        if (board_eval(moves[0].board))
        {
            printf("Computer Wins! (-_-)\n");
            init_board();
            displayboard(0);
        }
        else if (moves[0].moveList[0] == NO_MOVE)
        {
            printf("A draw! (*_*)\n");
            init_board();
            displayboard(0);
        }
    }

    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.