Tic tac toe是一個非常簡單的游戲，能夠讓你編程一臺電腦來玩。你可以編寫代碼告訴它如果可用的話進入井字中心，看看對手是否有兩個連在一起，如果是這樣的話就封鎖它，或者如果有一個可用的就連接到一個角落，讓自己的兩個連在一起等等。

但是這不是你學會玩的方式。有人把網格放在你的面前，并開始把Xs和Os放在它上面。過了一會兒，你為自己想出了策略。

那么，我們如何讓電腦模仿人類呢？計算機非常擅長的一件事是記住事情，為什么不創建一個應用程序，讓電腦記住它是如何輸了一場井字游戲，然后避免再次做同樣的事情。

這將如何實現？首先，考慮游戲棋盤：它有九個單元格，每個單元格有三個狀態：空，O和X。可以用一個九位數的三位數表示。所以，例如一塊空棋是000000000，中間有一個X（給出X的值為2）的棋是000020000等等。這個可以很容易地轉換成一個整數，這個整數可以是散列表中的關鍵字。所以，當電腦輸了這場游戲，它可以看看棋子是什么時候做了最后一步，評估，并設置一個hashmap（哈希映射）的值。將來在做一個動作之前，可以先看看棋盤的狀態，如果它做了一個特定的動作，并且如果它出現在HashMap中，它會知道它上次輸過這場游戲， 所以這次應該做點別的。

使用這種方法，不會有其他的策略，我們可以建立一個應用程序，迅速學習如何玩井字游戲。不僅如此，當你完成后，hashmap很容易轉移，即如何玩這個游戲的“記憶”可以給另一臺計算機，然后它會立即知道如何玩這個游戲。這個算法太天真了，它只會在第一個可用空間中移動。起初，它會失去很多，但是隨著時間的推移，它將記錄失敗的地方，并遵循避免策略。你會發現，它很快就學會了如何玩一個井字游戲，就像人類一樣。

以下是游戲的實際操作視頻——游戲中我拿X，電腦是O。它總是天真地走到第一個可用的位置，除非這個位置以前已經不能用了。當我在中心開始的時候，它總是往右走，我不斷地打擊電腦，直到它找出錯誤，然后迫使我陷入困境。當我改變我的策略，電腦已經學習到了：

實現這一機器學習的學習代碼是非常簡單的。這里有一個片段，顯示計算機評估棋子的位置，然后倒退導致丟失狀態的人為操作，將棋子狀態存儲在HashMap中：

public void learnFromLosing(){
    int losingPosition = calcBoardValue();
    losingPosition-= HUMAN_VALUE * Math.pow(3, lastHumanMove);
    losingGamePositions.put(losingPosition, true);
}
public int calcBoardValue(){
    int boardValue = 0;
    for(int nIndex=0; nIndex<9; nIndex++){
        boardValue += boardValues[nIndex] * Math.pow(3, nIndex);
    }
    return boardValue;
}

boardValues[]數組只保留0、1、2為空、O和X，所以calcBoardValue通過在它們之間循環并將它們乘以它們的索引來將其轉換為整數——有效地將棋子轉換為整數。在learnFromLosing中，將最后一個人的移動的值從中減去，以使棋盤恢復到預失敗狀態，然后失敗的位置存儲在loseGamePositions的哈希映射（hashmap）中。

當輪到電腦移動時，它會循環通過棋盤，直到它找到一個空的位置（這是天真的部分！），然后調用isOKToMove，如果它返回true，將使計算機移動到該位置。

boolean computer_moved=false;
for(int nIndex=0; nIndex<9; nIndex++){
    if(boardValues[nIndex]==EMPTY_VALUE){
        if(isOKToMove(nIndex)){
            boardValues[nIndex]=COMPUTER_VALUE;
            computer_moved=true;
            totalMoves++;
            drawBoard();
            break;
        }
    }
}

然后isOKToMove函數會查看棋盤，如果計算機執行此操作，并檢查該棋盤位置是否在失敗位置的hashmap中。如果是，那么就不能移動了。如果不是，那么電腦會做這個動作：

public boolean isOKToMove(int thisIndex){
    int boardValue = calcBoardValue();
    boardValue+=COMPUTER_VALUE * Math.pow(3, thisIndex);
    if(losingGamePositions.containsKey(boardValue)){
        return false;
    } else {
        return true;
    }
}

這就是它！為了您的方便，以下是實現此代碼的完整Android活動的源代碼（也就是您在上述視頻中看到的Android應用程序）。

接下來的步驟和思考：

1. 如何擴展應用程序，以便哈希映射中的“false”值表示棋子位置的失敗，“true”表示勝利？ 這樣，計算機不但可以避免記憶失效，還可以記住以前贏得的方式，從而更快地學習。
2. 如何將hashmap的結果序列化到Firebase，然后用這些結果初始化應用程序，從而從一個應用程序到另一個應用程序進行內存轉儲？
3. 你將如何將這個概念延伸到一個更復雜的游戲，如國際象棋？

import android.content.DialogInterface;
import android.support.v7.app.AlertDialog;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.view.View;
import android.widget.Button;
import java.util.HashMap;
public class MainActivity extends AppCompatActivity implements View.OnClickListener{
    int[] buttonIDs = new int[] {R.id.btn1, R.id.btn2, R.id.btn3, R.id.btn4, R.id.btn5, R.id.btn6, R.id.btn7, R.id.btn8, R.id.btn9};
    Button[] buttons = new Button[9];
    int[] boardValues = new int[9];
    int lastHumanMove=0;
    int totalMoves=0;
    public static final int EMPTY_VALUE=0;
    public static final int COMPUTER_VALUE=1;
    public static final int HUMAN_VALUE=2;
    public static final String COMPUTER_CHARACTER="O";
    public static final String HUMAN_CHARACTER="X";
    public static final String EMPTY_CHARACTER="";
    public static final String NOBODY="NOBODY";
    HashMap losingGamePositions = new HashMap<>();
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        final Button tmpButton;
        for(int nIndex=0; nIndex<9; nIndex++) {
            buttons[nIndex] = (Button) findViewById(buttonIDs[nIndex]);
            buttons[nIndex].setOnClickListener(this);
        }
        drawBoard();
    }
    @Override
    public void onClick(View v){
        if(v instanceof Button){
            Button thisButton = (Button) v;
            int index = Integer.parseInt(thisButton.getTag().toString());
            if(boardValues[index]==EMPTY_VALUE){
                boardValues[index]=HUMAN_VALUE;
                lastHumanMove=index;
                drawBoard();
                totalMoves++;
                if(checkWinner(HUMAN_VALUE)){
                    learnFromLosing();
                    showWinner(HUMAN_CHARACTER);
                } else {
                    if(totalMoves==9)
                    {
                        showWinner(NOBODY);
                    } else {
                        doComputerTurn();
                    }
                }
            }
        }
    }
    public void showWinner(String playerID){
        AlertDialog alertDialog = new AlertDialog.Builder(MainActivity.this).create();
        alertDialog.setTitle("Game Over");
        if(playerID==NOBODY){
            alertDialog.setMessage("It's a tie!");
        } else {
            alertDialog.setMessage("The Winner is " + playerID);
        }
        alertDialog.setButton(AlertDialog.BUTTON_NEUTRAL, "OK",
                new DialogInterface.OnClickListener() {
                    public void onClick(DialogInterface dialog, int which) {
                        dialog.dismiss();
                        for(int nIndex=0; nIndex<9; nIndex++){
                            buttons[nIndex].setText(EMPTY_CHARACTER);
                            boardValues[nIndex]=EMPTY_VALUE;
                            totalMoves=0;
                        }
                    }
                });
        alertDialog.show();
    }
    public boolean checkWinner(int playerID){
        if((boardValues[0]==playerID && boardValues[1]==playerID && boardValues[2]==playerID) ||
           (boardValues[0]==playerID && boardValues[3]==playerID && boardValues[6]==playerID) ||
           (boardValues[0]==playerID && boardValues[4]==playerID && boardValues[8]==playerID) ||
           (boardValues[1]==playerID && boardValues[4]==playerID && boardValues[7]==playerID) ||
           (boardValues[2]==playerID && boardValues[4]==playerID && boardValues[6]==playerID) ||
           (boardValues[2]==playerID && boardValues[5]==playerID && boardValues[8]==playerID) ||
           (boardValues[3]==playerID && boardValues[4]==playerID && boardValues[5]==playerID) ||
           (boardValues[6]==playerID && boardValues[7]==playerID && boardValues[8]==playerID))
            return true;
        else
            return false;
    }
    public void doComputerTurn(){
        boolean computer_moved=false;
        for(int nIndex=0; nIndex<9; nIndex++){
            if(boardValues[nIndex]==EMPTY_VALUE){
                if(isOKToMove(nIndex)){
                    boardValues[nIndex]=COMPUTER_VALUE;
                    computer_moved=true;
                    totalMoves++;
                    drawBoard();
                    break;
                }
            }
        }
        if (checkWinner(COMPUTER_VALUE)) {
            showWinner(COMPUTER_CHARACTER);
        } else {
            if(!computer_moved) {
                // There are no moves, so let's flag this as a bad board position
                learnFromLosing();
                // Just do any move, and lose
                for(int nIndex=0; nIndex<9; nIndex++){
                    if(boardValues[nIndex]==EMPTY_VALUE){
                        boardValues[nIndex]=COMPUTER_VALUE;
                        computer_moved=true;
                        drawBoard();
                        break;
                    }
                }
            }
        }
    }
    public boolean isOKToMove(int thisIndex){
        int boardValue = calcBoardValue();
        boardValue+=COMPUTER_VALUE * Math.pow(3, thisIndex);
        if(losingGamePositions.containsKey(boardValue)){
            return false;
        } else {
            return true;
        }
    }
    public void learnFromLosing(){
        int losingPosition = calcBoardValue();
        losingPosition-= HUMAN_VALUE * Math.pow(3, lastHumanMove);
        losingGamePositions.put(losingPosition, true);
    }
    public int calcBoardValue(){
        int boardValue = 0;
        for(int nIndex=0; nIndex<9; nIndex++){
            boardValue += boardValues[nIndex] * Math.pow(3,nIndex);
        }
        return boardValue;
    }
    public void drawBoard(){
        for(int nIndex=0; nIndex<9; nIndex++){
            switch(boardValues[nIndex]){
                case HUMAN_VALUE:
                    buttons[nIndex].setText(HUMAN_CHARACTER);
                    break;
                case COMPUTER_VALUE:
                    buttons[nIndex].setText(COMPUTER_CHARACTER);
                    break;
                default:
                    buttons[nIndex].setText(EMPTY_CHARACTER);
            }
        }
    }
}

推薦閱讀：

展望2018年：基于AI人工智能的移動應用程序開發將如何發展

開發一個聊天機器人（Chatbot）應用程序需要花費多少錢？

NLP|自然語言處理-語法解析指南：算法和技術

PS: 更多、相關視頻、培訓、公開課，請關注！

關于人工智能機器學習的最新資訊和相關開發工具推薦，請<>！