想迷惑初学者的棋手吗？请他与一匹马和一头大象对撞。想困惑一个新手程序员吗？要求他用一匹马和一头大象计算垫子。
下象棋的问题激发了程序员的想象力，这就是为什么在组合技巧的实际演示中，我选择了从“将军到孤独的国王”循环中最困难的下象棋问题。目标设定
该项目的目标是创建一个解决方案基础，即在棋盘上列出白国王，大象，马和黑国王所有可能位置的正确动作列表。在本出版物中，我将告诉您如何解决此问题，必须面对的困难以及最终的结果。使用的技术：C＃，JavaScript，PHP，HTML，CSS。作为一个非常平庸的国际象棋棋手，我从未学会过如何快速与一匹马和一头大象对峙。因此，我决定用自己的编程技能弥补这一缺点，对所有可能的职位进行排序，并为每个职位找到正确的举动。在编写至少一行代码之前，有几周的时间，我制定了一个“拿破仑式”的计划。我真的很想从头开始解决此问题，方法是对所有遮罩组合进行分类。然后退后一步，直到用尽所有可能的选项。有多少种选择？
棋盘上有64个单元。我们有四个数字。可能的组合数量为64 * 64 * 64 * 64 = 16,777,216。您只能留下白胸象。选项数量将减半：64 * 32 * 64 * 64 = 8,388,608。那么多职位将在我们的解决方案数据库中。实际上，组合的数量甚至更少：两块不能站在一个正方形上，国王不能站在相邻的正方形上，黑人国王不能处于支票之下，依此类推。展望未来，我要说的是解决方案数据库为5,609,790个组合，整个阵列将占67％。但是，为了简化算法并加快对数据库数据的访问，我决定不“浪费时间”，而是为所有组合创建一个四维数组。定义了以下结构来存储每个组合： struct Combo
{
public Coord whiteKing;
public Coord whiteBishop;
public Coord whiteKnight;
public Coord blackKing;
}
在内部，另一个Coord结构用于记录图形的坐标，并能够计算从0到63的索引，并带有重载的比较运算符。 public struct Coord
{
public byte x;
public byte y;
public int index
{
get { return x + y * 8; }
set { x = (byte) (value % 8);
y = (byte) (value / 8); }
}
public static bool operator == (Coord a, Coord b)
{
return a.x == b.x && a.y == b.y;
}
}
事实证明，此结构非常方便地将其作为参数传递给各种辅助功能，例如： bool isCheck (Combo combo);
bool isCheckmate (Combo combo);
bool isCheckByBishop (Combo combo);
但是，仅记录这种结构的决策结果还不够，我们仍然需要...白盒
我们程序的目标是创建一个“白盒子”，在该盒子中将“移动为白色”的所有位置以及已知的哪个动作采取了哪些动作以及保证将要检验的动作将被加在一起。“白盒”的组成部分是以下结构： struct WhitesMove
{
public Combo combo;
public byte moves;
public Coord moveFrom;
public Coord moveTo;
}
组织“白盒”的最简单方法是打开一个二维矩阵。该矩阵的每个维度对应于每个图形的可能位置： WhitesMove [ , , , ] box = new WhitesMove [64, 32, 64, 64];
第一维是白国王的坐标。第二维是白象/ 2的坐标。第三维是白马的坐标。第四维是黑王的坐标。最主要的是不要混淆它们的顺序：)阵列将被放电33％，但是非常便于处理。在此阵列中，将存储8,388,608个条目以解决组合。顺便说一句，在开始编写所有搜索算法之前，我创建了一个空项目并初始化了此四维矩阵，以确保有足够的内存并且不需要发明其他东西。显然，在过去的千年中参加计算机科学奥林匹克竞赛的经历影响了Turbo Pascal 7.0，当时该结构的大小不能超过64 KB。算法思想
简要描述解决此问题的主要思想。它基于广度优先搜索算法，由于两个人下棋并依次进行移动，因此必须稍作修改。因此，我们需要两条线而不是一条线：“黑色”和“白色”。 Queue<BlacksMove> blackQueue = new Queue<BlacksMove>();
Queue<WhitesMove> whiteQueue = new Queue<WhitesMove>();
通过WhitesMove的结构，我们已经见面了。BlacksMove的结构更加简单，因为不需要在其中存储Black的最后一招。struct BlacksMove
{
public Combo combo;
public byte moves;
}
首先，在“黑线”中，我们将放置所有移动为黑色的遮罩位置。然后，从每个这样的位置开始，怀特将反向移动并形成一条“白线”，即怀特移动的位置列表。需要重复这些步骤，直到用尽所有可能的组合。伪代码形式的主要算法为： " ", " ", " "
" "
{
" "
" "
" "
" "
" "
" "
" "
" "
" "
} " "
" "
磨砂位置
创建正确动作的基础始于搜索所有遮罩组合。使用枚举器可以非常有效地描述此过程。 foreach (Combo combo in AllCheckmates())
{
BlacksMove checkmate = new BlacksMove { combo = combo, moves = 0 };
blackQueue.Enqueue(checkmate);
}
总共找到232个遮罩位置。让我提醒您，我们只限于白场大象。其中一些是非常异国情调，不存在且“合作”的，这是黑人国王本人爬到垫子下的时候。
下象棋的人都清楚地知道，必须将带有马匹和白色野象的垫子放在白色的角落。在黑色角落中，只有在黑色同时出现时才有可能出现死敌。我在文章的开头特别贴了一张带有这种伪自动机的照片，以引起真正的国际象棋选手的注意：）一脚垫
下一步是反转白色。也就是说，对于找到的每个遮罩位置，使所有可能的白色移回。如何做出相反的举动？鉴于我们的职位没有提供任何捕捉，该算法非常简单-怀特采取任何行动，此后将不再向黑王检查。以此方式找到的所有位置均已放置在“白框”中，表示垫子之前有一个动作，以及执行此动作的方式。一路上，我们将发现的组合放在“黑线”中。这部分算法如下所示：
while (blackQueue.Count > 0)
{
BlacksMove black = blackQueue.Dequeue();
foreach (WhitesMove white in AllWhiteBackMoves(black))
if (!isCheck(white.combo))
if (!whiteBox.Exists(white.combo))
{
whiteBox.Put (white);
whiteQueue.Enqueue(white);
}
}
顺便关于收益yield- , , :
IEnumerable<WhitesMove> AllWhiteBackMoves(BlacksMove black)
{
foreach (WhitesMove white in AllWhiteKingMoves(black))
yield return white;
foreach (WhitesMove white in AllWhiteBishopMoves(black))
yield return white;
foreach (WhitesMove white in AllWhiteKnightMoves(black))
yield return white;
}
总共找到920个这样的位置，这是最有趣的：马
动作：大象
动作：国王动作：
垫子半步走
下一步是反转黑色。使用这种算法，我花费了最长的时间，在一切正常工作之前犯了很多错误。乍一看，一切都与以前的版本相似：对于“白线”中的每个位置，都必须整理出黑王所有可能的举动。并将找到的所有组合添加到“黑线”中-毕竟，这是一个半步的将死，然后您可以再次对怀特进行反向移动-将有两个步的将死-继续直到所有选项都被修改。那是错误。布莱克采取任何可能的举动都会采取“合作”将军的措施，但实际上国王不一定会在将军的统治下。德米特里·格林（Dmitry Grin）向我指出了这个错误，我参加了所有有关创建此程序的网络研讨会，为此我要多谢他。正确的算法如下：对于黑王反向移动之后的每个位置N，您都需要进行所有可能的直接移动，以确保它们都导致从“白盒”中熟悉的位置，即指向垫子。并且只有在该位置之后，才能将N添加到“黑线”。而且如果黑人国王可以“滑出”位置N，那么我们将跳过此选项。当有更多熟悉的职位时，她将在随后的迭代中见面。这部分算法如下所示：
while (whiteQueue.Count > 0)
{
WhitesMove white = whiteQueue.Dequeue();
Combo whiteFigures = white.combo;
foreach (BlacksMove black in AllBlackBackMoves(white))
{
bool solved = true;
foreach (Coord blackKing in AllKingMoves(black.combo.blackKing))
{
whiteFigures.blackKing = blackKing;
if (isCheck(whiteFigures))
continue;
if (box.Exists(whiteFigures))
continue;
solved = false;
break;
}
if (solved)
blackQueue.Enqueue(black);
}
}
总共找到156个“垫子和一半动作”的组合。中途迭代
所描述的用于创建半通的算法必须循环。从“黑线”我们形成“白线”，反之亦然-从“白线”我们形成“黑线”。依此类推，直到所有新职位用尽为止。在“白线”形成阶段，“白盒”被填充，因为它放置了白棋移动的位置。枚举所有选项的现成算法在12分钟内在某处起作用，并在第33步停止。这就是从任何位置使黑人国王与一匹马和一头大象交配所需的最大移动量。顺便说一下，没有那么多“最困难”的职位，只有156个，这里是其中之一：
马塔不会！
在很多职位上，即使白方迁居，黑人国王也可以吃骑士或主教并获得平局。也有僵局的选择。这是一些最有趣的项目。
如何存储解决方案数据库
如何存储找到的解决方案库？最简单和错误的方法是使用序列化。结构的序列化四维数组占用了1.7 GB的磁盘空间。序列化过程持续约六分钟，反序列化过程也差不多。当然，此选项不合适。另外，实际上，不需要使用整个四维数组。特定订单项仅需要一个条目。尤里卡！为了节省空间，您仍然可以摆脱存储每种组合的图形坐标的麻烦。当我们有一个四维数组时，每个图形在板上的位置由其在数组中的索引唯一地确定。决定将整个解决方案数据库存储在一个文件中-作为对二维数组的线性扫描。对于任何可能的位置，都会计算记录正确答案的地址。如何尽可能紧凑地记录我们需要的答案？图形的位置不需要存储，因此仅剩下三个数字-垫子上有多少移动，走什么和走哪里。这是唯一确定White正确举动的方式。6位移到垫子上的次数是0到33.2位之间的整数。行走的人物-三种可能的选择，国王，大象或马。6位哪儿去了-板上的字段索引是从0到63。因此，对于每个决策记录，两个字节就足够了：1个字节-移到垫子上有多少个，如果位置不熟悉则为0。2个字节-FFNNNNNNFF- 要行走的图形的编号（1-国王，2-大象，3-马）NNNNNN-单元格坐标-位置（从0到63）。因此，解决方案数据库文件占用64 * 32 * 64 * 64个字=正好16兆字节。图形的位置由每个单词的坐标设置，在第一个字节中-移至垫子的移动数（如果无解，则为0），第二个移动存储正确的移动。如果您不存储移动到垫子上的移动次数，则可以将文件大小减小一半，但是那样玩不会很有趣。黑平方白象的坐标
现在该为优化付出代价了。有必要为与“黑白”大象组合使用的坐标重新计算算法。这样做如下。如果大象的坐标落在黑场上，则必须“翻转”板上所有图形的坐标。在这种情况下，Y坐标保持不变，X更改为7-X。坐标翻转的视觉演示，请参见该图。
如果大象站在白色的笼子里，那么首先您需要“翻转”所有图形的坐标。然后在解决方案数据库中寻找位置。然后再次“翻转”从那里读取的正确移动的坐标。可视化解决方案库
这样，问题就解决了！解决方案数据库已创建。但是如何证明呢？最明显的方法是使用Web技术，这样您就可以给出一个有效示例的链接。在我的“程序员公式”中，已经创建了照片课程“ Nano-Chess ”，其中使用HTML，CSS，JavaScript和PHP技术创建了一个交互式棋盘，无需两个人就可以玩游戏。该脚本作为基础。我只剩下四个部分，消除了捕获的可能性，添加了PHP函数以从解决方案库中读取正确的步骤，并通过JavaScript赋予了“喘息的机会”。在www.videosharp.info/chess页面上，您可以尝试使用解决方案数据库。
对于每个位置，都会为白色和黑色计算移动。对于怀特-导致将死的最佳举动。对于黑色-垫子有多少移动可能发生任何移动。您可以用鼠标进行图形的任何移动，而不必按规则进行。该脚本将计算任何位置的期权，或者说没有期权。演奏，执行建议的动作或自行决定移动乐章非常有趣。结论
解决国际象棋问题的工作非常有趣。如果您想重复这种方法，则可以观看有关从头开始创建该程序的视频，并获得详细说明和独立任务的结果。祝你好运！