自己做個AlphaGo（一）（井字棋）

01-29

這是一個我不可能填完的坑，但我想井字棋和五子棋應該可以完成。

你可以先安裝GnuGo，和它下一盤棋。

我們先來解決一個比圍棋簡單的多的遊戲。井字棋。

井字棋_百度百科

井字棋有三種可能，贏棋，輸棋和和棋。

井字棋是sovled game，就是說，人類已經發現了不輸的方法。不論你是先手還是後手，都可以做到不輸棋。

我們的目標就是寫一個不會犯錯的人工智慧，來下井字棋。

我們將用C++語言來解決這個問題。我們首先來解決棋盤表示的問題。

顯然，用這個可以表示

// X 黑棋n// O 白棋n// 沒有棋子nchar cb[3][3]; // chess boardn

我們這樣列印棋盤（和GnuGo的表示方法一致）

A B Cn1 X (X) 1n2 O 2n3 3n A B Cn

其中用括弧括起來的棋子表示當前下的棋子。

所以我們的棋盤也需要表示當前下的棋子

struct TicTacToe {nt// X 黑棋nt// O 白棋nt// 沒有棋子ntchar cb[3][3]; // chess boardntshort x;ntshort y;n}n

接下來，我們自然需要初始化遊戲的功能。如下：

struct TicTacToe {ntstatic const int SIZE = 3;nnt// X 黑棋nt// O 白棋nt// 沒有棋子nt// chess boardntchar cb[SIZE][SIZE];ntshort x;ntshort y;nntTicTacToe() : x(-1), y(-1)nt{nttfor (int i = 0; i < SIZE; ++i)ntttfor (int j = 0; j < SIZE; ++j)nttttcb[i][j] = ;nt}n};n

初始的x和y都是-1，表示遊戲還沒開始。

接下來就是列印遊戲棋盤。

tvoid print()nt{nttprintColNum();nttfor (int i = 0; i < SIZE; ++i)ntt{ntttcout << i+1 << " ";ntttfor (int j = 0; j < SIZE; ++j)nttt{nttttcout << cb[i][j] << " ";nttt}ntttcout << i+1 << endl;ntt}nttprintColNum();nt}ntvoid printColNum()nt{nttcout<<" ";nttfor (int i = 0; i < SIZE; ++i)ntt{ntttprintf("%c ", i+A);ntt}nttcout<<endl;nt}n

遊戲棋盤的列印依賴於一個輔助函數，printColNum，這個是專門列印列號的。

但這並不能完全解決棋盤列印的問題，因為我們有時需要表示誰剛剛下了哪個子。所以，還需要將剛剛下的子用括弧括起來。列印）的時候只需要判斷j和y相等。但列印( 的時候卻需要提前判斷一下。

tvoid print()nt{nttprintColNum();nttfor (int i = 0; i < SIZE; ++i)ntt{ntttint j = -1;ntttprintf("%d%c", i+1, getBracketChar(i, j));ntttfor (j = 0; j < SIZE; ++j)nttttprintf("%c%c", cb[i][j], getBracketChar(i, j));ntttcout << i+1 << endl;ntt}nttprintColNum();nt}ntchar getBracketChar(int i, int j)nt{nttchar c = ;nttif (i == x)ntt{ntttif (j == y) return );ntttelse if (j+1 == y) return (;ntt}nttreturn c;nt}ntvoid printColNum()nt{nttcout<<" ";nttfor (int i = 0; i < SIZE; ++i)ntttprintf("%c ", i+A);nttcout<<endl;nt}n

我們將括弧的邏輯隱藏在 getBracketChar中。

接下來我們需要有判斷遊戲結束的辦法。如果某人贏了，遊戲結束；如果棋盤滿了，遊戲也結束。

tbool isGameOver()nt{nttif (whoWins() != -)ntttreturn true;nttfor (int i = 0; i < SIZE; ++i)ntttfor (int j = 0; j < SIZE; ++j)nttttif (cb[i][j] == )ntttttreturn false;nttreturn true;nt}n

這個需要有判斷誰贏誰輸的方法。輸贏的判斷方式這樣的，先判斷是否有棋子連成橫排，接著看是否有棋子連成豎排，接著看是否有棋子連成對角線。（這裡要注意，如果有空格，就可以直接判斷這裡沒有贏棋者）

t// return X|O|-nt// X勝 | O勝 | 平局或者沒有結果ntchar whoWins()nt{nttchar c = isRow();nttif (c != -) return c;nttc = isCol();nttif (c != -) return c;nttreturn isX();nt}ntchar isRow() {nttfor (int i = 0; i < SIZE; ++i)ntttif (cb[i][0] != && cb[i][0] == cb[i][1] && cb[i][1] == cb[i][2])nttttreturn cb[i][0];nttreturn -;nt}ntchar isCol() {nttfor (int j = 0; j < SIZE; ++j)ntttif (cb[0][j] != && cb[0][j] == cb[1][j] && cb[1][j] == cb[2][j])nttttreturn cb[0][j];nttreturn -;nt}ntchar isX() {nttif (cb[1][1] == ) return -;nttif (cb[0][0] == cb[1][1] && cb[1][1] == cb[2][2])ntttreturn cb[0][0];nttif (cb[0][2] == cb[1][1] && cb[1][1] == cb[2][0])ntttreturn cb[1][1];nttreturn -;nt}n

當然，我們需要「下子」這個動作。

tvoid play(int x, int y, char p) {nttcb[x][y] = p;nttthis->x = x;nttthis->y = y;nt}n

好了，現在我們開始「肉菜」。我們需要引入決策樹的概念。

這就是決策樹，最上面的稱為根節點。最下面的（圖中未畫出），也就是棋局終了，稱為葉子節點。一個完整的決策樹代表了所有可能的棋局，而從根節點到某個葉子節點的某個路徑代表整個棋局。我們稱根節點為第一層，稱所有葉子節點所在的層次為最後一層，其餘以此類推。

在葉子節點中，我們稱X勝的為X勝節點，稱O勝的為O勝節點，稱其他的為和棋節點。

整個井字棋的勝利被我們轉化成尋找根節點到葉子節點的路徑的問題。

我們倒推一下我們的策略，如果我們執X，在X勝節點我們就勝利了。在倒數第二層，我們如何選擇路徑呢？如果有X勝節點的話，我們選擇X勝節點，否則就選擇和棋節點，如果連和棋節點都沒有，我們就認輸。倒數第二層的所有節點，我們稱之為對手節點，因為這個節點是什麼，我們不能直接選擇，是由對手選擇的。

在對手節點上，如果這個節點的兒子節點包含X勝節點或和棋節點，我們稱之為不敗節點，否則，那就是只包含O勝節點，我們稱之為必敗節點。

那麼再往上一層呢？我們會選擇什麼樣的節點呢？記住，這次我們要選擇的節點都是對手節點的父親節點。一旦某個節點的兒子節點中包含哪怕一個必敗節點，我們也會稱這個節點為必敗節點。否則稱為不敗節點。我們不會選擇必敗節點，我們會選擇不敗節點。

到了這一層，我們就將所有的節點都標明清楚了。我們可以試著將這些節點都在紙上表示出來。

而我們策略也很簡單，那就是尋找不敗節點。

接下來，我們站在X的立場，來看看計算節點的「不敗」屬性的方法。很顯然，這是一個遞歸可以解決的問題：

如果一個節點是終局節點，如果其是非O勝節點，即為不敗節點，否則為必敗節點。
否則，如果一個節點的是對方節點，如果其兒子節點中包含不敗節點，則為不敗節點。否則為必敗節點。
否則（節點是我方節點），如果全部兒子節點都是不敗節點，則為不敗節點，否則為必敗節點。

代碼也很簡單：

tbool isXNotFail() // true => 不敗節點 false => 必敗節點nt{nttif (isGameOver())ntt{ntttreturn !(whoWins() == O);ntt}nttif (isCurPlayer(O))ntt{ntttint _x = x, _y = y;ntttfor (int i = 0; i < SIZE; ++i)nttt{nttttfor (int j = 0; j < SIZE; ++j)ntttt{ntttttif (cb[i][j] == )nttttt{nttttttplay(i, j, X);nttttttif (isXNotFail()) {ntttttttplay(i, j, );ntttttttx = _x; y = _y;ntttttttreturn true;ntttttt}nttttttplay(i, j, );nttttt}ntttt}nttt}ntttx = _x; y = _y;ntttreturn false;ntt}nttif (isCurPlayer(X))ntt{ntttint _x = x, _y = y;ntttfor (int i = 0; i < SIZE; ++i)nttt{nttttfor (int j = 0; j < SIZE; ++j)ntttt{ntttttif (cb[i][j] == )nttttt{nttttttplay(i, j, O);nttttttif (!isXNotFail()) {ntttttttplay(i, j, );ntttttttx = _x; y = _y;ntttttttreturn false;ntttttt}nttttttplay(i, j, );nttttt}ntttt}nttt}ntttx = _x; y = _y;ntttreturn true;ntt}nt}ntbool isCurPlayer(char p)nt{nttif (x == -1 && y == -1) {ntttreturn p == O;ntt}nttreturn (cb[x][y] == p);nt}n

isCurPlayer是檢測是否輪到某方走棋的函數。我們默認開局X先手。

如果我們怎麼模擬下一步走棋呢？我們先將現在的走棋位置記下來，然後在所有可能的位置走棋。當走完這些之後，將走棋位置重置。

好了，我們已經寫出不敗的策略了。

現在我們來討論這棵樹的大小。我們發現這棵樹的節點數量是 $9!=$ 362880，這是時間複雜度，n比較小，所以可以接受。棧深度是9，所以我們用不著做任何優化。直接用遞歸是可行的。

現在我們將這個策略用於實戰。

首先，我們先做一個遊戲界面，代碼如下：

int main(int argc, char const *argv[])n{ntTicTacToe ttt;ntchar str[25];ntwhile (!ttt.isGameOver()) {nttttt.print();nttchar p = ttt.isCurPlayer(X) ? O : X;nttprintf("It is %cs turnn", p);nttcin.getline(str, 25);nttchar col = toupper(str[0]);nttchar row = str[1];nttif (col == Q)ntt{ntttreturn 0;ntt}nttif (col < A || col > C) {ntttperror("must A-C");ntttreturn 1;ntt}nttif (row < 1 || row > 3)ntt{ntttperror("must be 1-3");ntttreturn 1;ntt}nttint x = row - 1;nttint y = col - A;nttif (ttt.cb[x][y] != )ntt{ntttprintf("%c%c has %c, please chose another move.n", col, row, ttt.cb[x][y]);ntttcontinue;ntt}nttttt.play(x, y, p);nt}ntchar winner = ttt.whoWins();ntif (winner == -)nt{nttcout << "Its a tie." << endl;nttreturn 0;nt}ntprintf("%c wins!.n", winner);ntreturn 0;n}n

你可以自己和自己玩一盤棋。

現在，我們要將那個人工智慧接入遊戲。我們讓人工智慧執O，後手。

那麼，我們需要O的不敗函數，幸虧，這也很簡單，複製代碼就行。

tbool isXNotFail() // true => 不敗節點 false => 必敗節點nt{nttreturn isPlayerNotFail(X);nt}ntbool isONotFail() // true => 不敗節點 false => 必敗節點nt{nttreturn isPlayerNotFail(O);nt}ntbool isPlayerNotFail(char p) // true => 不敗節點 false => 必敗節點nt{nttchar op = p == X ? O : X;nttif (isGameOver())ntt{ntttreturn !(whoWins() == op);ntt}nttif (isCurPlayer(op))ntt{ntttint _x = x, _y = y;ntttfor (int i = 0; i < SIZE; ++i)nttt{nttttfor (int j = 0; j < SIZE; ++j)ntttt{ntttttif (cb[i][j] == )nttttt{nttttttplay(i, j, p);nttttttif (isXNotFail()) {ntttttttplay(i, j, );ntttttttx = _x; y = _y;ntttttttreturn true;ntttttt}nttttttplay(i, j, );nttttt}ntttt}nttt}ntttx = _x; y = _y;ntttreturn false;ntt}nttif (isCurPlayer(p))ntt{ntttint _x = x, _y = y;ntttfor (int i = 0; i < SIZE; ++i)nttt{nttttfor (int j = 0; j < SIZE; ++j)ntttt{ntttttif (cb[i][j] == )nttttt{nttttttplay(i, j, op);nttttttif (!isXNotFail()) {ntttttttplay(i, j, );ntttttttx = _x; y = _y;ntttttttreturn false;ntttttt}nttttttplay(i, j, );nttttt}ntttt}nttt}ntttx = _x; y = _y;ntttreturn true;ntt}nt}n

然後，我們真正的將人工智慧集成進去。

我們在主循環中集成以下代碼：

twhile (!ttt.isGameOver()) {nttttt.print();nttchar p = ttt.isCurPlayer(X) ? O : X;nttprintf("It is %cs turnn", p);nttif (p == O)ntt{ntttint x,y;ntttstd::tie (x, y) = ttt.getAI_MoveO();nttt// printf("AI move %d, %dn", x, y);ntttif (x == -1)nttt{nttttcout << "I lose." << endl;nttttreturn -1;nttt}ntttttt.play(x, y, O);ntttcontinue;ntt}n

我們先調用getAI_MoveO，為O找到一步棋，如果找不到，就認輸。如果找到了，就按照這種路子去走。而getAI_MoveO也非常簡單，和之前的策略樹的邏輯是一樣的：

ttuple<int,int> getAI_MoveO()nt{nttint _x = x, _y = y;nttfor (int i = 0; i < SIZE; ++i)ntt{ntttfor (int j = 0; j < SIZE; ++j)nttt{nttttif (cb[i][j] == )ntttt{ntttttplay(i, j, O);ntttttif (isONotFail()) {nttttttplay(i, j, );nttttttx = _x; y = _y;nttttttreturn make_tuple (i, j);nttttt}ntttttplay(i, j, );ntttt}nttt}ntt}nttx = _x; y = _y;nttreturn make_tuple (-1, -1);nt}n

我們人工智慧遊戲已經完成了。現在它已經能保持不敗了。你可以多玩幾場喲。

---

可是，這個人工智慧只是不敗而已，有時它明明能贏，它也不會選擇贏。我們將改進一下，讓它可以做到能贏則贏。

我們繼續站在X的立場，來看看計算節點的價值屬性的方法。

如果一個節點是終局節點，如果其是X勝節點，為1分，平局節點為0分，O勝節點得-1分。
否則，如果一個節點的是對方節點，如果其兒子節點中包含1分節點，則為1分節點，否則，包含0分節點為0分節點，否則（子節點都為-1分節點）為-1分節點（必敗）。
否則（節點是我方節點，接下來的行動不歸我方控制），如果兒子節點包含-1分節點，就是-1分節點，否則，如果含有1分節點，就是1分節點，否則（子節點全部是0分節點）就是0分節點。

函數如下：

tint getNodeValue(char p) // true => 不敗節點 false => 必敗節點nt{nttchar op = p == X ? O : X;nttif (isGameOver()) {ntttchar w = whoWins();ntttif (w == -) return 0;ntttreturn (w == p) ? 1 : -1;ntt}nttint _x = x, _y = y;nttvector<int> v;nttif (isCurPlayer(op))ntt{ntttwalk_empty([&](int i, int j) {nttttplay(i, j, p);nttttint val = getNodeValue(p);nttttv.push_back(val);nttttplay(i, j, );nttt});ntttx = _x; y = _y;ntttif (any_of(v.begin(), v.end(), [](int i) {return i==1;})) {nttttreturn 1;nttt}ntttreturn (any_of(v.begin(), v.end(), [](int i) {return i==0;})) ?ntttt0 : -1;ntt}nttassert(isCurPlayer(p));nttwalk_empty([&](int i, int j){ntttplay(i, j, op);ntttint val = getNodeValue(p);ntttv.push_back(val);ntttplay(i, j, );ntt});nttx = _x; y = _y;nttif (any_of(v.begin(), v.end(), [](int i) {return i==-1;})) {ntttreturn -1;ntt}nttreturn (any_of(v.begin(), v.end(), [](int i) {return i==1;})) ?nttt1 : 0;nt}ntvoid walk_empty(function<void(int,int)> callback)nt{nttfor (int i = 0; i < SIZE; ++i)ntttfor (int j = 0; j < SIZE; ++j)nttttif (cb[i][j] == )ntttttcallback(i,j);nt}n

其中，為了簡化代碼，我使用了一個輔助函數 walk_empty，作用是遍歷所有的空的棋格。

接下來，讓我們的AI走子函數可以識得這個估值。優先選擇1分就可以啦。

ttuple<int,int> getAI_MoveO()nt{nttint _x = x, _y = y;nttvector<tuple<int,int,int>> vec;nttwalk_empty([&](int i, int j){ntttplay(i, j, O);ntttvec.push_back(make_tuple(i, j, getNodeValue(O)));ntttplay(i, j, );ntt});nttx = _x; y = _y;nnttint i, j, v;nttfor (auto e : vec) {nttttie(i, j, v) = e;ntttif (v == 1)nttttreturn make_tuple(i,j);ntt}nttfor (auto e : vec) {nttttie(i, j, v) = e;ntttif (v == 0)nttttreturn make_tuple(i,j);ntt}nttreturn make_tuple (-1, -1);nt}n

怎麼樣，還是有點厲害的吧。你稍微疏忽一下，就會被它贏了喲。

---

項目地址：GitHub - picasso250/TicTacToe: 井字棋人工智慧不敗