Negamax Alpha Beta搜索

我正在寻求实施Negamax Alpha-Beta搜索算法的帮助。 我的C并不是最好的，但是我已经有了一个工作框架来玩这款游戏，而且我的Alpha-Beta搜索一直在返回似乎是最后一招的问题，而不是返回最佳举措找到。

以下是我的alpha测试搜索源文件。 如果任何人都可以帮助，我将不胜感激。 我不是在寻找任何人“做我的作业”，因为很多人害怕，因为我真的很感兴趣，而且我已经用其他语言实施过搜索技术。

再次，任何帮助将不胜感激。

最好的祝福

#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/9627.html

上一篇: Negamax Alpha Beta search

下一篇: How do I center text horizontally and vertically in a TextView?