Negamax Alpha Beta search

I'm looking for help with implementing the Negamax Alpha-Beta search algorithm. My C isn't the best, but I've got a working framework for playing the game so far and I am having trouble with my Alpha-Beta search always returning what seems to be the last move found, rather than returning the best move found.

Below is my source file for my alpha beta search. If anyone can help I would greatly appreciate it. I'm not looking for anyone to "do my homework" as many people fear, as I am genuinely interested and I have implemented the search technique before in other languages.

Again any help would be greatly appreciated.

Best regards

#include "alphabeta.h"

struct tree_node * create_root(struct tree_node * root, struct Position *pos) 
{
    root = (struct tree_node*) malloc(sizeof(struct tree_node));
    root->pos = copy(pos);
    root->first_child = NULL;
    root->next_sibling = NULL;
    root->best_move = NULL;

    return root;
}

struct tree_node * create_node(struct tree_node *node) 
{
    struct tree_node *new_node = (struct tree_node*) malloc(sizeof(struct tree_node));
    new_node->pos = copy(node->pos);
    new_node->first_child = NULL;
    new_node->next_sibling = NULL;
    new_node->best_move = NULL;

    return new_node;
}

struct tree_node * add_child(struct tree_node *parent) 
{
    if (parent->first_child == NULL) 
    {
        parent->first_child = create_node(parent);
        return parent;
    }

    // Loop through the list of existing
    // children for the next gap
    struct tree_node *ptr = NULL;
    ptr = parent->first_child;
    while (ptr->next_sibling != NULL) 
    {
        ptr = ptr->next_sibling;
    }

    // create the new child and append to the list
    ptr->next_sibling = create_node(parent);
    return ptr;
}

struct tree_node * destroy_tree(struct tree_node * root) 
{
    if (root->first_child != NULL) 
    {
        destroy_tree(root->first_child);
    }

    // loop through the siblings and delete
    struct tree_node *ptr = root->next_sibling;
    struct tree_node *ptr2 = root;
    while (ptr != NULL) 
    {
        free(ptr2);
        ptr2 = ptr;
        ptr = ptr->next_sibling;
    }

    return root;
}

int negamax(struct tree_node *node, int color, int *num_static,
        int *num_cutoff, int height, int achievable, int hope) 
{
    printf("Called negamaxn");

    // first costruct the list of moves
    struct move_list *list = NULL;
    list = moves(color, node->pos, list);
    int num_moves = size_of_list(list);

    int best_score = NEG_INF;

    if (height == 0 || num_moves == 0) 
    {
        *num_static = *num_static + 1;
        return static_evaluator(node->pos, color, num_moves);
    }
    else 
    {
        int temp = 0;
        while (list != NULL) 
        {
            // Make the new move
            struct tree_node *new_node;
            //new_node = add_child(node);
            new_node = create_root(new_node, node->pos);
            make_move(new_node->pos, list->move);

            print_board(new_node->pos);

            list = list->prev;

            // Recurse over alpha beta
            temp = -negamax(new_node, color, num_static,
                    num_cutoff, height - 1,
                    -hope, -achievable);

            destroy(new_node->pos);
            free(new_node);
            //destroy_node(new_node);
            //new_node = NULL;

            //printf("Returned from the recursive calln");
            // set the new best move
            /*
                if (temp > achievable) 
                {
                    best_score = temp;
                    node->best_move = list->move;
                    printf("Best move: %sn", node->best_move->str_rep);
                }
            */

            if (temp >= hope) 
            {
                *num_cutoff = *num_cutoff + 1;
                return temp;
            }

            // set to the max value
            if (achievable <= temp) 
            {
                node->best_move = list->move;
                printf("Best move: %sn", node->best_move->str_rep);
                achievable = temp;
            }
        }
    }

    return achievable;
}

/*
 * This is my evaluation function. The parameters
 * to the function are the attributes of the position;
 * The guard count, the king count and the number of
 * moves available. I chose to weight the parameters
 * offering the highest weight to the number of moves
 *
 * If there are no moves available, I decided to remove
 * points from the function. It will never go below zero,
 * but this should permit it to give an extremely low
 * value for positions which have no available moves
*/
int static_evaluator(struct Position *pos, int color, int num_moves) 
{
    int evaluation = 1;

    // Calculate the value, while applying
    // weights to the parameters
    switch (color) 
    {
        case BLACK_COL:
            if (num_moves == 0) 
            {
                evaluation += 1;
                if (pos->num_black_kings > 0) 
                {
                    evaluation += pos->num_black_kings - 1;
                }
            }
            else 
            {
                evaluation += num_moves * 3;
                evaluation += pos->num_black_kings * 2;
                evaluation -= pos->num_white_kings * 2;
            }
            // Always count the guards
            evaluation += pos->num_black_guards;
            evaluation -= pos->num_white_guards;
            break;

        case WHITE_COL:
            if (num_moves == 0) 
            {
                evaluation += 1;
                if (pos->num_white_kings > 0) 
                {
                    evaluation += pos->num_white_kings - 1;
                }
            }
            else 
            {
                evaluation += num_moves * 3;
                evaluation += pos->num_white_kings * 2;
                evaluation -= pos->num_black_kings * 2;
            }
            evaluation += pos->num_white_guards;
            evaluation -= pos->num_black_guards;
            break;
    }

    return evaluation;
}

链接地址: http://www.djcxy.com/p/9628.html

上一篇: 如何将主要变体搜索与negamax一起使用跳棋游戏？

下一篇: Negamax Alpha Beta搜索