對戰踩地雷 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。

[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();    

[Java] 製作 Sign Applet

前言：

Applet 是用於網頁上的小程式，基於安全理由，它不允許你做任何的 IO 操作，(存取本機電腦 及 網路連線...等，只有存放該網頁的 server 例外)否則一旦開了惡意的 applet，電腦就如同中了木馬一般。

這種概念稱為 Sandbox，只允許你在盒子內部操作，所以無論你在盒子裡做了什麼事，都不會影響到盒子外的世界。如果有特殊的需求，可以使用 Sign Applet，在開啟程式前會先出現確認視窗，待使用者同意後，程式便能夠有較高的存取權限。

製作 Sign Applet 方法：

1. 產生 key:
   keytool -genkey -keyalg RSA -alias "key_name"
   
   
   
   1. 如果 key store 目前並不存在，
      則必須設定 keystore 密碼；
      反之，如果先前已經設定過密碼，
      則此時就需要輸入先前所設定的密碼。
   2. 接著必須輸入一些基本資料，
      如: 姓名, 單位, 國碼, ... 等等，
      此處就不贅述了。
   3. 最後輸入 key 密碼，即可順利產生 key。
   
   
2. 將 key 加入 applet 中:
   jarsigner "applet.jar" "key_name"
   此時需要依序輸入 key store 密碼與 key 密碼。 
3.  Sign Applet 製作完成，
   此時連上嵌入此 Sign Applet 的網頁，
   即會跳出確認視窗，詢問是否同意進行操作。 
   

延伸說明:

1. 在產生 keytool 時，如果沒有特別指定，
   將會存放在此: ~/.keystore
   註: 此處以 ubuntu 為例， Windows 作業系統將會在其他的位址。
   如果需要額外指定存放位址， 需加上參數 -keystore "path"。
2. 列出目前已有的 key:
   keytool -list
3. 檢查 jar 是否已經完成 Sign
   jarsigner -verify "applet.jar"

Java Access Modifiers

Visibility	public	protected	package (default)	private
same class	Y	Y	Y	Y
non-subclass in the same package	Y	Y	Y	N
non-subclass outside the package	Y	N	N	N
subclass in the same package	Y	Y	Y	N
subclass outside the package	Y	Y	N	N

1. Class 只有 public 和 package 兩種 modifiers。
2. 表格中 subclass 的 visiblility 指的是使用繼承方式 access 該 member。
3. protected 所修飾之 member，若其 subclass outside the package，則在 subclass 中，該 member 為 private。
4. sub-package 不算是 same package

Java Thread

Java 的 Thread 和 Process 一樣，共有五個 state，
分別是 New, Runnable, Running, Waiting/blocked/sleeping, Dead。

New - 當 thread's instance 已經建立，但是尚未呼叫 start()，
此時，這個 thread 仍然稱做 not alive。

(其他的 state 和 Process 幾乎相同，這裡就省略了)


接下來介紹有關操作 thread 所需要呼叫的 method。

start() - Thread's non-static method

將該 thread 從 New state 移至 Runnable state，
至此，該 thread 才成為一個 alive thread。

無論如何，同一個 thread 物件都只能 start() 一次，
否則將會產生 RuntimeException；
然而同一個 Runnable interface，
則可以經由 Thread's Constructor，建立並啟動多個 thread。

yield() - Thread's static method

將目前的 thread 由 Running state 移至 Runnable，
並且由 Runnable state 中，
選一 "相同" priority 的 thread 進入 Running state，
故有可能會選到原先的 thread。

由於 JVM 對於 priority 的實作未必確實為 1~10，
可能會有多個設定值對應到同一個 priority 的情形，
所以需要特別注意。

sleep() - Thread's static method

將目前的 thread 由 Running state 移至 Sleeping，
並等待指定的時間後，才會進入 Runnable。

並不是時間一到立刻進入 Running，
所以通常該 thread 的休息時間會較長於指定的時間。

若是在 synchronize block 中呼叫 sleep()，
則 thread 並不會釋放自己所擁有的資源。

join() - Thread's non-static method

暫停目前 thread 的執行，並等待指定的 thread 執行完畢後，
此 thread 才會回到 runnable state。

以下三個指令都必須在 synchronize block 中才可呼叫。

wait() - Object's non-static method

目前 thread 進入 Waiting，暫時釋放指定的資源。

當此 thread 經由 notify() or notifyAll() 叫醒後，
會送出 InterruptedException()。

另外，wait() 也有 over-loading 的版本，
提供最長等待時間作為參數。

notify() - Object's non-static method

叫醒某個正等待此物件之 thread。

叫醒的順序與 thread 進入 Wainting 的時間無關。

notifyAll() - Object's non-static method

叫醒所有正在等待此物件之 thread。

註: notify 與 notifyAll 所叫醒的 thread 只是回到 runnable，
而並不會立刻執行。          

Java Assertion

Assertion 是 Java 1.4 後才有的一個新特色，作用是幫助 debug。

例如在以下的程式中，num 的值應該要大於 0，則你可以使用 Assertion 來幫助你確認。

private void methodA(int num) {
    assert(num>0);
    useNum(num+x);
}

簡單的說，當 assert 後方的引數為 false 時，則程式就會丟出 AssertionError。

另一種用法是提供一些訊息給 Assertion，當出現 AssertionError 時，
這些訊息就會顯示在 Stack Trace 上。

例: assert(num>0):"num must greater than 0";
冒號後方的引數可為 primitive 或 Object。


Asertion 預設是不啟用，若是要啟用 Assertion 的功能，
在編譯時必須使用 "javac -source 1.4"。
(預設是 "javac -source 1.3")
目前在 6.0 版 Compile 時，已經不需要增加額外的參數了。

而在執行時則用 "java -ea" 或著 "java -enableassertions"，
同樣的預設值也是不啟用。

如果只須啟用部分 class 或著部分 package 的 Assertions 功能，
可以用這樣的方式 "java -ea:com.foo.Bar"，
或著只有某 package 不啟用 "java -ea -da:com.foo"，
(-da 為 -disableassertions 的縮寫)
另外還有兩個參數為 "-dsa" 和 "-esa"，
分別代表 "disable systema ssertion" 和 "enable systema ssertion"。

[註] Java 中的 package 並無階層的關係，

例如 com.foo 以及 com.foo.xxx，其中並沒有任何的關係，
它們只是在檔案系統中使用相同的目錄。

但是 Assertion 是唯一的例外，上述的 "java -ea -da:com.foo"，
除了啟動 com.foo 的 Assertion 機制， com.foo 的 subpackage 也會啟動。

在 Assertion 未啟用的情況下，JVM 會忽略 Assertion 的處理。


Assettion 在以下的情況不建議被使用:

1. 用來驗證 public method 的 argument。
   這是因為 public method 可以被任何人呼叫， 而在 Assetion 未啟用的情況下， 即使是不正常的參數， 程式仍然會繼續執行，應該改用例外處理。
   只適用於 private method 的 argument。
2. 用來驗證 public method 的 argument。
   原因同上。
3. 用在會導致 side effect 的情況下。
   程式在 assertion 的檢查過程中，不應該改變程式目前的 state。

Java Stream 簡介

Java 的 stream 相關類別很多，讓人目不暇給，
FileInputStream, FileOutputStream, FileReader, FileWriter
光是 File 開頭的就有這四種，
其他開頭的還有 Object, Data, Print, Buffered....，
另外還有兩個 InputStreamReader 和 OutputStreamWriter 這兩個奇怪東西。


到底我該用的是什麼? 它們之間又有什麼差別?

先從 Reader/Writer 和 InputStream/OutputStream 說起好了，

Reader 是讀，InputStream 也是讀，
兩著乍看之下都是在做讀資料，
其間差別究竟何在?

根據 API 上的說法，InputStream 是以 byte 為單位，
而 Reader 則是以字元為單位，並且會根據編碼 decode。
當然，OutputStream 與 Writer 的差別也是同理。


再來討論這些 streams 的另一個差別，
在前面所提到的所有類別中，
只有 File 開頭類別的沒有 "以其它 Stream 類別為參數" 的 Constructor。
(以下就只以 OutputStream 為例)

這是因為只有 FileOutputStream 是直接在跟 File 溝通，
其他的 Stream 都只是將資料寫入 Constructor 參數中的 OutputStream。


那麼，我們為什麼不只用 FileOutputStream 就好?

你可以去看看 FileOutputStream 提供了哪些 method，
會發現它只提供了有關 byte array 的操作，
如果你想要輸出一行字給 FileOutputStream，你可能會自己處理得很辛苦。

所以啦，Java 提供了一系列好用的 Stream，
把最底層，只提供 byte array 操作的 Stream 包裝起來，
讓你操作起來更直覺，
因此想要寫入字串可以用 PrintStream，
想要把各種基本資料型態，
如 int, double...等的 "值" 輸出，可以用 DataOutputStream。
想要把整個物件 Serialize，則可以用 ObjectOutputStream。

或許你有注意到，
PrintWriter 也有提供檔名和 File 物件做為 Constructor 的參數呀!
但這只是為了你使用上的方便，
實際上 PrintWriter 還是會自己宣告一份 FileOutputStream 與檔案溝通。


而 InputStreamReader 和 OutputStreamWriter，
則是用來將 Stream 包裝成 Reader/Writer，
並且由這兩個物件做編碼的處理。


另外，這些包裝是可以多層的，
例如 ObjectOutputStream -> BufferedOutputStream -> FileOutputStream，
或著 PrintWriter -> OutputStreamWriter -> FileOutputStream。


如果你想要惡搞，
用 ObjectOutputStream 去包裝 DataOutputStream，
甚至是 ObjectOutputStream -> ObjectOutputStream -> ObjectOutputStream -> ....
這樣在宣告與執行上也不會有問題。
(這樣也算是錯誤，不過這是程式邏輯上的錯誤)