c++中带递归的减法计数下降到零博弈模式
使用递归，我必须为一个游戏做一个AI，其中计算机将从4，3或1中选择，并从1到99之间的给定数字中减去它。这个游戏将在人工智能和人类之间进行。然而，AI不能从4,3或1中选择任意的随机数，它必须总是选择有助于它赢得比赛的值。另外，当数字是2，AI或人类不能选择4或3，因为它大于2，所以他们必须选择1。同时假设AI是玩家2，人总是1。
例如:如果起始数n= 7，那么玩家1选择1和n=6，那么计算机选择4和新的n= 2。玩家1将选择1和n=1，然后AI将选择1和n= 0。因此AI赢得了这场比赛。
到目前为止，我对这个问题的看法是：
我知道不同的数字，直到6，应该由AI选择(从4，3或1)来赢得比赛。
例如:当n=1时，选择1 n= 2，选择1；n= 3，选择3；n =4，选择4；n= 5，选择3；n= 6，选择4；
但我无法找到一个通用的算法，可以应用于所有的数字从1到99，以赢得比赛。我想知道和理解如何得到一个一般的递归方程和递归算法，就像Fibonacci级数中的函数递归：
Fibonacci(n-1)+Fibonacci(n-2)
选择数字之间的4，3或1之间由人工智能赢得比赛。
我没有递归方面的经验，所以请试着详细解释算法。
回答 2
Stack Overflow用户
发布于 2018-05-24 04:21:33
我认为不能移动的玩家会输掉比赛。你似乎在任何地方都没有提到，但这就是它的样子。
首先，请注意，每个数字要么是一个获胜的位置，要么是一个失败的位置，让玩家采取这一轮，无论是哪个球员。例如，数字7是一个失败的位置:如果当前玩家选择1，另一个选择4；如果3或4，分别用4或3。
递归关系如下：
win(x) = not win(x-1) or not win(x-3) or not win(x-4)事实上，如果有一个行动，导致一个失败的立场，我们可以通过选择这一举动获胜。如果没有，我们的对手就会赢，假设他们从那时起打得很好。
现在，与其实现递归，不如使用它来计算每个数字自下而上的得失状态，并将其存储在数组中，如下所示：
win[0] := false
win[1] := true
win[2] := false
win[3] := true
for x := 4, 5, ..., 99:
win[x] := not win[x-1] or not win[x-3] or not win[x-4]这样，您只需进行100个简单的计算，而不是遍历所有可能的游戏的庞大递归树，从数字99开始。
现在，在计算了这个win数组之后，如何从数字x中移动？如果是win[x] = false，这两个动作都行:如果对手打得很好，我们无论如何都会输。如果是win[x] = true，请查找win[x-1]、win[x-3]和win[x-4]中的哪一个存在(注意下面的流量！)而且是假的，然后做出这样的举动。
最后，注意到计算阵列看起来如下所示：
[0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1]显然，有一个7的周期。因此，对于这个精确的游戏，一个定制的策略可以完全不使用数组，只要看看我们的数字模7的剩余部分。事实上，你几乎在问题中做到了，只是在前面加上了“剩余模7是.”再加上一些大约零的东西：
例如:当n=1时，选择1 n= 2，选择1；n= 3，选择3；n =4，选择4；n= 5，选择3；n= 6，选择4；
Stack Overflow用户
发布于 2018-05-24 03:54:51
这是我针对你的问题的代码，它可能对你有帮助
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
//init nimbers
int arr[100];
fill(arr,arr+100,-1);
arr[0]=0;
queue<int> q;
q.push(0);
while(q.size()>0){
int u=q.front();
q.pop();
if (u+1<100 && arr[u+1]!=1)
{
arr[u+1]=(arr[u]+1)%2;
q.push(u+1);
}
if (u+3<100 && arr[u+3]!=1)
{
arr[u+3]=(arr[u]+1)%2;
q.push(u+3);
}
if (u+4<100 && arr[u+4]!=1)
{
arr[u+4]=(arr[u]+1)%2;
q.push(u+4);
}
}
int n=7;
cout<<"Welcome to the Game\n";
cout<<"You are player 1\n AI is player 2\n";
int play=0;
while(n>0){
if (play%2==0)
{
int step=-1;
cout<<"Enter your move?";
cin>>step;
n-=step;
cout<<"Now n="<<n<<endl;
}
else{
int step=1;
if(n-1>=0 && arr[n-1]==0) step=1;
if(n-3>=0 && arr[n-3]==0) step=3;
if(n-4>=0 && arr[n-4]==0) step=4;
n-=step;
cout<<"AI played "<<step<<" move\n";
cout<<"Now n="<<n<<endl;
}
play=(play+1)%2;
}
if (play)
{
cout<<"You won";
}
else cout<<"AI won";
return 0;
}https://stackoverflow.com/questions/50499973
复制相似问题
腾讯云开发者
