尼姆游戏(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/the-nim-game-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 7 分钟阅读 - 3237 个词 阅读量 0尼姆游戏(译文)
原文地址:https://www.codeproject.com/Articles/19938/The-Nim-Game
原文作者:Volynsky Alex
译文由本站 robot-v1.0 翻译
前言
A two-player mathematical game of strategy
两人策略性数学游戏
介绍(Introduction)
什么是Nim游戏?(What is the Nim Game?) Nim是两人策略的数学游戏,其中玩家轮流从不同的堆中移除对象.在每一回合中,玩家必须移除至少一个对象,并且可以移除任意数量的对象,前提是它们都来自同一堆.(Nim is a two-player mathematical game of strategy in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap.) Nim的变种自远古时代就开始演奏.据说该游戏起源于中国(与中国游戏" Jianshizi"或" Picking Stones"非常相似),但其起源尚不确定.欧洲最早提到Nim的时间是16年代初(Variants of Nim have been played since ancient times. The game is said to have originated in China (it closely resembles the Chinese game of “Jianshizi”, or “picking stones”), but the origin is uncertain; the earliest European references to Nim are from the beginning of the 16)日(th)世纪.(century.) 它的当前名称是由哈佛大学的查尔斯`布顿(Charles L. Bouton)创造的,他也在1901年开发了完整的游戏理论,但从未充分解释该名称的由来.该名称可能源自德语nimm!意思是" take!",或者同义的过时英语动词nim.有人指出,将NIM上下颠倒会导致WIN.(Its current name was coined by Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901, but the origins of the name were never fully explained. The name is probably derived from German nimm! meaning “take!”, or the obsolete English verb nim of the same meaning. Some people have noted that turning the word NIM upside-down and backwards results in WIN.) Nim通常是一场悲惨的游戏,玩家拿走最后一个物体会失败.尼姆也可以作为普通游戏玩,这意味着做出最后一招的人(即取得最后一个物件的人)获胜.之所以称为正常游戏,是因为大多数游戏都遵循此约定,即使Nim通常不遵守该约定.(Nim is usually played as a misere game, in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.)
XOR赢得Nim的技巧(XOR Tricks for Winning at Nim)
虽然需要一些高级数学才能找到Nim的秘密策略,但采用该策略实际上只需要了解二进制数即可.(Although it takes some high-level math to find the secret strategy of Nim, employing that strategy really only requires an understanding of binary numbers.) 为了在Nim上获胜,您必须知道如何使用二进制运算XOR,XOR表示"异或". XOR的真正含义是"如果x或y为1,则x XOR y =1,但如果它们都为1,则不是.“因此,0 XOR 0 =0\1 XOR 0 =1\0 XOR 1 =1和1 XOR 1 =0.或者,更简单地说,如果两个参数相同,则XOR运算的结果为0,而XOR 1的结果为1.论点是不同的.(In order to win at Nim, you have to know how to use the binary operation XOR, which stands for “exclusive or”. What XOR really means is “x XOR y = 1 if either x or y is 1, but not if they are both 1.” So, 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, and 1 XOR 1 = 0. Or, more simply, the result of the XOR operation is 0 if both arguments are the same and 1 of the arguments is different.) 对于Nim中的任何给定情况,都有一个数字确定该情况是否是失败的情况.要找到该数字,必须对每行中的对象数连续执行XOR操作.例如,位置是:(For any given situation in Nim, there is a number which determines whether or not that situation is a losing one. To find that number, you have to perform the XOR operation on the number of objects in each row successively. For example, the position is:)
因此,要查看这是否是亏损头寸,我们必须对每一行中的对象数量进行异或运算,如下所示:(So to see if this is a losing position, we have to XOR the number of objects in each row, as follows:)
1 XOR 3 XOR 5
当以二进制显示时,它是:(which when shown in binary is:)
001 XOR 011 XOR 101
现在我们必须对每个数字中的每个数字进行异或运算,并将每个结果放在该数字的列下方.让我们从最右边的数字开始.(Now we have to XOR each digit in each number and put each result below the column for that digit. Let’s start with the rightmost digits.)
1 XOR 1 XOR 1 is the same as (1 XOR 1) XOR 1
1 XOR 1 =0,并且0 XOR 1 =1.因此1 XOR 1 XOR 1 =1.(1 XOR 1 = 0, and 0 XOR 1 = 1. So 1 XOR 1 XOR 1 = 1.) 现在继续其余的列,直到有一个新的二进制数.(Now continue with the rest of the columns until we have a new binary number.)
001 XOR 011 XOR 101 = 111
如果此最终数字的所有数字均为零,则该头寸为亏损头寸!如果轮到您而该头寸是亏损头寸,那么您就有麻烦了.但是,在此示例中,该数字非零,因此我们可以将头寸变成对手的亏损头寸.(If all the digits of this final number are zero, the position is a losing position !!!!!!! If it’s your turn and the position is a losing position, you’re in trouble. However, in this example, the number is non-zero, so we can turn the position into a losing position for our opponent.) 让我们以对行进行XOR运算得到的数字111尝试查找与111进行异或运算后得到的行数比以前的行低.好吧,我们知道是否将001 XOR 111大于1,将011 XOR 111大于3,所以我们必须对101 XOR 111进行运算,即010,或者十进制2,并且小于5.因此,为了让对手失去位置,您只需从5行中删除3个对象,剩下2个即可.(Let’s take the number 111 that we got from XORing the rows and try to find a row which, when XORed with 111, gives us a lower number than the row previously had. Well, we know if we do 001 XOR 111 it will be greater than 1, and 011 XOR 111 will be greater than 3, so we must do 101 XOR 111, which is 010, or in decimal 2, and is less than 5. So in order to give your opponent a losing position, you just have to remove 3 objects from the row of 5, leaving 2.)
概要(Summary)
获胜所需的步骤是:(The steps needed to win are:)
- 轮到您了时,将每行中的对象数转换为二进制数并对它们进行XOR.(When it is your turn, convert the number of objects in each row into binary numbers and XOR them.)
- 如果结果为(If the resulting number is)
0
,您没有什么可以赢得的.如果不是(, there’s not much you can do to win. If it isn’t)0
,将其与一行进行XOR并进行移动,以便在该行中保留许多对象.(, XOR it with a row and make a move so as to leave that many objects in that row.) 有关游戏数学理论的更多信息,请参见(For more information about Mathematical theory of game, see) 维基百科(Wikipedia) .(.)
使用代码(Using the Code)
我不会逐步详细介绍游戏或类似的内容,但我将讨论一些特定的元素.(I’m not going to be detailing the game step by step or anything like that, but I’ll talk about a few specific elements.) 该代码演示了C#中标准小部件的工作.以下代码说明了这些控件的动态创建和初始化过程(例如:按钮,组合框,图像等).(The code demonstrates the work of the standard widgets in C#. The following code illustrates the process of dynamic creation and initialization of these widgets (for example: buttons, ComboBoxes, image, etc.))
/**************************************************/
/* The method creates seven ComboBoxes */
/**************************************************/
void CreateNew_ComboBoxes()
{
int i,x=31;
try
{
cmbbox = new ComboBox[7];
for ( i = 0; i < 7; i++)
{
cmbbox[i] = new ComboBox();
cmbbox[i].Parent=this;
cmbbox[i].Width=40;
cmbbox[i].Location=new Point(x,5);
x+=107;
cmbbox[i].ForeColor=Color.Blue;
cmbbox[i].MaxDropDownItems=30;
cmbbox[i].Tag=i;
cmbbox[i].DropDownStyle=ComboBoxStyle.DropDownList;
cmbbox[i].Visible=true;
cmbbox[i].SelectedValueChanged += new System.EventHandler(
this.Change_Select_Data_ComboBox);
}
FlagColor = true;
}
catch (System.IndexOutOfRangeException exc)
{
MessageBox.Show(exc.Message,"Overloaded");
return;
}
}
/**************************************************/
/* The method enters numbers in ComboBoxes */
/**************************************************/
void Fill_ComboBoxes()
{
Random rdm;
int Number_Members_In_One_Row;
SumOfImages=0; // sum of all pencils
for (int i =
0; i < 7; i++)
{
rdm = new Random(unchecked((int)DateTime.Now.Ticks));
// get random number of elements for one heap
Number_Members_In_One_Row = (rdm.Next(30)+1);
SumOfImages+=Number_Members_In_One_Row;
if(cmbbox[i].Items.Count!=0)
{
cmbbox[i].Items.Clear();
}
for(int k=1; k<=Number_Members_In_One_Row; k++)
{
cmbbox[i].Items.Add(k);
}
cmbbox[i].Text=Number_Members_In_One_Row.ToString();
num_choos_pens=0;
System.Threading.Thread.Sleep(35);
}
}
经过上述代码后,我们将看到7(After the above-stated code, we shall see 7) ComboBox
es:(es:)
用同样的方法(In the same way, methods) CreateNew_Images()
和(and) Fill_Images()
用铅笔创建"堆”.(create “heaps” with pencils.)
/*******************************************************************/
/* The method creates a matrix in the size 7 on 30 for the pencils */
/*******************************************************************/
void CreateNew_Images()
{
int y;
int x=0;
Image image = Image.FromFile("GrayPen.bmp");
images = new PictureBox[7][];
for(int i=0; i<7; i++,x+=107)
{
y=this.Height-(int)(6*(image.Height));
images[i] = new PictureBox [30];
for(int j=0; j<30; j++)
{
images[i][j]= new PictureBox();
images[i][j].Parent=this;
images[i][j].Height=15;
images[i][j].Width=104;
images[i][j].Anchor=AnchorStyles.Bottom|AnchorStyles.Left;
images[i][j].Location=new Point(x,y);
y-=16;
}
}
}
/*************************************************************/
/* The method fills in a matrix gray pencils */
/*************************************************************/
void Fill_Images()
{
int new_number_elements;
int old_number_elements;
Image image = Image.FromFile("GrayPen.bmp");
for(int i=0; i<7; i++)
{
new_number_elements = cmbbox[i].Items.Count;
old_number_elements=(int)numberLoadImages[i];
// if you must insert images
if(old_number_elements < new_number_elements)
{
for(int j=old_number_elements; j < new_number_elements;
j++)
{
images[i][j].Image=image;
}
numberLoadImages.SetValue(new_number_elements,i);
}
// if you must remove images
else if(old_number_elements > new_number_elements)
{
PictureBox img = new PictureBox();
for(int j=old_number_elements-1;
j>=new_number_elements; j--)
{
images[i][j].Image=img.Image;
}
numberLoadImages.SetValue(new_number_elements,i);
}
}
}
该程序支持两个玩家(一个对抗另一个)的游戏机会,以及具有计算机的人的游戏模式.以下代码说明了计算机的策略(当然,如果我们选择了与计算机一起玩的选项):(The program supports an opportunity for game of two players (one against another), and a mode of game of the person with a computer. The following code illustrates strategy of a computer (if we have, of course, chosen an option to play with a computer):)
/*******************************************************/
/* Computer's game strategy */
/*******************************************************/
private void ComputerGame()
{
int [] arr = new int[7];
//Array numbers of "gray" pens in each column
for(int i= 0;i<7; i++ )
{
arr[i]=((int)numberLoadImages[i]-BlueRedImages[i]);
}
int tryResultElements=-1;
int numElements;
int n;
//////////////////////////////////////////////////////////////////
// 3 cycles for find column and number elements //
//////////////////////////////////////////////////////////////////
//for k times
for(int k= 0;k<7 && tryResultElements!=0 ; k++)
{
numElements=arr[k];
for (n=1; n<=numElements; n++)
{
num_choos_pens=n;
index=k;
////////////////////////////////////////////////////
tryResultElements = numElements-n;
//for m columns
for(int m= 0;m<7; m++)
{
if(k!=m)
tryResultElements^=arr[m];
}
if(tryResultElements==0)
{
num_choos_pens=n;
index=k;
break;
}
}
}
//////////////////////////////////////////////////////////////////
// from (k+1) column computer must get n elements //
//////////////////////////////////////////////////////////////////
int j;
int count;
Image imageRed = Image.FromFile("RedPen.bmp");
SumOfImages = SumOfImages-num_choos_pens;
count=num_choos_pens;
j=
((int)numberLoadImages[index]-BlueRedImages[index]-1);while(
count>0)
{
cmbbox[index].Items.Remove(cmbbox[index].Items.Count);
count--;
}
//Save blue/red items in array images[index][]...
BlueRedImages[index]=BlueRedImages[index]+ num_choos_pens;
for(int
i=
0;i < num_choos_pens; i++, j--)
{
images[index][j].Image=imageRed;
}
if(SumOfImages==0)
{
switch(MessageBox.Show("New Game?","The game" +
"is over.Red won",MessageBoxButtons.YesNo))
{
case DialogResult.Yes: //New Game
this.winBlue=true;
this.winRed=false;
this.UpdateGameWin();
this.Fill_ComboBoxes();
this.Fill_Images();
this.btnOK.Focus();
this.num_choos_pens=0;
this.index=-1;
this.FlagColor=false;
return;
case DialogResult.No: //Finish Game
this.Close();
break;
}
}
int newNumElementsInComboBox;
newNumElementsInComboBox=cmbbox[index].Items.Count;
cmbbox[index].Text=(
newNumElementsInComboBox>0)? Convert.ToString(
newNumElementsInComboBox):"";
winBlue=!winBlue;
winRed=!winRed;
num_choos_pens=0;
index=-1;
}
执照(License)
本文没有附带任何明确的许可,但可能在文章文本或下载文件本身中包含使用条款.如有疑问,请通过下面的讨论区与作者联系.可以找到作者可能使用的许可证列表(This article has no explicit license attached to it, but may contain usage terms in the article text or the download files themselves. If in doubt, please contact the author via the discussion board below. A list of licenses authors might use can be found) 这里(here) .(.)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# .NET Windows Visual-Studio Dev 新闻 翻译