关于维尔斯和铁链的问题

算法+数据结构=程序-VirtN。

“我们有一个很好的机会来进行一次小型但非常有启发性的战术练习”

尽管有这篇文章的第一篇题词，我还是允许我不同意作者的观点，并试图表明，在某些情况下，正确选择数据结构可能比正确选择算法更重要。 为了说明这种煽动性的论点，让我们考虑一个简单但有希望的任务来研究“ Chain”游戏。

首先，关于游戏规则-两个玩家进行游戏，起始位置由附近的N个对象组成。 下一步是删除附近任何一个或两个对象（您可以尝试对“附近位置”进行正式定义，但是在直观的水平上是可以理解的）。 删除最后一个对象的玩家将赢得直接游戏，或者必须（您不能跳过此举）选择最后一个对象的玩家将赢得反游戏。 由于在此规则版本中，直接游戏将变得毫无趣味（稍后会对此进行更多介绍），因此引入了附加限制-第一步只能删除一个对象。

首先，我们确定游戏是有限的，因为随着每一步的移动，对象数严格减少，并且当达到零计算的对象数时游戏结束，因此我们有权指望该​​游戏的研究成功。 此外，很明显，游戏的持续时间不能超过N个动作，让我们记住这一事实。

对游戏的研究在于确定对于特定初始数量的对象而言，第一步的玩家是否获胜（因为这是一个零和的游戏，否则他会输），并且双方都是最优的游戏，以及在什么最小的步数上获得了收益（或通过损失移走的最大移动次数是多少？

对于某些H，答案是显而易见的-在一个对象的情况下，第一个对象在一个回合中赢得一场直接比赛，也输掉了一场逆向比赛（P1 = 1，I1 = -1）。 在有两个对象的情况下，第一个玩家在直接游戏中输了两步，而在反向游戏中赢了两步（P2 = -2，I2 = 2），这可能会导致一个关于评估此游戏的简单性的假设，这由三个对象的情况证实（P2 = 3， I3 = -3）。 幸运的是（否则该文章不会发表）具有四个对象的游戏会稍微改变画面（P4 = -4，但I4 = -3），因此确实需要研究游戏。

对于某些H和某些类型的游戏，有启发式算法可确保获得收益。 例如，对于直接游戏的初始H为奇数的游戏，如果您先移动中心对象，然后以中心位置为对称轴重复对手的移动，则可以保证获胜，然后我们保证拿到最后一个对象并获胜。 即使不是为了第一步的限制，相同的策略也适用于偶数个对象，这使得游戏不是那么琐碎。 一般而言，对称策略在计数游戏中很常见，但不是万能药，因为例如在我们的逆向游戏中，这种策略会失败。 应该注意的是，试探法给出了获胜算法，但没有给出位置的准确估计，因为可能存在导致更快获胜的策略（这种情况就是这种情况）。

我们该如何评估游戏-就像我之前收到的1-4个对象的估计值一样-该方法称为从上到下的详尽搜索-我们必须考虑游戏的完整树，即双方的所有可能动作并评估每个位置，包括来源，根据某些规则。 应当指出的是，成功的启发式方法的存在并不能保证我们做出准确的评估，因为它只能回答问题的前半部分-谁获胜，但没有给出所需的最少移动次数。

这意味着我们必须构建完整的游戏树，但是在继续构建之前，我们必须创建正在研究的对象（在本例中为游戏）的模型。

我为什么要专注于此阶段-因为我们无法在对象的实质性体现中对其进行探索。 不，从理论上讲这是可能的（“从理论上讲，世界上几乎没有什么可能）”，我可以想象一幅图片，其中有大量的机器人在现实世界中玩很多游戏，但是这种解决游戏评估问题的材料成本超出了合理的想象数量，因此我们被迫走上与其软件对应对象建模的道路。 在此非常重要的一点是，将足够的模型充分性和必要的简化相结合，沿着一条细线走。

但是首先，需要一些数学来评估任务的复杂性-我们需要对游戏中所有可能的动作进行排序（注意并不是所有可能的位置，这是另一种方法的主题，即动作），并且我们想在开始工作之前评估所需的资源量-确定任务的顺序。 第一步，我们有机会从可用的H中移除任何筹码（我将继续称呼对象），在下一步中-剩余的H-1或附近的两个筹码中的任何一个（与H-2相比，此类筹码的对不超过），其中给出选项总数Hx（H-1 + H-2）。 不难看出，第三步之后我们得到Hx（H-1 + H-2）x（H-2 + H-3 +Δ），依此类推。

如果我们在每个括号中只限制总和的第一项，那么我们得到的移动总数为H！的估计值，从而得出了H ^ H的平方的估计值。

这是一个非常不愉快的结果，它声称我们在使用有效H时会遇到很大的问题，因此最可能的“正面”建模将带来大量的计算成本。 例如，对于处于起始位置的16个筹码，我们将需要考虑大约16！=1013步，并且如果一步为10E-9秒（相当乐观的估计），则总时间约为10E4秒或将近3小时，这有点多，但可以接受，但是对于20个芯片，预期的计算时间为77年，这显然是不可接受的。 阶乘增长非常快，对此无可奈何。

我们提请注意这样一个事实，即移动数量大大超过了可能的位置数量，仅为2 ^ N，并且很明显，我们将落入16个10E（13-5）= 10E7倍筹码的单独位置，这在每天发生搜索任务。 记住这一事实，以后对我们有用。

尽管如此，我们将开始编写程序，并为其确定模型。 首先，我们将芯片编号从1到H，然后创建一个具有元素数量H的数组，并确定索引值为n的数组元素中的数字1表示存在芯片编号n，而数字0表示在特定位置不存在芯片编号。 这样的模型足够，简单，直观，并且可以使切屑清除操作有效，并确定“接近”条件。

现在我们有了一个模型（数据结构），我们可以开始（在全球范围内使用猫头鹰）在该模型上的算法。 完整的带有收益的枚举算法在程序框图中很简单，它包括两个独立的部分-实际的枚举和位置评估，首先，我们将实现第一部分。 请注意，这种算法并不是在结构化编程范式的框架内最好地实现，并且如果我们允许我们自己使用过渡或重复代码，将会更有效，但是即使没有这些风格上的偏差，实现也绝不会自命不凡（圈复杂性是可以接受的） 。 由于我们尚未进行评估，并且希望从该程序中获得结果，因此我们只需导出所考虑的职位，并用肉眼观察它们，以评估正确的实施方案，并确保结果与预期的相符。

现在让我们添加一个位置估计值-当然，编写良好的代码是自记录的（尽管对此声明有不同的看法），但这部分最好用文字描述。 我们的想法是，根据博弈规则，对最终头寸进行明确评估（在我们的情况下，它是唯一的并且由零筹码组成），对于所有其他头寸，我们进行初步的中立评估，然后开始通过将估计向上移动到树上来对其进行优化。 向后移动时，当前位置的估计值在从零的方向上改变一个，然后反转并转移到先前的位置，在此位置，它根据以下规则与先前的估计值组合：

1. 中立评估更改为新评估，
2. 正面评级会变为较小的正面评级，
3. 负面评估会变成很大的负面或正面。

在我们完成所有步骤之后，对初始位置的评估才是最终的。

我们将估算值添加到生成所有位置的过程中，并且可以欣赏分析结果（显示在表格中），添加进度计数器和用于进行分析的计时器。 在装有处理器的计算机上的gcc编译器（优化模式为-O2）上，我得到了一张表，该表完全证实了我们对任务复杂性阶乘顺序的初步假设。 从同一张表中，我们看到我不再期望H超过11，因为计算时间变得不可接受（对我来说，也许您已经准备好等待半小时），并且我们对航向和纳秒的假设与实际时间（平均时间）不符。考虑该位置为100纳秒）。 问题来了-如果我们想在初始位置估计超过11个筹码，该怎么办。

我们可以采取小型优化的方法，使用过渡和标志，进入汇编程序插入，从处理器指令系统中应用棘手的矢量运算，这样，您有时就可以毫无疑问地赢得一个数量级的速度-可能是两个数量级-这是不太可能的，但是我们需要获得许多数量级的增益，因为该数量级（甚至更多）会使H的增量增加10倍。顺便说一句，如果您仅打开编译器优化，它将对我们有所帮助，执行时间将减少 我有4次 - 不坏，并与我们的预期相符。

因此，我们必须首先尝试改进应用的算法，而这些（也是主要的）改进中的第一个是截断暴力法或“ alpha-beta程序”。 它的主要思想看起来很健壮，并且在于以下事实：如果我们将某个排名定为获胜排名，我们将停止提高该排名的排名，然后回到树上。 这种方法可以大大提高算法的速度，特别是如果我们首先研究成功的举动（导致获胜）。 但是，这也可能增加时间，因为增加了当前评估的验证并且选择过程很复杂，因此很难预先估计该方法的影响，因此必须进行实验。 还有一个考虑因素-我们不应忘记，在进行淘汰赛的情况下，在获胜位置的情况下，我们给出了真实但不准确的估计值，因为我们没有考虑部分选择权，并且他们可以通过较少的举动获得胜利。 如果这样的准确性降低适合我们，那么为什么不使用这种方法，但是为了进行准确的评估，除了详尽的搜索之外什么都没有用。

裁剪枚举的结果显示在下表中，我们看到性能有所提高，并且显着提高，但不足以研究大的N值。我们将朝着哪个方向继续我们的研究-首先，我们将看看另一个数据结构，然后，您猜到了（与狡猾的观众打交道很不错）是另一种算法。

让我们注意一个事实，即我们采用的数据结构使芯片变得唯一，例如，单个（不相邻）芯片的位置不等于位置n + 2的单个芯片，这是完全错误的。 我们选择游戏位置的关键元素-旁边的筹码组，并确定其主要特征-该组中的筹码数。 正是这些信息唯一地确定了游戏中的任何位置，我们必须以便于编程的形式呈现它。 我们选择最简单，最明显的数据结构-启动一个由H个元素组成的数组，并将其中恰好有n个芯片的组数存储在该数组的n个元素中。 然后，例如。 对于3个筹码的起始位置，我们将得到表示{0,0,1}。 给定演示文稿的执行过程仍然简单有效，尽管比第一个版本复杂。 在第一步（其中有两个而不是三个）之后，我们得到了位置{0,1,0}和{2,0,0}。

让我们尝试估计给定数据结构在移动次数方面的预期收益。 第一步，我们有（H-1）/ 2 +1选项，第二步（我们将H组分为m和N-m-1）（m-1）/ 2 +（N-m-1-1）/ 2（取1个筹码）+（m-2）/ 2 +（N-m-1-2）/ 2（取2个筹码）=（H-3）/ 2 +（H-5）/ 2并类推，我们得出结论，在每一步中，我们至少节省了一半的举动。 那么我们的增益应至少为2 ^ H，这对于大H非常非常好。 实际上，增益将更大，例如，对于第一个实施例中的位置{8,0 ...}，您需要整理出8个动作，而在第二个动作中，只有1个动作，这种情况下的增益将是8倍。 因此，我们可以坚定地指望2 ^ H，但是期望值会更高，我们将对其进行检查。 可以肯定的是，对于根据这种表示形式的程序，我们得到了表4，最后一行显示了切换到第二版数据结构（手动计算）时的性能提升。 增长简直是巨大的，我们自信地（到达最低点）突破了以合理的时间成本在起始位置分析多达20个筹码的可能性的上限。

此外，我们可以针对给定的数据结构对算法进行微妙的优化，甚至可以获得性能上的提升，但是我们不会获得如此大幅度的增长（数量级），这再次表明Wirth是错误的。 例如，在上面的程序中，故意为下一个动作创建下一个候选程序的过程并非最佳，其明显的改正（让它留给好奇的读者）将速度提高了3倍，但这是一件小事，尽管是一件令人愉快的事。

让我们注意结果，看看一些不明显的事情。 例如，该程序声称，直接启发式游戏中有9个筹码的保证胜利根本不是通过启发式对称算法的9个举动来实现的，而是仅用7个举动就能实现，并且第一个举动与启发式一致（而且，这是唯一的获胜位置） ），但第三和后续动作完全不应该重复对手的动作，这是根据朴素算法得出的，此处的键为{1,0,0,1}，评分为+4。 现在我们已经对游戏进行了准确的评估，我们可以提出一些有趣的问题，例如是否存在具有稳定评估的位置（我们可以让对手为自己奋斗），枚举树中关键位置的存在，以唯一正确的举动找到位置等等（等等）甚至可以获得这些问题的答案以及正确的答案）。

这是汇总成绩表

薯片	直达	意见反馈	职位/时间	职位/时间
1个	1个	-1	1/0	1/0
2	-2	2	4/0	2/0
3	3	-3	17/0	7/0
4	-4	-3	82/0	20/0
5	5	4	463/0	71/0
6	5	-5	3032/0	263/0
7	7	6	22693/0	1107/0
8	-8	-7	191422/0	4945/0
9	7	-7	1798427 / 0.1	24,283 / 0
10	9	8	18634228 / 0.8	125419/0
11	11	-9	211177537 / 10.4	699165 / 0.1
12	-10	-9	*** / 127	4057686 / 0.6
13	11	10		25056975 / 3.84
14	-12	-11		160643971/28
15	13	12		1082854607/213
16	-14	-13		*** / 1698年

尽管如此，我们看到，尽管增长率显着下降，但对运行时间的估计仍然是因子分析。 让我们寻找其他探索游戏树的方法。

我们已经完善了自上而下的算法（当然，我们并没有按照我在信封背面绘制的丑陋形式完成它，您可以通过认真地重写基本过程来显着提高性能，这是可以肯定的，但是问题并没有从根本上解决。决定），所以让我们走另一条路-从下到上。 这种方法的想法直观上简单易懂，但对于人类来说却非常困难-我们从根据游戏规则估算的最终位置开始，然后根据与自上而下搜索相同的规则开始将估算值向上转移到树上。 当然，与此同时，我们正在考虑不可能从当前位置向下移动，但是我们正在考虑所有可以一站式进入当前位置的位置。 我们根据上述规则转让估算。 此外，我们迭代地应用此程序，并且当它停止产生结果时，即在下一轮中，没有一个职位改变了评估，任务完成并且初始职位的评估是正确和准确的。 这种方法使您可以大大减少搜索时间，尤其是在进行一些改进的情况下，但是它有一个很大的缺点（这是经典的方法-我们更改了存储时间），极大地限制了它的范围-高内存需求，因为我们必须存储估算值 , ( ).就所讨论的游戏而言，第一种数据结构的位表示方法表明了自身的价值，还有其他一些方法可以减少所需的内存量（仅存储三个考虑的树级别（低层除外）），但是当然会降低性能，因为搜索变得非常平凡。不过，对于不大于20的H，位置的总数将不超过2 ^ 20，并且对于包含-20至20（即8位数字）的元素的内存，此大小的数组是我可以想象的它的实施将不会困难。因此，很可能为这种算法编写程序并评估结果性能，但是我们不要着急进行估算。我们必须分配哪种内存并不难确定，但使用临时参数则要复杂一些。假设我们立即创建所有可能的位置，它们将为M，则从一个位置开始的平均移动次数可以估计为不超过2 * N（非常粗略的估计）。然后，在每次迭代中，我们都需要执行不超过估计值的M * 2 * H转移，并且由于在每个循环中我们将改善至少一个位置的估计，因此总工作时间将约为M * 2 * H * M.

然后，对于表示数据的第一种方式，我们得到2 ^ H * M * 2 ^ H = 2 ^（2 * H）* M（我们再次强调，该估计从上方算起很强），例如，对于H = 20，则从上方得出搜索时间的估计-down将是20！〜10E18，对于自底向上搜索，我们有2 ^ 40 * 20 =（2 ^ 10）^ 4 * 40 =（10 ^ 3）^ 4 * 40〜10 ^ 14，即20个筹码我们赢了至少10E6次，这非常好。我们还将算出9个初始筹码，获得9！〜10E6进行顶部搜索，并获得2 ^ 9 * 2 ^ 9 * 18〜10E6进行自下而上的筛选，也就是说，从该数字开始，获得底线搜索的优势。最后一条语句有些草率，因为评估下一个位置的过程变得相当长-我们将不得不在已经生成的位置中寻找它，但是对于以位数组形式的特定表示形式，该过程在O（1）中执行。

对于第二个演示，有必要评估不同位置的数量，这是组合技术领域的一项任务。例如，假设有9个初始筹码的游戏，其不同位置的总数为：1+（1 + 4）+（1 + 3 + 2）+（1 + 3 + 3 + 2）+（1 + 2 + 2 + 1 + 1）+（1 + 2 + 1 + 1）+（1 + 1 + 1）+（1 + 1）+ 1 = 1 + 5 + 6 + 9 + 7 + 5 + 3 + 2 + 1 = 39。
然后，通过相同方法进行的估算将得出值H * M * M = 39 * 39 * 9〜10E4，与第一种表示形式相比，其速度要好两个数量级，并且随着H的增加，增益只会增加。与第二种观点相比，您应该期望性能有显着提高，但是很难评估，因此更容易尝试。

因此，如果您自下而上地执行解析程序，则进行第二次演示。我不会给这个程序，我需要留一些东西给读者做家庭分析。我们应该在非常合理的时间内获得有关H的结果。从下方突破的另一个好处是，我们可以通过固定位置下半部分（其筹码数量少于N / 2）的估计值来节省大量资金，因为一旦将估计的下半部分结转下来而下一个筹码数量没有变化，这将给我们带来额外的胜利。 2次

— , , . , , ( ) .

好吧，总而言之，对于那些对我的职位太过认真并且愤慨（公平）愤怒的人的必要解释-我完全不确定在程序定义公式中将算法指定为第一项是否能确定其重要性，我完全同意在某些特定情况下，正确选择的算法可以有序地提高生产率，并且我不会因为错误而责备Dijkstra（我尊重的人）。所有这些都是吸引人们注意的短语，并且该帖子还有其他内容-数据结构在性能方面也非常重要，我希望在设计过程中不要忘记这一点。

PS。他们在听众那里告诉我（嗨，麦克斯），还有另一种研究游戏的方法-数学，而且，鉴于双重姓氏假说，大多数计数游戏都归结为尼姆的游戏，因此我们只需要计算他-总和初始位置（在我看来，这种说法是可疑的），您还可以将原始游戏转换为图表上的游戏（此处没有异议），您可以期望在工作时间达到1.878 ^ N（尽管具体数字有些令人困惑）。这些考虑可能具有生命权，至少该内容的文章令人信服，但我是一名纯从业人员，请将这些选择留给好奇的读者（ars longa，vita brevis）。