我试图解决我遇到问题的部分问题,这是我正在做的更大项目的一部分(不是家庭作业).我认为将它描述为游戏是最容易的(因为我需要它来完成我正在进行的游戏).这是一个单人游戏,就像我描述它一样.
开始您从以下两个职位之一开始:
(2,0,-1)和一个red游戏(3,1,-1)和两个red戏剧END时,你有没有更多的玩游戏结束.目标是以重量结束比赛(0,0,0).
有两种类型的戏剧red和blue.考虑到一个游戏,你可以选择四个部分中的一个:A,B,C,D这会给你额外的重量和可能的额外游戏.以下是规则:
在red戏剧上:
(0,-2,-1)(1,-1,-1)并增加了一个red游戏(2,0,-1)和两个red游戏(0,2,1)和两个blue游戏blue播放的规则是相似的,但是权重的前两列是交换的,最后一列是反向的,并且播放的类型是相反的,所以你得到这个:
在blue戏剧上:
(-2,0,1)(-1,1,1)并增加了一个blue游戏(0,2,1)和两个blue游戏(2,0,-1)和两个red游戏问题可以赢得这场比赛吗？
我正在尝试编写一个程序,通过选择游戏赢得游戏,以便最终的平衡是(0,0,0)你没有更多的游戏.只有我似乎无法做到这一点.所以现在我认为也许没有算法来赢得比赛.我真的很想知道为什么会这样.如果有人有任何想法我可以证明这一点,那么请让我知道!或者,如果你尝试并找到获胜的方法,那么请告诉我.谢谢!!
rua*_*akh 11
可能我错过了一些东西,但只是通过检查,看起来这一系列步骤应该有效吗？:
(2,0,-1)和一个red游戏"开始red戏,片C,其中"增加了重量(2,0,-1)和两个red剧本",让你与体重(4,0,-2)和两个red剧本.red玩一个游戏,一块A"增加重量(0,-2,-1)",给你带来重量(4,-2,-3)和一个red游戏.red戏,片D,其中"增加了重量(0,2,1)和两个blue剧本",让你与体重(4,0,-2)和两个blue剧本.blue玩一个游戏,一块A"增加重量(-2,0,1)",给你带来重量(2,0,-1)和一个blue游戏.blue戏,片A,其中"增加重量(-2,0,1)",让你与体重(0,0,0)和无戏.更示意一点:
move weight plays
------ --------- -------
(2,0,-1) red
red C (4,0,-2) red x2
red A (4,-2,-3) red
red D (4,0,-2) blue x2
blue A (2,0,-1) blue
blue A (0,0,0) -
...没有？
编辑添加:
我是怎么发现的
由于这个问题引起了很多人的兴趣,也许我应该解释一下我是如何找到上述解决方案的.这基本上是运气; 我发生了两个关键的观察:
red A并且red D在重量方面相互抵消(前者补充(0,-2,-1),后者补充(0,2,1)),并且总共添加两个blue游戏(均来自red D)和没有red游戏; 所以,如果你一个接一个地播放,你将两个red剧本"转换" 成两个blue剧本.blue A取消初始重量(它增加(2,0,-1))并且不添加任何游戏,因此可以通过将一个red游戏"转换" 为一个blue游戏来解决整个问题.这给了我一个良好的开端.我开始red C这样做以获得两个red可以"转换"为两个blue剧本的剧本,我立即看到它red C也是blue A重量方面的"对立面" ,因此也可以取消blue A.在我的脑海中,这一切似乎完全抵消了; 然后我把它写下来以确保.
证明它是最小的:
此外,虽然我当时没有理由通过它,但我也可以证明这是一个"最小"的起始位置 - 我的意思是,如果一个序列以"重量(2,0,-1)和一个red游戏"开头"并且以重量结束(0,0,0)而没有游戏,那么序列必须包含至少五个动作.为此,假设我们有一个满足此条件并且移动少于五个的序列.然后:
red游戏减少它,序列将需要至少一个blue游戏,这意味着它必须red D至少包括一次(因为这是获得blue游戏的唯一方式,如果你不'从一开始).red D至少一次,并且red D给我们两个blue游戏,序列将必须包括blue至少两次(因为游戏不会结束直到没有游戏剩余).red D至少包括一次,并且red D在重量的第二个分量上加2,它必须red A至少包含一次,或者red B至少包含两次(因为没有其他方法可以减少重量的第二个分量)至少2).但显然,如果它red D至少包含一次,blue至少两次,red B至少两次,那么它将包含至少五次移动,这是假设禁止的; 所以必须使用这种red A方法.red D至少包含一次,blue至少两次,red A至少一次.并且通过假设,它包含少于五个移动.因此,它必须包含正好一个red D两个blueS,一个red A和零等动作.red游戏,序列包括两个red游戏.因此,序列必须包含一个只产生一次red游戏的移动.但唯一可能的做法是red B,序列不包含.因此,不可能有这样的顺序.
其他起始位置:
我还可以使用类似的参数来证明任何以"权重(3,1,-1)和两个red游戏"选项开头的解决方案也必须包含至少五个动作.一个这样的五步解决方案是:
move weight plays
------ --------- -------
(3,1,-1) red x2
red A (3,-1,-2) red
red B (4,-2,-3) red
red D (4,0,-2) blue x2
blue A (2,0,-1) blue
blue A (0,0,0) -
以下是每个起始位置的解决方案:
Start 1: (2, 0, -1) Reds=1 Blues=0
Red B ==> (3, -1, -2) Reds=1 Blues=0
Red B ==> (4, -2, -3) Reds=1 Blues=0
Red D ==> (4, 0, -2) Reds=0 Blues=2
Blue A ==> (2, 0, -1) Reds=0 Blues=1
Blue A ==> (0, 0, 0) Reds=0 Blues=0
Start 2: (3, 1, -1) Reds=2 Blues=0
Red A ==> (3, -1, -2) Reds=1 Blues=0
Red B ==> (4, -2, -3) Reds=1 Blues=0
Red D ==> (4, 0, -2) Reds=0 Blues=2
Blue A ==> (2, 0, -1) Reds=0 Blues=1
Blue A ==> (0, 0, 0) Reds=0 Blues=0
通过以下C#程序即时发现,该程序随机散步并在少量移动后放弃.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SO8683939
{
struct State
{
public int V1;
public int V2;
public int V3;
public int Reds;
public int Blues;
public int Tokens { get { return Reds + Blues; } }
public string Description;
public State(int v1, int v2, int v3, int reds, int blues)
{
V1 = v1;
V2 = v2;
V3 = v3;
Reds = reds;
Blues = blues;
Description = null;
}
public State Add(State other)
{
State sum;
sum.V1 = V1 + other.V1;
sum.V2 = V2 + other.V2;
sum.V3 = V3 + other.V3;
sum.Reds = Reds + other.Reds;
sum.Blues = Blues + other.Blues;
sum.Description = null;
return sum;
}
public override string ToString()
{
var detail = string.Format("({0}, {1}, {2}) Reds={3} Blues={4}", V1, V2, V3, Reds, Blues);
if (Description != null)
{
return Description + ": " + detail;
}
return detail;
}
}
class Program
{
static void Main(string[] args)
{
var start1 = new State(2, 0, -1, 1, 0) { Description = "Start 1" };
var start2 = new State(3, 1, -1, 2, 0) { Description = "Start 2" };
var end = new State(0, 0, 0, 0, 0);
var redA = new State(0, -2, -1, -1, 0) { Description = "Red A" };
var redB = new State(1, -1, -1, 0, 0) { Description = "Red B" }; ;
var redC = new State(2, 0, -1, 1, 0) { Description = "Red C" }; ;
var redD = new State(0, 2, 1, -1, 2) { Description = "Red D" }; ;
var redOptions = new[] { redA, redB, redC, redD };
var blueA = new State(-2, 0, 1, 0, -1) { Description = "Blue A" };
var blueB = new State(-1, 1, 1, 0, 0) { Description = "Blue B" };
var blueC = new State(0, 2, 1, 0, 1) { Description = "Blue C" };
var blueD = new State(2, 0, -1, 2, -1) { Description = "Blue D" };
var blueOptions = new[] { blueA, blueB, blueC, blueD };
var startingPosition = start1;
var maxSolutionLength = 5;
var rand = new Random();
var path = new List<State>();
while (true)
{
var current = startingPosition;
path.Clear();
//Console.WriteLine("Starting");
//Console.WriteLine(current);
while (true)
{
State selected;
if (current.Reds == 0)
{
selected = blueOptions[rand.Next(4)];
}
else if (current.Blues == 0)
{
selected = redOptions[rand.Next(4)];
}
else
{
if (rand.NextDouble() < 0.5)
{
selected = blueOptions[rand.Next(4)];
}
else
{
selected = redOptions[rand.Next(4)];
}
}
//Console.WriteLine(selected);
path.Add(selected);
current = current.Add(selected);
//Console.WriteLine(current);
if (current.Equals(end))
{
Console.WriteLine("Success!");
var retrace = startingPosition;
Console.WriteLine(retrace);
foreach (var selection in path)
{
retrace = retrace.Add(selection);
Console.WriteLine("{0} ==> {1}", selection.Description, retrace);
}
Console.ReadLine();
break;
}
else if (current.Tokens == 0)
{
// fail
//Console.WriteLine("Fail");
break;
}
else if (path.Count >= maxSolutionLength)
{
// fail
//Console.WriteLine("Fail");
break;
}
}
}
}
}
}