LolAI 的设计 1. 对每一格作以下的分析 a. IF 这一格已经被标为地雷 OR 已知这一格是空白 (数字零) THEN 略过这格 (因为这格并不能告诉我们什麽资讯) b. IF 这一格是未知状态 AND 所有的邻居中没有任何已知格 THEN 把这格加入 wagCandidate 这个 collection 後结束对这格的分析 (因为我们没办法作任何 educated guess, 所以把这格加入 Wild Ass Guess Candidates XD) c. (如果我们到了这里，代表这格通过了前面两个检查 易言之，这一格没有地雷，但我们知道他的邻局里有地雷 (这一格有非零的数字) 这一格可以提供有用的资讯) c.1 计算这一格的邻居里确实有多少地雷 * 我们知道这格的数字 (代表着他的邻居里总共有几颗雷) * 我们看得到这格所以的邻居的状态 (所以我们知道有哪几个邻局是未知， 有哪几个邻居是已知雷) -> 是故，我们知道「这格的未知邻居里有几个雷」 例: ? ? ? ? 3 _ X _ _ X 代表已知雷 _ 代表空白格 ? 代表未知格 那我们就知道那四个 ? 中有至少两个雷，且，至多两个雷 c.2 把 c.1 的计算结果用以下的方式记录起来 { min <= [? ? ? ... ?] <= max } 那些 ? 是 (x,y) 的形式，也就是该 ? 格的座标 易言之，我们可以用上面这个方式把我们对目前棋盘上的状态通通写下来 以 c.1 里的例子而言，我们写下来的 clause 就会像这个样子 { 2 <= [ (0,0) (0,1) (1,0) (2,0) ] <= 2 } 用中文说的话，上面这个 clause 就代表 「在 (0,0) (0,1) (1,0) (2,0) 这几格中，有至少两个雷，有至多两个雷」 我们会把场面上所有数字不为零的格子都如此分析一次 然後把所有的 clause 都存起来 这些 clause 就是 LolAI 表示「资讯」的方式 ========================================================================= 2. 用 deduction 的方式，从所有已知 clause 中萃取出最重要的资讯 假设有以下的情形 _ _ ? _ 1 ? _ 2 ? _ _ ? 当我们用上述第一节里提到的方法分析这个棋盘时 我们会从 (1,1) 这格得到这个 clause: { 1 <= [ (2,0) (2,1) (2,2) ] <= 1} 我们暂且将此 clause 称作 C1 我们会从 (1,2) 这格得到这个 clause: { 2 <= [ (2,1) (2,2) (2,3) ] <= 2} 我们暂且将此 clause 称作 C2 以下我将解释 deduction 的演算法， LolAI 的成败就在於此演算法上 为了简化文字描述，我将 clause 的表示方法以 Java code 定义如下 class Clause { int min; int max; Set<Cell> cells; // 注意，这是个 set , 等一下我们将会利用 set 的计算 } 以 C1 为例， C1.min == 1 C1.max == 1 C1.cells == [ (2,0) (2,1) (2,2) ] 从 C1 与 C2 这两个 clause 里，我们可以知道三件事 #1 在 C1 与 C2 共有的格子 (cell) 中，至少及至多有几个雷 #2 在 C1 独有的格子中，至少及至多有几个雷 #3 在 C3 独有的格子中，至少及至多有几个雷 易言之， #1 代表 C1.cells ∪ C2.cells 的部分 #2 代表 C1.cells - C2.cells 的部分 #3 代表 C2.cells - C1.cells 的部分 易言之，从 C1 及 C2 这两个 clause 中，我们可以算出三个新的 clause 让我们称他们为 N1, N2, N3 在这里我将先略过数学上的推演，直接告诉你最後推导出来的算式 因为我已经打字打得快发疯了 XD 如果你能独立的推导一次来验证这个算式的话，那是再好也不过的了 N1.cells = intersection(C1.cells, C2.cells) N2.cells = C1.cells - C2.cells N3.cells = C2.cells - C1.cells N1.min = max(0, max(C1.min - N2.cells.size, C2.min - N3.cells.size)) N1.max = min(N1.cells.size, min(C1.max, C2.max)) N2.min = max(0, C1.min - min(N1.cells.size, C2.max)) N2.max = min(N2.cells.size, C1.max - max(0, C2.min - N3.cells.size)) N3.min = max(0, C2.min - min(N1.cells.size, C1.max)) N3.max = min(N3.cells.size, C2.max - max(0, C1.min - N2.cells.size)) OMG... 在重新检视这段 code 时，我找到 LolAI 之前的 bug 了… 又是个天杀的 copy&paste error... orz 现在 LolAI 的 clause deduction 就应该完全正确了… orz 如果我没有打错字的话，用这个演算法，从 C1 与 C2 你会得到 N1.cells = (2,1) (2,2) N2.cells = (2,0) N3.cells = (2,3) N1.min = 1 N1.max = 1 N2.min = 0 N2.max = 0 N3.min = 1 N3.max = 1 易言之 N1: { 1 <= [ (2,1) (2,2) ] <= 1 } N2: { 0 <= [ (2,0) ] <= 0 } N3: { 1 <= [ (2,3) ] <= 1 } 用中文说出来的话，就是 N1: 在 (2,1) (2,2) 里，至多有 1 雷，至少有 1 雷 N2: 在 (2,0) 里，至多有 0 雷，至少有 0 雷 N3: 在 (2,3) 里，至多有 1 雷，至少有 1 雷 至此，我们已经从 C1 与 C2 中萃取出了更重要的资讯 所以，把所有的 clause 互相进行 deduction 的动作後 我们可以找出这些 clause 一开始没有直接告诉我们的事 在这里我略去了「把所有的 clause 互相进行 deduction 的动作」的详细步骤 重点是，必须一直把新生出来的 clause 正确地与现有的 clause 融合 然後重覆进行这步骤，直到没有新的 clause 可以从已知的 clause 被算出来 还要适当地丢弃完全无用的 clause 这一段是吃 CPU+memory 最重的地方，我为了 optimize 这段花了不少心力 甚至生出了一些 bug 所以我先不想多谈这部分的架构 (而误导你)，或许你独立生出来的架构会更好 ======================================================================== 3. 我想，看到这里你已经了解接下来要作什麽了 第二节所提到的是 AI 的脑的肉体 而第三节 (也是我之前没有足够时间彻底研究的) 则是 AI 的灵魂 (人格) 首先，以上述我们知道的 N1 N2 N3 来看 很明显地 N3 是已知解 ( N3.min == N3.cells.size == N3.max ) 所以我们应该先把 N3.cells 里的格子先喂给 game driver 而比较 N1 与 N2 可以知道，在 N1 里面挑一个猜至少有 50% 的命中率 所以我们应该先猜 N1.cells 里的东西 而 C1 与 C2，如果你的 deduction engine 写得正确的话，应该要被丢掉 因为他们没有比 N1 N2 N3 来得严谨 当你把所有最精萃的 clause 找到时， 此 AI 就具有人类玩家在这游戏里的思考能力 不能必胜，但 This is the best it can get. 而现在回头来看，LolAI 的惨败并是应该的 因为 LolAI 并没有适当地丢掉无用的 clause 且 LolAI 并没有正确地在 wagCandidate 与非已知解的 clause 中做出正确的选择 是故， LolAI 死好 XD 如果要作出最强的 AI ， 这一部分的重要性不输给上面第二节所提到的 clause deduction 易言之，就是当 AI 把所有已知解都喂给 game driver 後 接下来 AI 如何从不确定解里挑出最好的 guess, 这就是决定胜负的地方 =============================================================== 如同 tkcn 所说的，如果能合作写 AI 的话将会是一大乐事 希望上述对 LolAI 的解析能派上用场，提供给读者一个优良的踏脚石 (欢迎索取我的程式码作参考 :) 不用担心什麽智财权什麽鬼的，想怎麽用就怎麽用 LolAI 程式码直接释出在 public domain) (如果可以的话，我希望在这个联合 AI 的制作过程中先不要去 winmine 找资料 我想要 beat winmine 板板友 fair and square :) ) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 65.87.177.87 ※ 编辑: AmosYang 来自: 65.87.177.87 (09/24 15:09) ※ 编辑: AmosYang 来自: 65.87.177.87 (09/24 15:27) ※ 编辑: AmosYang 来自: 65.87.177.87 (09/24 15:36)