井字游戏...我敢肯定，每个人都玩过。 该游戏的简单性非常吸引人，尤其是当您将时钟拖到课程中的某个位置（一对夫妇）时，除了笔记本纸和一支简单的铅笔之外，什么都没有。 我不知道谁是第一个猜出要在9个正方形内画十字和圆形的人，但是从那以后，游戏的需求就丝毫没有减少，尤其是因为人们提出了很多游戏变种。
本文是关于在JavaScript上开发AI以播放井字游戏的这些变体之一的过程：我有很多资料，但我用动画和图片稀释了。 无论如何，至少值得一试。
此版本的游戏与原始版本之间的区别如下：
- 该字段可以任意大 （笔记本计算机可以使用多长时间）
- 获胜者是连续放置5件 （如果可以这样称呼）的人。
一切都很简单……同时又很复杂：游戏的结果无法像经典模拟游戏一样预先计算。 这种“小预测”夺走了我很多时间和神经。 希望你觉得有趣。
在开始之前
我被迫提前为文章的数量道歉，并且在某些地方还不太清楚地表达思想，但是，我不能挤鸡群而不损失内容和质量。
我建议您首先熟悉
结果 。
代号热键和命令：
- D -AI将为您迈出第一步
- T-查看细胞重量
- 在控制台中编写SHOW_WEIGHTS = true可以查看所有已分析单元的权重。
让我们开始吧
您需要从游戏本身的实现开始，即 到目前为止，没有机器人的情况下为两个玩家编写了一个应用程序。 就我的目的而言，我决定使用javascript + jquery + bootstrap4，尽管实际上并没有在其中使用它，但最好保留它-否则表会浮动。 没有什么特别的要说的，关于js，jquery和bootstrap的材料很多。 我只能说我使用了MVC。 无论如何，我不会绝对解释所有代码-已经有很多资料。
这样，运动场就准备好了。 您可以在单元格中设置形状。 但是，任何球员的胜利都没有以任何方式确定。
游戏结束
当其中一名玩家连续放置
5张棋子时，游戏结束。 “很简单！” 我以为 然后他开始扫描场中的所有单元：首先是水平的，然后是垂直的，最后是对角线。
这是一种愚蠢的方法，但它确实有效。 但是，它可以大大改善，我做到了：大多数游戏单元在整个游戏过程中都将保持空白-比赛场地太大，无法完全填充。 由于必须每一步扫描一次，并且一次只能放置一块，因此您只能专注于这一块（单元）：只扫描拥有同一单元的单元的一个水平，垂直和两个对角线。
另外，您无需扫描所有细胞系。 由于游戏的结尾是连续5个块，因此彼此不相隔6个单元的块对我们来说并不重要。 扫描每侧五个单元就足够了。 不明白吗？ 请参见下面的动画。
查看代码checkWin( cellX, cellY ){ var res = null; var newFig = getFig(cellX,cellY); if( ! newFig ) return false; var res; res = res || checkLine( cellX, cellY, 1, 0 );
让我们来看看机器人本身
因此，我们已经写了一个带有tic-tac-toe的页面。 我们完成了主要任务-AI。
如果您不知道怎么做，就不能只接受并编写代码：您需要考虑机器人的逻辑。
底线是分析运动场（至少是其中的一部分），并计算场上每个单元的
价格（权重） 。 重量最重-最有希望的单元将被机器人放置在那里。 主要困难在于计算一个细胞的重量。
术语学
十字架和脚趾是数字。
一次进攻将被称为并排在同一条线上的几个相同的人物。 实际上，这很多。 攻击的次数就是它的
威力 。 一个单独的部分也是攻击（力量1）。
在相邻的攻击单元（末端）上可能有空的单元或敌方碎片。 逻辑上可以认为，在“端”有两个空单元的攻击可以朝两个方向发展，这使其更具希望。 攻击“末尾”的空单元数将被称为其
潜能 。 电位可以是0、1或2。
我们将攻击表示如下：
[攻击力，潜力] 。 例如，
攻击[4：1] 。
图1.攻击[4：1]在分析过程中，我们将评估进入特定区域的所有单元格。 每个单元将计算其
重量 。 它是根据该单元影响的所有攻击的权重计算的。
分析的实质
想象一下，在运动场上已经有一个和第二个玩家进行了几次攻击。 其中一位球员出了招（让十字架）。 自然，他将自己移到一个空的单元格，因此他可以：
- 发展您的攻击，甚至可能不止一次，以增强攻击力。 可能会发起新的攻击等
- 防止发展或完全阻止敌人的进攻。
也就是说，我们的主角可以进攻和防守。 或者一次全部完成。 对他来说，第一和第二都很重要。
分析的实质如下：
- 机器人将其替换为选中单元格中的数字：首先是一个十字，然后是一个零。
- 然后，他搜索此类举动收到的所有攻击并总结其权重。
- 收到的数量就是电池的重量。
- 对运动场的所有单元执行类似的算法。
实际上，我们使用这种算法来检查如果我们这样走会发生什么……以及如果对手这样走会发生什么。 我们期待着一步，并选择最合适的电池-重量最大。
如果一个单元比另一个单元具有更大的权重，那么它会导致产生更多危险的攻击，或者阻止强大的敌人攻击。 一切都是合乎逻辑的……在我看来。
如果转到该页面并在控制台中写入SHOW_WEIGHTS = true，则可以直观地感觉到算法的操作（将显示单元权重）。
进攻权重
我动脑筋，带来了这样的攻击和重量对应：
ATTACK_WEIGHT = [[],[],[],[],[],[]]; ATTACK_WEIGHT[1][1] = 0.1; ATTACK_WEIGHT[2][1] = 2; ATTACK_WEIGHT[3][1] = 4; ATTACK_WEIGHT[4][1] = 6; ATTACK_WEIGHT[5][1] = 200; ATTACK_WEIGHT[1][2] = 0.25; ATTACK_WEIGHT[2][2] = 5; ATTACK_WEIGHT[3][2] = 7; ATTACK_WEIGHT[4][2] = 100; ATTACK_WEIGHT[5][2] = 200; ATTACK_WEIGHT[5][0] = 200;
根据经验选择-也许这不是最佳选择。
我为阵列增加了5的攻击力，而且重量过大。 这可以通过以下事实来解释：机器人分析游戏，向前看（将单元格中的数字替换）。 跳过这样的攻击不过是失败。 好吧，还是胜利……取决于谁。
具有高潜力的攻击的价值更高。
在大多数情况下，进攻[4：2]决定了比赛的结果。 如果玩家成功进行了这种攻击，那么对手将不再能够阻止它。 但是，这不是胜利。 即使我们在场上有[4：2]的攻击，敌人也可以更快地完成游戏，所以它的权重低于5的攻击力。请参见下面的示例。
图2.攻击[4：2]撕裂袭击
该段代码未列出。 在这里，我们介绍攻击分隔器的概念，并解释
“撕裂攻击”的本质。
请考虑以下情况：替换图形以删除几个空单元格（但不超过5个）时，将再定位一个。
而且，似乎在同一行上有两个相同的数字……在视觉上看起来像是攻击，但实际上并非如此。 这不是命令，因为此类“撕裂”攻击也可能带来潜在威胁。
特别是在这种情况下，对于每次攻击，我们都会计算除数。 最初，其值为1。
- 我们将“撕裂”攻击列为几种普通攻击
- 我们计算中心攻击和侧方之间的空单元数
- 对于每个空单元格，将除数增加1
- 我们照常计算中央攻击的权重，侧面攻击的权重-除以除数
图3.“ Torn攻击”分析。 扫描带有黄色叉号的单元格。因此，AI也将考虑到撕裂的攻击。 实际上，这将是普通攻击，但距离扫描单元越远，对其的影响就越小，因此权重也就越小（这要归功于分隔器）。
攻击搜索算法
首先，创建
一个攻击
类 。 该攻击将具有3个属性，这是我之前写的：
class Attack{ constructor( cap = 0, pot = 0, div = 1 ){ this.capability = cap;
一种将返回给定攻击的权重的
方法 ：
countWeigth(){ return ATTACK_WEIGHT[ this.capability, this.potential ] / this.divider } }
下一个 我们将搜索所有针对一个单元的攻击分为：
- 横向搜索
- 垂直搜索
- 45度对角线搜索
- 135度对角线搜索
所有这些都是
线路 ，可以概括搜索这些线路上的攻击的算法：
checkLine class 。
但是，我们不需要检查整个行。 我们感兴趣的最大攻击力是5。当然，有可能产生6的攻击力。 但是对于分析下一局游戏情况的AI来说，它等于6或5。获得其中一种攻击的可能性表明下一局游戏即将结束。 因此，在两种情况下，被分析单元的重量将相同。
类属性：
class checkLine{ constructor(){
必须停在这里，因为可能会出现问题：如果最大攻击力为5，为什么要检查第6个单元格。答案是确定远离攻击中心的潜在位置。
这是一个示例：图片中功率为1的攻击位于扫描区域的边界上。 要发现这种攻击的可能性，您需要“放眼国外”。
图 3.扫描第6个细胞。 如果不扫描第6个单元，则可能会错误地确定潜在的攻击可能性。
可能根本没有足够的空间来完成某些攻击。 在计算了攻击地点之后，我们可以提前了解哪些攻击是没有希望的。
图 4.攻击地点算法如下：
1）让我们从中央单元开始。 它应该是空的（我们要在其中移动，对吗？但是我们不要忘记，我们的AI必须替换此单元格中的数字来分析下一步移动。我们替换的数字是
this.subfig-默认为叉号。由于中心单元在替换后最初将包含某种形状，因此它将属于
this.curAttack的攻击：
- 其功率将不小于1（中央单元格中的数字）
- 分隔线-1，因为 这是一次集中攻击（它属于被扫描的单元）；
- 电位未知-默认值为0；默认值为0。
我们在默认的构造函数值中显示了所有这些点-参见上面的代码。
2）接下来，减少迭代器，在已扫描单元的一侧迭代5个以上的单元。
getAttacks函数
（cellX，cellY，subFig，dx，dy）对此负责，其中：
cellX，cellY-所检查单元格的坐标
subFig-我们在选中的单元格中替换的图
dx，dy-周期中x和y坐标的变化-这是我们设置搜索方向的方式：
- 水平（dx = 1，dy = 0）
- 垂直（dx = 0，dy = 1）
- 对角线45（dx = 1，dy = -1）
- 对角线135（dx = 1，dy = 1）
从某种意义上讲，这是平行于搜索线的向量。 因此，一个功能将能够在4个方向上搜索，而我们不会再次违反DRY原理。
功能码：
getAttacks( cellX, cellY, subFig, dx, dy ){ this.substitudeFigure( subFig );
请注意，如果checkCell（）返回某些内容，则循环停止。
3）我们检查这些单元格的数字。
checkCell（x，y）函数负责：
首先，将形状写入到
fig变量中：
Model.Field是我们的竞争环境。
checkCell( x, y ){ var fig = Model.Field[x] && Model.Field[x][y] !== undefined ? Model.Field[x][y] : 'b';
图可以是“ x”，“ o”，“ b”（边界），0（空单元格）。
4）如果在第5个单元格上该图与中心单元格重合，则攻击“搁置”在边界上，并确定攻击可能性，您必须“检查边界”（
this.checkEdge = true ）。
if( this.iter == 4 && fig == this.subFig )
checkCell功能已准备就绪。 但是，我们将继续处理
checkLine类。
5）完成第一个周期后，您需要“转身”。 我们将迭代器转换为中心和中心攻击（索引为0），将其从攻击数组中删除，并将其设置为当前攻击。
turnAround(){ this.iter = 1; this.checkEdge = false; this.curAttack = this.Attacks[0]; this.Attacks.splice(0,1) }
6）接下来，转到当前单元格的另一侧，增加迭代器。
绝对相同的数字检查。 （已编写代码
-getAttacks函数）
7）一切，我们将所有攻击集中在一个阵列中。
checkLine类就是这样
...一切都完成了。
好了，那么一切都很简单-为每条线（水平和垂直的两个对角线）创建一个
checkLine对象，然后调用
getAttacks函数。 也就是说，对于每一行-自己的
checkLine对象，以及相应的自己的攻击集。
让
getAllAttacks（）函数负责所有这些工作-已经与上述类分开；
getAllAttacks( cellX, cellY ){
在输出中，我们有一个对象，其中包含针对测试单元的所有攻击
但是，您可能已经注意到某种过滤功能。 它的任务是筛选“徒劳的”攻击：
- 零功耗（您永远不知道它们是否会进入阵列）
- 缺少空间的攻击（攻击场所<5）
- 零电位。
但是，如果攻击的功效大于5，则过滤器将跳过它。 该漫游器必须看到此类攻击，它们的筛选将导致游戏结束时出现干扰。
filterAttacks( attackLine ){ var res = [] if( attackLine.attackplace >= 5 ) attackLine.Attacks.forEach( ( a )=>{ if( a.capability && a.potential || a.capability >= 5 ) res.push( a ) }) attackLine.Attacks = res; return res }
断点
是的...再次抱歉！ 因此，当一个错误的举动决定了游戏的结果时，我们将这种情况称为游戏中的情况。
例如，攻击[3：2]是一个断点。 如果对手没有通过在其旁边放置一个棋子来阻止它，那么下一招，我们就已经在运动场上发动了进攻[4：2]-嗯，无论结果如何，比赛的结果都是决定的（在大多数情况下）。
或攻击[4：1]。 打哈欠-游戏可以轻松完成。
图5.断点一切都清晰易懂，并且上述算法已经能够考虑断点并及时阻止它们。 该机器人非常期待。 他将看到对手在下一回合能够发起攻击[5：1]，例如其体重为200-这意味着狡猾的书呆子将来到这里。
但是，想象一下一个球员设法在场上获得2个断点的情况。 显然，这没有给对手任何机会，因为 一口气，我们只能阻止一个断点。 如何教我们的AI阻止此类攻击？
图6. 2个断点很简单，当分析一个单元格时，在其中替换一个单元格时，我们将计算下一个回合将获得的断点数（机器人会看着前进，不要忘记）。 通过计算2个断点，我们将单元重量增加了100。
而现在，该机器人不仅可以防止此类游戏情况，而且还能够创建它们，这使其现在成为更强大的对手。
如何理解攻击是一个断点
让我们从显而易见的地方开始：任何幂为4的攻击都是一个断点。 错过的一招让我们有机会完成比赛，即 连续放置5件。
此外，如果攻击可能性为2，则我们将多花1圈来阻止此类攻击，这意味着存在一个断点，其功效为3。但是只有一个这样的断点-这是一次攻击[3：2]。
以及更困难的
“撕毁式攻击” 。
我们将只考虑中间有一个空单元的攻击，而不再考虑。 这是因为为了在中间有两个空单元来完成攻击，您需要花费至少2步-这显然不是断点。
我们记得，撕裂攻击被视为几种常规攻击：一次中央攻击和侧面攻击。 中央攻击属于已扫描的单元，侧面分配器有1个以上-这已在上面描述。
查找断点的算法（更轻松，请阅读下文）：
- 我们介绍可变分数
- 我们采取集中进攻，我们考虑力量
- 如果除数不超过2倍，则选择其中一个。
- 得分 -中央和侧面攻击力的总和
- 如果中央和侧面攻击的可能性为2，则要阻止此类攻击，您需要多转一圈。 因此，分数增加1
- 如果得分 > = 4，则这是一个断点
实际上，可以简单地列举断点，但断点并不多，但是我并没有立即理解这一点。
isBreakPoint( attackLine ){ if( ! attackLine || ! attackLine.length ) return false; var centAtk; attackLine.forEach( ( a )=>{ if( a.divider == 1 ) centAtk = a; }) if( centAtk.capability >= 4 ) return true if( centAtk.potential == 2 && centAtk.capability >= 3 ) return true; var res = false; attackLine.forEach( ( a )=>{ var score = centAtk.capability; if( a.divider == 2 ){
是的，我们最终将所有东西整合在一起
因此，上面描述了主要的地狱。 是时候从中塑造出一些有用的东西了。 函数
countWeight（x，y） -将单元格的坐标作为输入，并返回其权重。 她的内幕是什么？
首先，我们获得该单元所属的所有攻击的数组。 （
getAllAttacks（x，y） ）。 遍历所有行，我们计算断点的数量。 如果有两个断点，我们记得这种情况可以决定游戏的结果，并使单元重量增加100。
但是，所有断点必须属于一个玩家，因此我必须分两步实施检查：首先进行交叉，然后进行零。
由于在攻击权重数组（
ATTACK_WEIGHTS [] ）中，我没有提供6或更高
功效的攻击，因此我不得不用5的
功效替代攻击。这没有什么区别-它们都导致游戏结束。
好吧，我们总结一下攻击权重-仅此而已。
另一个要点是：为了使机器人在游戏结束时不会愚蠢，当它已经以4的幂进行攻击并考虑当前移动时，有必要显着增加单元的重量以完成这种攻击。 没有这个，AI可以简单地开始防御对手的“危险”攻击，尽管这场比赛似乎将获胜。 最后一步很重要。
countWeight( x, y ){ var attacks = this.getAttacks( x, y ) if( ! attacks ) return; var sum = 0; sum += count.call( this, attacks.x, '×' ); sum += count.call( this, attacks.o, '○' ); return sum function count( atks, curFig ){ var weight = 0; var breakPoints = 0; [ "0", "45", "90", "135" ].forEach( ( p )=>{ if( this.isBreakPoint( atks[p] ) ){ debug( "Break point" ) if( ++breakPoints == 2 ){ weight += 100; debug( "Good cell" ) return; } } atks[p].forEach( ( a )=>{ if( a.capability > 5 ) a.capability = 5; if( a.capability == 5 && curFig == Model.whoPlays.char ) weight += 100; weight += a.getWeight(); }); }) return weight } }
现在，当为特定单元格调用此函数时，我们将获得其权重。 我们对所有单元格执行此操作，然后选择最佳（权重最高）。 到那里去）
您可以在
github上找到其余的代码。 已经有很多资料，而且我还没有尝试过，它的呈现方式有很多不足之处。
但是，亲爱的读者，如果您能读到这一点，那么，我感谢您。我对结果的看法
下来吧 是的，您可以击败他，但是这样做对我个人而言有点麻烦。也许我只是不够小心。也尝试一下自己的力量。我知道这很容易，但是我不知道如何。我想听听知道或关注这种机器人其他实现的人们。我知道有什么更好的。是的...您可以使用众所周知的算法，例如minimax，但是为此，您需要具有博弈论领域的一些知识基础，但不幸的是，我对此并不吹嘘。将来，我计划将断点分析添加到几个步骤中，这将使该机器人成为更加严重的竞争对手。但是，我现在对此实施尚不明确。我只有即将举行的课程和不完整的文凭，这让我感到很难过。谢谢，如果您读完了。