CODEWITHSUNDEEP
calgorithmgomoku
omfg
omfg

Reputation: 55

Method for obtaining speed up on computer decision in C

I'm trying to figure out the algorithms to play Gomoku(5 by 5 version of tictactoe) with computers. In this case, I found that the most commonly used algorithms are Min-max(or Alpha-beta) but these are too hard for me to handles.. So I decided to use following codes which are quite easy to understand but time consuming. It shows how a computers make its reasonable choice.

//------------------------------------------------------------
// computer_move() checks for all legal moves in the current  |
// position. then for each of them it calls the dfs_search()  |
// function to get the moves' score. And finally it returns   |
// the move with the best score.                              |
//------------------------------------------------------------

int computer_move()  //
{
    int best_move;  // best move so far
    int best_score = -100;  // best score so far 
    int score;  // current score
    int i;

    for (i = 0; i < 16; ++i) { //
        if (pos[i] == EMPTY) {  // if a legal move can be made 
            pos[i] = COMPUTER;  // mark the move
            score = -dfs_search(HUMAN); // 
            pos[i] = EMPTY; // take back the move

            if (score > best_score) {
                best_score = score;
                best_move = i;
            }
        }
    }

    printf("Computer's move: %d\n", best_move);
    return best_move;   // return the best move found
}


//------------------------------------------------------------
// dfs_search() gets the side to move, find all legal moves   |
// for him, and for each move, it recursively calls itself.   |
// It returns a score for the position.                       |
// This recursive function continues on each variation until  |
// the game's end is found in that variation. Which means     |
// that the variation continues until check_result() returns  |
// a value other than CONTINUE.                                   |
// Note that this can be done in tic-tac-toe, since it's a    |
// deterministic game. For games like chess or checkers we    |
// can't continue the variation until reaching the game's end |
// so we have to cut the variation at some point.             |
//------------------------------------------------------------

int dfs_search(int player) // 
{
    int best_score = -100;
    int score;
    int result;
    int i;

    result = check_result(player);
    if (result != CONTINUE) return result;  // return the result

    for (i = 0; i < 16; ++i) {
        if (pos[i] == EMPTY) {
            pos[i] = player;
            score = -dfs_search(CHANGE_PLAYER(player)); // 
            pos[i] = EMPTY;

            if (score > best_score)
                best_score = score;
        }
    }

    return best_score;  // return the best score
}

For 3 by 3 matrix, it works pretty well. For 4 by 4, however, it takes too long to leave a next stone. Since the reason of long time consuming is the first three or four decisions, I thought that just making the computer to search for best points only around the human's last choice(point) would be a solution. After the first three or four decisions, above formal algorithm will work well for the few remaining points. How do you think about it? And give some advices to modify the current algorithm.

Upvotes: 1

Views: 127

Answers (1)

Imran
Imran

Reputation: 13468

You are trying to solve the entire game tree. On a 3x3 board there are 9! = 362880 nodes in the tree, which is small enough for your computer to handle, however on a 4x4 board there are 16! = 20922789888000 (20.9 trillion) nodes, which is too many to visit in a reasonable amount of time.

Consider implementing a search algorithm that can return a reasonable estimate of the current position's score without solving the entire game tree. For GoMoku I recommend Monte Carlo Tree Search. It has been successfully applied to many games such as Go, and in its vanilla form it doesn't require you to write a static evaluation function as required for fixed depth min-max search and its variants such as alpha-beta.

Upvotes: 0

Related Questions