数字游戏程序

Question

我尝试为 this question 编写 C++ 程序。我假设所有玩家都玩得很好，而且程序也玩得很好来对抗它。我尝试使用递归（通过在每一步将问题减少为 2 个较小的问题）。 'final state' 给出的值告诉您是赢 (1) 还是输 (0)。我的代码有什么问题，因为手动计算出的解决方案会给出不同的结果。

#include<iostream>
using namespace std;

bool win(int player,int no_of_players,int counter)
{
    if(no_of_players==1)
        return 1;
    if(counter>=10)
    {
        --no_of_players;
        counter=0;
    }
    if(player>no_of_players)
        player=0;
    if(win(player+1,no_of_players,counter+1)==0)
    {
        cout<<"\nMove 1";
        return 1;
    }
    if(win(player+1,no_of_players,counter+2)==0)
    {
        cout<<"\nMove 2";
        return 1;
    }
    cout<<"\nLosing position";
    return 0;
}

int main()
{
    int a=win(0,2,1);
    cout<<"\nFinal state :"<<a;
    return 0;
}

Answer 1

你的方法有很多问题。

主要是因为这不是简单的两人最小-最大，你不能简单地 return 一个分数，递归。对于给定玩家的每次比赛，您必须 return 每个玩家将获得的分数。类似于：

void scores(int currentPlayer, int toWrite, int outScores[], int nbOut)

请问return所有玩家的得分在outScores，如果currentPlayer要写一两个数，从toWrite，nbOut 名玩家已经出局。

不过，这并不是最佳选择。递归地尝试 10 个玩家的所有解决方案意味着向下超过 50 个级别，分支因子为 2。你需要一些动态规划来使其高效。

我编码了。它适用于 4 名玩家，最大值为 10。对于更多玩家来说它变得非常慢。正如我所说，动态规划正是您在这里寻找的。

此外，我假设玩家宁愿只玩一次，如果它仍然会以相同的顺序输掉。

#include <memory.h>
#include <vector>
#include <iostream>
using namespace std;

const int NB_PLAYERS = 3;
const int MAX_VALUE = 10;

vector<pair<int, int>> scores(int currentPlayer, int toWrite, int outScores[], int nbOut)
{
    if (outScores[currentPlayer] == -1) // we're already out, lets just have the next player play
    {
        return scores((currentPlayer + 1) % NB_PLAYERS, toWrite, outScores, nbOut);
    }

    if (toWrite == MAX_VALUE) // one player is out
    {
        vector<pair<int, int>> ret;
        if (nbOut + 2 != NB_PLAYERS)
        {
            outScores[currentPlayer] = -1; // so the game can continue without us
            ret = scores((currentPlayer + 1) % NB_PLAYERS, 1, outScores, nbOut + 1);
        }
        else
        {
            for(int i=0; i < NB_PLAYERS; i++)
            {
                if (outScores[i] == 0)
                {
                    outScores[i] = NB_PLAYERS; // set the winner
                }
            }
        }
        outScores[currentPlayer] = nbOut + 1;
        ret.push_back(pair<int, int>(1,currentPlayer));
        return ret;
    }

    if (toWrite + 1 == MAX_VALUE) // no point playing to lose, if we can avoid it
    {
        vector<pair<int, int>> ret;
        ret = scores((currentPlayer + 1) % NB_PLAYERS, toWrite + 1, outScores, nbOut);
        ret.push_back(pair<int,int>(1,currentPlayer));
        return ret;
    }

    int scoresIfPlay1[NB_PLAYERS];
    int scoresIfPlay2[NB_PLAYERS];
    vector<pair<int,int>> ret1;
    vector<pair<int,int>> ret2;

    memcpy(scoresIfPlay1, outScores, sizeof(int) * NB_PLAYERS);
    memcpy(scoresIfPlay2, outScores, sizeof(int) * NB_PLAYERS);

    ret1 = scores((currentPlayer + 1) % NB_PLAYERS, toWrite + 1, scoresIfPlay1, nbOut); //recurse with both choices
    ret2 = scores((currentPlayer + 1) % NB_PLAYERS, toWrite + 2, scoresIfPlay2, nbOut);

    if (scoresIfPlay2[currentPlayer] > scoresIfPlay1[currentPlayer]) // pick the solution that yields the higher score
    {
        memcpy(outScores, scoresIfPlay2, sizeof(int) * NB_PLAYERS);
        ret2.push_back(pair<int,int>(2,currentPlayer));
        return ret2;
    }
    else
    {
        memcpy(outScores, scoresIfPlay1, sizeof(int) * NB_PLAYERS);
        ret1.push_back(pair<int,int>(1,currentPlayer));
        return ret1;
    }
}

int main()
{
    int outScores[NB_PLAYERS] = {0};

    vector<pair<int, int>> plays = scores(0, 1, outScores, 0);

    for(int i = 0; i < NB_PLAYERS; i++)
    {
        cout << "Player " << i << " has score " << outScores[i] << endl;
    }
    cout << endl;

    cout << "Plays were: " << endl;
    for(int i = plays.size() - 1; i >= 0; --i)
    {
        cout << "player " << plays[i].second << " plays " << plays[i].first << " times." << endl;
    }

}

===旧答案===

如前所述，这个问题不允许你判断你是赢还是输。为此，您必须以一种或另一种方式更改规则：由于将有 9 名输家和 1 名赢家，任何未获胜的玩家都可以改变他们的比赛方式，并且在他们仍然输的同时影响谁获胜。例如。玩家 x 输掉任何一种方式，但可以使玩家 y 获胜或失败。 x 将如何播放未定义。

您需要选择一个场景：

每个玩家都会尽可能快地消灭所有其他玩家，只要这不会让他们输掉。
或者，稍后被淘汰会获得更多积分。玩家将最大化他们的分数。

无论如何，解决方案应该比上面更复杂。您可能想要递归

int scoreFromPosition(int player,int no_of_players,int counter)

当 no_of_player 玩家剩余时，return 玩家玩家可以获得的最高分数，与柜台目前正在柜台。

Answer 2

正如 Jeffrey 所指出的，这个游戏不能超过两个玩家来解决。所以我的理解是现在的问题是为什么你的程序对两个玩家不起作用。

你的双人游戏逻辑中最大的问题是你误解了 counter 的值。 counter 在您的代码中的有效含义是玩家现在需要写入的值（也可以选择在那之后写入 counter + 1 ）。所以你正确地假设如果 counter >= 10，那么玩家输了，尽管你处理它的方式可能不正确。如果 counter 大于或等于 10.

，那么我会做的是，因为我们在这里谈论的是双人游戏，所以我会立即 return 0

现在讨论主要问题 -- 调用递归函数的方式。第一次调用是正确的

if(win(player+1,no_of_players,counter+1)==0)

你将它传递给另一个玩家（顺便说一句，你没有以任何方式使用 player 变量，所以我只是将它从代码中完全删除），写 counter董事会，这时候我们知道 counter 不是 10，所以写它是安全的。

然而，你的第二次调用是错误的。

if(win(player+1,no_of_players,counter+2)==0)

在这里，在将 counter 和 counter + 1 都写在棋盘上之后，您有效地将回合传递给下一个玩家。但是等等，如果 counter + 1 是 10 怎么办？你需要这样称呼它：

if(counter + 1 < 10 && win(player+1,no_of_players,counter+2)==0)

换句话说，如果第二轮会打印 10，甚至不要考虑转两轮。

最后，您考虑的最后一个问题是，如果您将程序称为 win(1, 2, 1) 和 win(2, 2, 1)，您的程序将 return 不同的值。您没有使用变量 player，因此它不能 return 不同的值。您的 win 函数并没有说明序号为 player 的玩家是否获胜，而是说当前玩家是否获胜。所以为了测试它是否真的有效，改变初始值 counter 更有意义，模拟第一个玩家的不同回合，看看 return 值如何变化。例如，第一个玩家输了，所以 win(1, 2, 1) 是 0，无论第一个玩家转什么回合，第二个玩家都赢了，所以 win(2, 2, 2) 和 win(2, 2, 3) 是 1.

这是它的样子。我只对您的代码做了两处更改：如果 counter 为 10，则立即将其设为 return 0，并更改了如上所述进行第二次递归调用的方式。我没有删除 player 和 no_of_players 变量，但它们不再真正在代码中使用了：

#include<iostream>
using namespace std;

bool win(int player,int no_of_players,int counter)
{
    if(no_of_players==1)
        return 1;
    if(counter>=10)
    {
        return 0;
    }
    if(player>no_of_players)
        player=0;
    if(win(player+1,no_of_players,counter+1)==0)
    {
        cout<<"\nMove 1";
        return 1;
    }
    if(counter + 1 < 10 && win(player+1,no_of_players,counter+2)==0)
    {
        cout<<"\nMove 2";
        return 1;
    }
    cout<<"\nLosing position";
    return 0;
}

int main()
{
    int a=win(0,2,1);
    cout<<"\nFinal state :"<<a<<endl;
    return 0;
}

数字游戏程序

Program for number game

c++

algorithm

recursion

logic