在 Nim 游戏中构建树

Question

我想创建一个像 Nim 这样的游戏。

玩家可以取走 1 或 M（定义）个方块，取走最后一个方块的玩家获胜。我还将创建一个 minimax 函数，因此 MAX 玩家（总是先玩）会做出最好的举动。我开始编写我的程序，但我在创建树游戏时遇到了问题。这是我的代码：

#define M 30
#define K 4

char player[3] = "MAX";
int cubesCounter = M;

struct Node {
    int value;
    int numCubes;
    struct Node *left;
    struct Node *right;
};

char switchPlayer() {
    if (strcmp(player, "MAX") == 0) {
        strcpy(player, "MIN");
    } else {
        strcpy(player, "MAX");
    }
}

struct Node buildGameTree() {
    struct Node *cube;
    cube->numCubes = M;

    cube->left = NULL;
    cube->right = NULL;

    if (cube->numCubes >= 1) {
        cube->numCubes = cube->numCubes - 1;
        cube->left = buildGameTree();
    }

    if (cube->numCubes >= M) {
        cube->numCubes = cube->numCubes - M;
        cube->right = buildGameTree();
    }
}

我在这些行中遇到错误，我无法弄清楚出了什么问题：

cube->left = buildGameTree();
cube->right = buildGameTree();

谁能帮我实现这个功能？

Answer 1

您的 buildGameTree 应该是：

struct Node *buildGameTree(){
    struct Node *cube= calloc(1,sizeof(struct Node));
    cube->numCubes = M;

    cube->left = NULL;
    cube->right = NULL;

    if (cube->numCubes >= 1){
        cube->numCubes = cube->numCubes - 1;
        cube->left = buildGameTree();
    }
    if (cube->numCubes >= M){
        cube->numCubes = cube->numCubes - M;
        cube->right = buildGameTree();
    }
    return (cube);
}

即：

为立方体分配内存；
return函数末尾分配的立方体。

关于此函数的用途仍有一些疑问，因为它不接收任何参数。由于 cube->numCubes 总是 M，所以 if (cube->numCubes >= 1).

会无限递归

Answer 2

我更改了代码，现在是：

struct Node *buildGameTree(int ncubes){
    struct Node *cube = calloc(1, sizeof(struct Node));
    cube->cubesRemaining = ncubes;

    if (cube->cubesRemaining >= 1){
        cube->left = buildGameTree(ncubes - 1);
        switchPlayer();
    }
    if (cube->cubesRemaining >= M){
        cube->right = buildGameTree(ncubes - M);
        switchPlayer();
    }

    return (cube);
}

编译代码我没有遇到错误问题。当我完成我的程序时，我会测试这个。

在 Nim 游戏中构建树

Building tree in Nim game

c

tree

artificial-intelligence

minimax