作者stimim (qqaa)
看板java
标题Re: 踩地雷 AI PK 赛比赛结果！
时间Wed Sep 29 01:30:00 2010
大家好，我是 GeminiAI 的作者 stimim ，
这次很幸运的在比赛中得到第二名真的很开心！！
大概说一下我的写法：
( 我的source code:
http://ppt.cc/wL@v )
CLASS 结构：
Square
|----UnknwonSquare
`----KnownSquare
|----MineSquare
|----NumberedSquare
`----ZeroSquare
Assumption
GeminiAI
Square 系列的类别都是用来存一个 Square 的资讯
其中，真正会用到的有：
UnknownSquare : 代表一个未知格
MineSquare : 地雷，会存这是谁的地雷
ZeroSquare : 1. 已打开的 0
2. 未打开，但没有地雷(由之後的运算得知)
NumberedSquare : 已打开的数字格
当AI被呼叫时，会用 Info.getMap() 得到的地图产生一个 Square[][] 的二维阵列
每一格都会是 Unknown , Mine , Zero , Numbered 的其中一种，
对每一格NumberedSquare都先呼叫 checkNeighbor 这个方法，他会：
this.neighbors = 空集合
this.totalNeighbors = this.leftMine = 0
对八个相邻格 v ：
1) v is an instance of UnknownSquare：
把 v 加入到 this.neighbors 中，
同时也把 this 加入到 v.neighbor 中
// neighbor 是一个 HashSet
this.totalNeighbors ++ ;
// 计录 neighbors 中的数量
2) v is an instance of MineSquare：
this.leftMine -- ; // 对这格来说，未找到的炸弹数少一个
这样一来，在处理完所有的数字格後，就会产生一个结构，存着 UnknownSquare 和
NumberedSquare 之间的关系，这在之後要算机率时会用到。
接下来，对每一个 NumberedSquare ，呼叫 checkTrivial 这个方法：
这个方法是用来处理一些很简单的情况：
Ex1:
. ? ? // ? : 已知不是炸弹
? 1 ? // . : Unknown
? ? ? // 很明显的 . 一定是一颗炸弹
Ex2:
* . . // * : 已知是炸弹
. 1 . // . : Unknown
. . . // 可知图中的 . 皆不是炸弹
也就是判断 leftMine == totalNeighbor 或 leftMine == 0
当我们由此找到一个非炸弹或炸弹格时，还有一些格子也会受到影响：
Ex3:
1 ? ? 因为
. 一定是炸弹(由
1得知)
. 2 ? 使得
. 也一定是炸弹
1 .
.
格子之间的影响关系为：
1 -> 1 -> 2 //
1让1可以确定.不是炸弹，进而让2确定
.是炸弹
因此，当我们发现某一个 NumberedSquare u 的邻格都是或都不是炸弹时，要：
产生一个 updateList
对 u.neighbors 中的所有 UnknownSquare v ：
把 v.neighbors 加入 updateList
把 v 换成 Zero 或 Mine
把 updateList 中的 u 去掉
对 updateList 中的所有 NumberedSquare v ：
v.checkNeighbors
对 updateList 中的所有 NumberedSquare v ：
v.checkTrivial
当我们完成以上的程序後，我们可能已经找到一些地雷了，也可能没有，这时就要计算
每一格 UnknownSquare 是地雷的机率
(机率算法待补)
当所有机率都算出来了以後，我的做法是帮每一个 UnknownSquare 打两个分数：
1. 我要不要把他当成炸弹来踩？
public double scoreUnknown(UnknownSquare square) {
double isMineChance = square.isMineChance;
if (isMineChance >= 0.99)
return 10000.0 + isMineChance * 10000.0;
if (isMineChance >= 0.799999)
return 4000.0 + isMineChance * 10000.0;
if (isMineChance >= 0.499999)
return isMineChance * 10000.0 * (1 - isBlank(square));
/*
* if( isMineChance >= 1/3 ) return 500.0 + isMineChance * 10000.0 ;
*/
return isMineChance * 9000.0 * (1 - isBlank(square));
}
其中，isBlank 算的是他的邻格都不是炸弹的机率，这会对他的分数造成影响
2. 假设他不是炸弹，踩他好不好？
public double scoreZero(Square square) {
double score = 0;
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (dx != 0 || dy != 0) {
int x_ = square.x + dx;
int y_ = square.y + dy;
if (x_ >= 0 && x_ < gameInfo.getWidth() && y_ >= 0
&& y_ < gameInfo.getHeight()) {
if (map[x_][y_] instanceof KnownSquare)
score += 500;
if (map[x_][y_] instanceof UnknownSquare) {
double chance =
((UnknownSquare) map[x_][y_]).isMineChance;
if (chance <= 0.05 || chance > 0.99)
score += 700;
}
if (map[x_][y_] instanceof MineSquare) {
score += 900;
}
} else {
score += 600;
}
}
}
}
return score * (1 - isBlank(square));
}
基本上就是，他的邻居中有越多已知是炸弹的越好，如果有那种几乎可以确定是或不是
炸弹的也不错，其他的就乱给分 XDD
最後还要考虑四周没有炸弹的情况来调整分数。
可以发现当是炸弹的机率> 0.8 时，大概都会给他猜下去，其他的状况就看谁的分数高
来决定踩谁(分数一样时，机率均等)
不过现行的打分数方式其实我不是很喜欢，毕竟机率都算出来了，应该有更好的算法
想法一： A格的期望值
Score(A) = A.p * ( 1 + Σv.p(A是炸弹) ) - (1-A.p) * ( Σv.p(A不是炸弹) )
A.p : A 是炸弹的机率
v.p( A 是 炸弹 ) : 已知 A 是 炸弹 时，v 是炸弹的机率
v.p( A不是炸弹 ) ：无知 A不是炸弹 时，v 是炸弹的机率
v 是 A 以外的 UnknownSquare
这样应该可以有更好的评估，不过实在是懒得写……可能之後有空的话会再来写写看
// 机率计算的部份待补，先来去睡~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.153.118
1F：推 GoForward:谢谢不吝分享! 09/29 02:14