對戰踩地雷 AI 設計 (3)

當初開始寫這系列文章時，我只打算用二至三篇文章介紹我所使用的方法，第一篇是辨識出確定的地雷，第二篇則是使用機率去猜比較有可能是地雷的格子。然而在我開始著手第二篇文章時，我發現我在程式中所使用的機率完全不正確，既然如此，似乎也沒有什麼寫出來的必要？因此我在第二篇中另闢戰場，用正確的機率做了些簡介，並且在文章結尾埋了令人玩味的梗：最強 AI 設計！。

這裡的最強當然不是指此次比賽的結果，我設計的 AI 在比賽結束後不久即已被超越(詳見 PTT Java 板踩地雷系列文章)，並且也被人類玩家慘電，實在距離所謂的 "最強" 非常遙遠。既然如此，我所說的最強指的是什麼呢？這個最強必須建立在一個難以達到的前提之下：如果我能夠知道每一個格子為地雷或各數字的的機率。

在上一篇文章中可以看到，只要不是在開場的兩步之內，想要計算出完全正確的機率是非常困難的。但是，如果我假設能夠算得出來呢？

如果我能夠知道目前地圖上每一個格子為地雷及各數字的機率，我便能夠算出「假如我猜錯了，我的對手猜中地雷的機率」，甚至繼續計算「如果我的對手也猜錯了，我這次猜中的機率是多少」，然後再繼續……。雖然可以一直算到遊戲結束，不過以踩地雷這遊戲的特性來看，算到兩、三步之後意義應該就不大了。

我們用期望值來表示，下在 A 猜中地雷的期望值設為 E[A]，而在這一步之後對手利用 A 的數字猜中地雷的期望值為 E'[A]，於是一個理想的 AI 便誕生了：

雖然這公式看起來很簡單，並且可能還存在漏洞，但是我認為已經足夠了。

註：由於我並沒有考慮到第二步的情形，因此當 E[A] > E'[A] 成立時，有可能 E'[A] > E''[A]，此時反而會讓自己進入不利情況。反過來看，當 E[A] > E'[A] 不成立時，也有可能出現 E'[A] < E''[A]，使得自己的情況比對手更好。

幻想完了，讓我們回到現實，雖然沒有辦法計算出完全正確的機率，但有沒有辦法取得估計值呢？我認為 PTT Java 板 stimim 的文章(#1CefM1Hg)是個很好的出發點，如果能夠正確解決我所提出的問題(#1CerxcHD)，應該會有不錯的成果。

這系列文章到此算是暫時的告一段落，未來如果還有文章，應該會是我照著上述策略實作時的心得或是其它發現吧。

對戰踩地雷 AI 設計 (2)

在套用機率來設計 AI 之前，讓我們來看看機率能夠做到什麼程度。

先來考慮最簡單的場景: 開局，在開局的第一手裡，無論下在哪，踩中地雷的機率都是 51/256 = 0.199219。但若是沒有踩中地雷呢？我們考慮以下三種情形:

1. 下在角落: k=3
2. 下在邊緣: k=5
3. 下在其他位置: k=8

註: k 為鄰居數量

代入公式 C(k, n) * C(256-k-1, 51-n) / C(256, 51)
我們可以算出下了第一步之後，出現各種數字的機率，便可以得到以下的表格:

各數字出現機率:

數字	角落(n=3)	邊緣(n=5)	其他(n=8)
0(空白)	0.408787	0.259806	0.130630
1	0.309626	0.331252	0.270543
2	0.076263	0.164802	0.239116
3	0.006106	0.039977	0.117756
4	0.000000	0.004726	0.035327
5	0.000000	0.000218	0.006608
6	0.000000	0.000000	0.000752
7	0.000000	0.000000	0.000048
8	0.000000	0.000000	0.000001

根據經驗，開局時有兩種情形特別糟糕，一是點出的數字剛好等於 k，這表示對手要收下這 k 枚地雷了，好在這種情形發生的機率並不高。第二種情形是點到空白，這時候通常都會炸出一片空地，雖然不是絕對，但對手多半也是能輕鬆取分。

而根據上面的表格，只要第一步下在角落、邊緣以外的位置，就能將發生這兩種情形的機率降到最低。因此機率告訴我們的第一件事，就是開局時不要下在角落和邊緣。


接下來換到對手的角度，如果對方(開局者)第一步沒有踩到地雷，又該如何應對？
註: 此處我們假設對手也知道第一手不下在外圈比較好，所以僅考慮此種情形之機率。

如果出現的數字為 n，且考慮只下在此數字的八個鄰居時，踩中地雷的機率為 n/8。
踩該數字上下左右四個鄰居而該位置是空白的機率: (C(3,n) * C(244,51-n)) / (C(8, n) * C(247,51-n))
而下在斜角位置卻是空白的機率則為: (C(5,n) * C(242,51-n)) / (C(8, n) * C(247,51-n))
計算之後將可得到以下表格:

數字	踩中地雷機率	踩數字上下左右炸開機率	踩數字斜角炸開機率
1	0.125000	0.189666	0.199619
2	0.250000	0.055024	0.117023
3	0.375000	0.009311	0.060020
4	0.500000	0.000000	0.024623
5	0.625000	0.000000	0.006313
6	0.750000	0.000000	0.000000
7	0.875000	0.000000	0.000000
8	1.000000	0.000000	0.000000

但這時候如果另闢戰場去踩新的區域:
踩中地雷機率為: (51-n) / (256-9)
炸開機率為: C(256-9-9, 51-n) / C(256-9, 51-n)

數字	踩中地雷機率	炸開機率
1	0.202429	0.125727
2	0.198381	0.131714
3	0.194332	0.137954
4	0.190283	0.144454
5	0.186235	0.151225
6	0.182186	0.158277
7	0.178138	0.165620
8	0.174089	0.173264

機率教會我們的第二件事，就是當出現數字為 1 時，請選擇另闢戰場；其餘情況則猜上下左右。


沒有數字和只有一個數字的情況我們已經考慮完了，該是時候面對現實了，來看看兩個數字的情形吧:

在上圖左上角的三個未開區域中，可能的解共有兩組，分別是 "左右兩邊各一枚地雷" 和 "只有中間有地雷"，
假設在這地圖上共剩下 27 個未開點 (含左上角那三個)，並還有 10 個未找出之地雷。

此時在三格中出現一個地雷的組合數是: C(3,1) * C(24,9)，機率為: 0.640000，
而出現兩個地雷的組合數是: C(3,2) * C(24,8)，機率為: 0.360000，
雖然在這個例子中地雷出現在中間的機率較高，但是一旦猜錯將立刻奉送對手兩枚地雷，因此在猜與不猜之間仍需仔細拿捏。


再來看看更複雜的例子:

在上圖的場景中，可能的解變得更多了，A,B,C 區塊各自的地雷數量可能是: (2,0,3), (1,1,2), (0,2,1)。

只要分別找出數字 2 和 3 他們共有的鄰居(B)及獨有的鄰居(A 和 C)，並且使用前面提過的機率公式，我們一樣能夠計算出每一種解出現的機率，並且推測出最有可能是地雷的位置。然而這些公式都是建立在我們能夠算出其餘未開區域出現各種地雷數量之機率的前提下，但是在實際對戰中，這種情形幾乎不可能出現。而數字的牽扯也經常不只有兩個，更多的數字將會讓公式變得非常複雜。

到此為止，真實機率的計算可說是宣告失敗了，所以這篇就在此打住吧，不過下一篇將會看到機率的反擊: 最強 AI 設計。

對戰踩地雷 AI 設計 (1)

日前 PTT Java 板舉辦了一場懸賞踩地雷 AI 的活動，我也被主辦人 PsMonkey 脅迫參加，開發了自己的 AI，並且在 AI 之間的 PK 獲得了不錯的成績。然而當對戰於真人對手時，所有人的 AI 都明顯屈居下風，面對人類高手時，甚至是被打得毫無招架之力。(參看排行榜)

為了促進 AI(s) 的進步，在這篇文章中我將會分享我的想法與程式碼，歡迎隨意取用。


在開始之前，先讓我做些定義:
    num(x,y): 表示在地圖 (x,y) 位置所顯示的數字，也代表在其周圍九宮格內的地雷數量。
    numUnknown(x,y): 表示地圖 (x,y) 周圍九宮格內 "未開" 的數量。
    numCommonUnknown(x1,y1,x2,y2): 表示地圖上 (x1,y1) 和 (x2,y2) 共同鄰居中未開的數量。
    numMine(x,y): 表示地圖 (x,y) 周圍九宮格內，"已經被點開" 的地雷數量。

而關於圖形的說明如下:

    灰色格子: 表示尚未點開
    白色空格: 表示周圍無地雷
    數字k: 表示周圍有 k 個地雷
    ?: 表示已經點開，但究竟是空格或著數字是多少我們並不關心
    X: 表示已經點開的地雷


我將踩地雷 AI 的任務分成兩個部份，第一個部份是試著找出確定為地雷的位置，在這個部份中，一旦能夠確認出地雷位置，就可以肆無忌憚的選取該位置。而當地圖上的資訊不足以確切的判斷出地雷的位置時，我將這種情況歸類為第二部份。

此篇文章將只說明第一部份，第二部份留待下一篇文章。

場景1:

在第一個部份中，最簡單的狀況就像是上圖這樣: 當 num(x,y)-numMine(x,y) 等於 numUnknown(x,y) 時，表示這些未開都是地雷。

這種情況在 AI 的實作非常直覺，因此就略過不提。

場景2:
然而並不是每個情境都這麼簡單，例如下面這張圖。

在上圖中，單考慮數字 2 並沒有辦法辨別出那一個位置才是剩餘的地雷，然而連數字 1 也一起考慮時，我們便能夠確定位置 (1,2) 一定不是地雷，進而確定地雷的位置在 (1,1)。

遇到這種情況時，我的處理方式是，找出所有確定不是地雷的位置，並且將它們做上標記，如此一來就有機會將場景 2 變為場景 1。

到目前為止，處理第一部份的 Pseudo Code 會是這樣:

    do{
        // 處理場景 1
        // 處理場景 2
    } whlie 當場景 2 辨識出新的 "確定不是地雷的未開區域" 時繼續

場景3:
接下來這種場景也很容易見到，但就不是那麼容易處理了。

只看數字 2 時，我們只能知道位置 (1,1), (1,2), (1,3) 之中有兩個地雷，卻沒有辦法得知究竟是哪兩格。然而考慮數字 1，我們能判斷出在位置 (1,2) 和 (1,3) 中只有一格是地雷，因此可以確定 (1,1) 也是地雷。

在這個場景中，因為數字 1 的所有鄰居也都是數字 2 的鄰居，並且數字 1 沒有其他未開鄰居，因此雖然我們並不知道在這些共同鄰居中，哪些點才是地雷，但是卻能知道其中地雷的數量有多少。利用這些資訊，就能夠算出數字 2 獨自擁有的鄰居中有多少地雷，如果地雷數等於獨自擁有的未開鄰居數，那麼...bingo! 這些數字 2 獨有的未知鄰居全都是地雷。

程式部份我是這樣寫的，首先我掃遍地圖中所有位置為數字的格子 A，對每一個符合的格子再進一步找出另一個可能與它有共同鄰居的數字格子 B。(很顯然，A 與 B 的距離一定是兩步之內，因此我只需要掃的 A 週邊共 24 個格子即可。)接下來只要檢查 numUnknown(A)-numUnknown(A,B) 是否等於 num(A)-num(B)，如果成立，則表示 A 獨有的鄰居都是地雷，讓 AI 隨便從中選一個吧！

加上場景三，Pseudo Code 變成這樣:

    do{
        // 處理場景 1
        // 處理場景 3
        // 處理場景 2
    } whlie 當場景 2 辨識出新的 "確定不是地雷的未開區域" 時繼續

以上就是我設計的 AI 對於第一部份的處理。

根據我開發時的測試，我認為場景三的處理是我的 AI 能夠領先其他 AI 的關鍵。

下一篇將繼續討論第二部份，當無法找出確定地雷時的策略與機率。

[GWT] GWTCanvas 簡易範例

GWTCanvas 是 Google Web Toolkit Incubator 的一個子項目，其作用是提供了操作 HTML5 Canvas 的 API 供 GWT 使用。

在官方的 wiki 上可以看到簡易的操作說明，因為並不複雜，所以這裡就不多做說明了。有興趣者也可以參考 API。


接下來我利用 GWTCanvas，配合 UiBinder, Timer，試著寫了一個 Bubble Sort 的教學範例，其功能就像是以往常見的 Applet。(由於此篇文章的重點是在於 Canvas 而不是 Bubble Sort，所以請原諒我只撰寫了非常陽春的 Demo)

完整的專案可以在此下載: canvas.zip

程式碼內容如下: BubbleSortDemo.java

package canvas.client;

import com.google.gwt.core.client.EntryPoint;
import com.google.gwt.core.client.GWT;
import com.google.gwt.event.dom.client.ClickEvent;
import com.google.gwt.uibinder.client.UiBinder;
import com.google.gwt.uibinder.client.UiFactory;
import com.google.gwt.uibinder.client.UiField;
import com.google.gwt.uibinder.client.UiHandler;
import com.google.gwt.user.client.Timer;
import com.google.gwt.user.client.ui.Button;
import com.google.gwt.user.client.ui.HTMLPanel;
import com.google.gwt.user.client.ui.RootLayoutPanel;
import com.google.gwt.widgetideas.graphics.client.Color;
import com.google.gwt.widgetideas.graphics.client.GWTCanvas;

public class BubbleSortDemo implements EntryPoint {

    interface uiBinder extends UiBinder<HTMLPanel, BubbleSortDemo> {
    }

    private static uiBinder uiBinder = GWT.create(uiBinder.class);
    
    @UiField GWTCanvas canvas;
    @UiFactory GWTCanvas makeCanvas(int width, int height) {
        return new GWTCanvas(width, height);
    }
    
    public static final int LENGTH = 10;
    
    private Timer t;
    private int i;
    private int j;
    private int[] arr;

    @UiField Button nextBtn;
    @UiField Button playBtn;
    @UiField Button stopBtn;
    @UiField Button resetBtn;
    
    private void initArray(){
        arr = new int[LENGTH];
        
        for(int i=0;i<LENGTH;i++){
            arr[i] = (int)(Math.random()*100); 
        }
    }

    private void initVariable() {
        i = LENGTH-1;
        j = 0;
    }
    
    private void display(){
        canvas.clear();
        
        for(int i=0;i<LENGTH;i++){          
            int gray = arr[i]*2;
            canvas.setFillStyle(new Color(gray, gray, gray));

            int height = arr[i];
            int x = 30+i*30;
            int y = 130-height;
            canvas.fillRect(x, y, 20, height);
        }
    }   
    
    private void swap(int a, int b){
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t; 
    }

    @Override 
    public void onModuleLoad() {

        HTMLPanel outer = uiBinder.createAndBindUi(this);
        RootLayoutPanel.get().add(outer);
        
        initArray();
        
        display();

        /*
        // This is the original version bubble sort.
        for(int i=LENGTH-1;i>=0;i--){
            for(int j=0;j<i;j++){
                if(arr[j]>arr[j+1]){
                    swap(j, j+1);
                }
            }
        }
        */

        initVariable();
        
        t = new Timer() {
            public void run() {
                while(i>=0){
                    
                    while(j<i){
                        
                        if(arr[j]>arr[j+1]){
                            swap(j, j+1);
                        }
                        
                        display();
                        
                        j++;
                        return;
                    }
                    
                    i--;
                    j = 0;
                    return;
                }
                
                t.cancel();             
            }
        };
        
    }
    
    @UiHandler("nextBtn")
    void handleNext(ClickEvent e){
        t.run();
    }
    
    @UiHandler("playBtn")
    void handlePlay(ClickEvent e){
        t.scheduleRepeating(500);
    }
    
    @UiHandler("stopBtn")
    void handleStop(ClickEvent e){
        t.cancel();
    }
    
    @UiHandler("resetBtn")
    void handleReset(ClickEvent e){
        initArray();
        initVariable();
        display();
    }

}

其對應的 UiBinder: BubbleSortDemo.ui.xml

<!DOCTYPE ui:UiBinder SYSTEM "http://dl.google.com/gwt/DTD/xhtml.ent">
<ui:UiBinder xmlns:ui="urn:ui:com.google.gwt.uibinder"
 xmlns:g="urn:import:com.google.gwt.user.client.ui" xmlns:graphics="urn:import:com.google.gwt.widgetideas.graphics.client">
 <ui:style>  
  .canvas{
   border: solid 1px black;
  }
 </ui:style>
 <g:HTMLPanel>
  <graphics:GWTCanvas ui:field="canvas" styleName="{style.canvas}" width="350" height="200"></graphics:GWTCanvas>
  
  <br />
  <g:Button ui:field="nextBtn">Next</g:Button>
  <g:Button ui:field="playBtn">Play</g:Button>
  <g:Button ui:field="stopBtn">Stop</g:Button>
  <g:Button ui:field="resetBtn">Reset</g:Button>
 </g:HTMLPanel>
</ui:UiBinder> 

[Java] Concurrency in Swing

參考 Java Tutorials 的 Concurrency in Swing 章節所寫的筆記。

一個好的 Swing 程式會利用 concurrency 去建立不會 "凍結" 的 UI — 無論程式正在做什麼，都會回應使用者的操作。

一個 Swing programmer 將需要處理以下三種類型的 thread:

1. Initial thread:
   啟動應用程式的 thread
   
2. Event dispatch thread:
   所有的 Event-handling 程式都位於此 thread，大部分與 Swing 互動的程式也在此 thread 上執行。
   
3. Worker thread:
   也稱做 background thread，需要消耗較長時間的 task 位於此 thread。
   

一個 Swing 程式應該這樣寫:

1. Initial thread 沒有太多事要做，它最主要的工作就是建立一個 Runnable 物件負責建立 GUI，並且將這個物件交由 event dispatch thread 負責執行。 
    
2. 將建立 GUI 交由 event dispatch thread 負責的方法為 javax.swing.SwingUtilities.invokeLater 或著 javax.swing.SwingUtilities.invokeAndWait，這兩個 method 都傳入一個 Runnable 物件。它們的差別在於 invokeLater 只會將工作加入排程後便返回，而 invokeAndWait 將會等待工作執行結束後才返回。
        
3. 在 Applet 中，應該在 init 方法中呼叫 invokeAndWait，否則 init 可能會在 GUI 建立完成前就返回，這將可能造成瀏覽器啟動 applet 時的問題。
        
4. 在其他類型的程式中，建立 GUI 通常都是 initial thread 中的最後一項工作，因此無論呼叫 invokeLater 或 invokeAndWait 皆可。
   
5. 一旦 GUI 建立完成，程式的主要運作就變成 event-driven。其中較短的 task 將交由 event dispath thread，較長的 task 則交給 worker thread。

[GWT] 使用外部 resource

使用外部 resource 是 Declarative Layout with UensureInjected()iBinder 其中的一個章節，並且已經由 PsMonkey 完成此文的翻譯。

我在實作這個章節所提及的方法時，遭遇了一點問題，因此提出來與大家分享。

在此說明一下我所遭遇的問題:

1. 我寫了一個名為 Resources 的 interface，打算在其他的 template file 中使用，內容如下。
   
   
   

   public interface Resources extends ClientBundle {
       @Source("Style.css")
       MyStyle style();
   
       @Source("Logo.jpg")
       ImageResource logo();
   
       public interface MyStyle extends CssResource {
           String red();
       }
   } 

2. 當然 Style.css 與 Logo.jpg 都是存在的，並且 Sytle.css 中也定義了 .red。
   
3. 然而當我使用如下的 template file 去使用 Resources 時，雖然 Image 能夠正常顯示，但是所有與 CssResource 相關的設定都沒有作用。
   
   
   

   <ui:UiBinder xmlns:ui='urn:ui:com.google.gwt.uibinder'
       xmlns:g='urn:import:com.google.gwt.user.client.ui'>
   
     <ui:with field='res' type='com.my.app.widgets.logoname.Resources'/>
   
     <g:HTMLPanel>
   
       <g:Image resource='{res.logo}'/>
   
       <div class='{res.style.red}'>
         this text should be red
       </div>
   
     </g:HTMLPanel>
   </ui:UiBinder> 

4. 如果使用 Firebugs 等工具觀察， 會看到對應的 HTML 元素確實被指定了 CSS class，然而在 CSS file 內卻沒有對應的設定存在。
   

解決的方法為，建立一個 Resources 實體並呼叫 CssResource 的 ensureInjected() 方法，以確保 CssResource 有被加入 DOM 中。

Resources resources = GWT.create(Resources.class);
resources.style().ensureInjected(); 

值得注意的是，無論創造了幾個 MyStyle 實體(包含在 Resources 內)，也只需要執行一次 ensureInjected() 。所以合理的作法應該是在 EntryPoint 內呼叫 ensureInjected()，如果希望所有的頁面都能使用同一個 Resources 實體，可以將此處建立的物件傳給其他頁面，詳細作法參考同一篇文章中的 Share resource instances 章節(中譯: 共用 resource 的 instances)。

[Java] ImageIO.read() 的怪異行為

我個人覺得這個問題還算蠻棘手的，所以在這篇文章的開頭先提供幾個關鍵字，讓同樣遇到此問題的朋友更有機會找到這篇文章。

[關鍵字]

ImageIO
Socket
Serializable
BufferedImage
NullPointerException

[問題描述]

我寫了一支 Server/Client 程式，Server 端會利用 ImageIO.write(image, "png", out) 將圖片傳給 Client 端，Client 端則用 ImageIO.read(in) 讀進為 BufferedImage 物件。

但是這支程式只有第一張圖片能夠正確的傳送，從第二張開始 ImageIO.read() 就只會回傳 null，如果在你的 code 中還有對圖片進行操作，那就可能會出現 NullPointerException 或著其他的錯誤。

[原因]

經過仔細分析後，我發現 ImageIO.read() 在讀進 PNG 格式的資料時，會留下 16 byte 在 stream 內，因此在讀取第二張圖片時就會讀到這多餘的 16 byte 而造成錯誤。

經由 PTT Java 板板友 LPH66 說明，這多出的 16 byte 中前 4 byte 是 PNG IDAT 區的 checksum，最後 12 byte 是 IEND 區。即使沒有這些資料，依然可以正確的解析圖片。

PTT Java 板板友 sbrhsieh 並補充這是因為 ImageReader 在處理數據的順序/數量上的不匹配造成的。在針對 PNG 格式時，ImageIO.read() 有短缺消耗的問題；而在處理 JPG 格式時，則有過度消耗的行為，也就是讀取一張圖片時，可能會連下一張圖片的資料也被消耗掉，使得下一張圖片無法正確讀入。在使用 ImageIO 與 FileInputStream 配合時，通常一個檔案內只會有一張圖片的資料，在讀進 JPG 時會遇到 EOF，因此並不會造成問題。

[解決方法]

當需要利用 ImaqeIO 與 Stream 傳送多張圖片時，我建議使用下列的方式:

// 修改自 PTT Java 板板友 ogamenewbie 所提供的程式
public class SerializableImage implements Serializable {
    
    byte[] data;

    public SerializableImage(BufferedImage image, String type) throws IOException {
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        ImageIO.write(image, type, baos);
        data = baos.toByteArray();
    }

    public BufferedImage getBufferedImage() throws IOException {
        return ImageIO.read(new ByteArrayInputStream(data));
    }
}

寫入圖片時:

SerializableImage serialImage = new SerializableImage(image, "png");            
out.writeObject(serialImage);

讀取圖片時:

SerializableImage serialImage = (SerializableImage)in.readObject();                
BufferedImage image = serialImage.getBufferedImage();