作者stimim (qqaa)
看板java
标题GeminiAI 的设计逻辑 (下)
时间Wed Sep 29 09:25:18 2010
其实在大约两年前我曾经写过一个自动玩 游乐场 中的踩地雷程式
程式Demo:
https://www.youtube.com/watch?v=8H5izBQEB7U
而这次的 AI 中的机率计算基本上也是用之前的大架构，
只是实作上比较OO (之前是很多Global Variable和错纵复杂的function call...)
--------------------
在上一编中，我对每一格 NumberedSquare 都做了 checkNeighbor 的动作，
在每一个 NumberedSquare 和 UnknownSquare 中，都有一个HashSet neighbors：
numberedSquare.neighbors 是一些 UnknownSquare ，代表受他限制的
UnknownSquare 有哪些
unknownSquare.neighbors 是一些 NumberedSquare ，代表他受哪些
NumberedSquare 限制
而checkNeighbor 就是在建立这些关系：
Ex1:
1 ? // ? 是 UnknownSquare
1 ?
1 ?
1.neighbors = {
? ,
? }
?.neighbors = {
1 ,
1 }
1.neighbors = {
? ,
? ,
? }
?.neighbors = {
1 ,
1 ,
1 }
1.neighbors = {
? ,
? }
?.neighbors = {
1 ,
1 }
当所有的 NumberedSquare 都呼叫过 checkNeighbor 後，这些关系就建立好了
接下来则是要把地图分成几个区块 (在我的程式中称为section)
为什麽要画分 section 呢？因为在地图上并不是所有的格子都会互相影响：
Ex2:
1 . 2 . // . 是 UnknownSquare
. . . . 可以发现，
绿色区的炸弹分布方式并不会影响
黄色区的炸弹分布
. . . .
绿色区有6种可能的排列，
黄色区有3种，分开算的话就只要算9
2 . . . 种，一起算的话则是 6*3 = 18 种，当地图越大时，差别越明显
numberedSquare.belongsTo 是一个 Set 的 Reference ，代表他属於哪一个section
belongsTo 的初始值为 null ，建立 section 的方式为：
unknownSquare.unionNeighbors() 这个方法会把 unknownSquare.neighbor 中的
NumberedSquare 合并到同一个 Section
对 UnknownSquare v 来说 若 u1, u2 都属於 v.neighbor
则 u1 , u2 属於同一个 Section ，因为他们的邻格会互相影响
unionNeighbors:
对 u 属於 v.neighbor
result = u.belongsTo 的 size > result 的 size
result = u.belongsTo
如果所有的 u.belongsTo 都是 null ：
result = new Set
把 v.neighbor 中的其他 section 加到 result 中
// 也就是：result.addAll( u.belongsTo )
对 u 属於 result ：
u.belongsTo = result
现在我们有了一些 section 了以後，就可以藉由枚举所有可能来计算未知格是炸弹
的机率：
computeProb( section ):
对於 NumberedSquare v 属於 section
如果 v.makeAssumption() 成功：
如果 section 中的所有格子都已经有 assumption 了：
计录现在的 assumption
否则：
前往下一个 v
否则：
到目前为止的 assumption 是有问题的，回到上一个 v
当以上的假递回跑完了以後，我们应该就计录了一些 assumption ，这些都是可能的
分布方式，由此可以算出 unknownSquare 是炸弹的机率
unknownSquare 是炸弹的 assumption 数
p = -------------------------------------
全部的 assumption 数
------------------------
PS:
画分 section 的做法是在两年前想到的，因为 16 x 30 的地图很大，当开出来的
格子变多时，如果还是当成同一个 section 来算机率，会慢很多
如果 section A 有 50 种可能
section B 有 50 种可能 => 分开: 100 种 ， 合起来: 2500 种…
不过，这次比赛的地图只有 16 x 16 ，就算全部一起算也不会慢太多就是了。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.4.182