时间戳

首页 > 解决方案 > 找到可以生成提供的 Connect-4 棋盘状态的任何一个移动序列

algorithm - 找到可以生成提供的 Connect-4 棋盘状态的任何一个移动序列

问题描述

给定矩阵 A(6x7) 中的有效Connect-4板状态，其中

A[i][j] = '0',  if empty,
A[i][j] = 'r',  if filled with red stone,
A[i][j] = 'y',  if filled with yellow stone.

我正在尝试考虑一种算法，该算法可以返回可以生成给定棋盘状态的任何有效移动序列。

可以假设红色总是开始游戏。

例子：

A = [0 0 0 0 0 0 0
     0 0 0 0 0 0 0
     0 0 0 y 0 0 0
     0 0 0 r 0 0 0
     0 0 0 y 0 0 0
     0 0 r r 0 0 0]

Valid sequence of moves:- 44443

44443 表示 ->
第一个玩家在第 4 列上移动，
然后第二个玩家在第 4 列上移动，...（以列号为 1-indexed）

我的方法:-
-) 首先通过非空位置数量的奇偶性找出最后一块石头的颜色。让那个颜色成为last_coloured。
-) 然后last_coloured从棋盘中取出一颗最上面的彩石，递归地继续前进，如果找不到彩石last_coloured则回溯。

虽然这种方法可以在不到 16^21 步内解决 7*6 板。
（编辑：感谢@Prune 纠正这个上限）

问题1）上述方法的步骤数是否有更好的界限？
问题2）有更好的方法吗？

标签： algorithmrecursion2d-games

解决方案

不要把它想象成 Connect-4，而是同一个棋盘上的单人纸牌游戏。你的目标是移除所有的石头。你有清除石头的规则；现在，如果你有一个很好的函数来评估任何棋盘位置，它会改进搜索树。

由于您交替去除颜色，因此您有

  • 规则：任何移除都​​必须至少露出另一种颜色的宝石
  • 启发式：在暴露的红色和黄色石头之间保持平衡
  • 启发式：如果一列只包含一种颜色的石头，那么从该列中移除一块石头是最后的手段。

这也将导致 eval 函数中的次要项：如果您的石头可用性不平衡，请确定需要奖励挖掘以获取稀缺颜色的列。

对于这么小的棋盘，我猜一个相对简单的启发式算法将为任何实际游戏位置提供有效的解决方案，而无需回溯：双方玩家的合理策略将促进易于导航的棋子组合。

这足以让你动起来吗？

推荐阅读