作者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