問題描述

五子棋AI。

設(shè)計(jì)一個(gè)交互式的應(yīng)用，用戶用鼠標(biāo)在棋盤上單擊左鍵表示落子，然后五子棋AI分析棋局，并在它認(rèn)為最好的地方落子，雙方交替，直到分出勝負(fù)或者和棋。

在分析問題的過程中，我們假定圖形用戶界面已經(jīng)完成，并且支持“開始游戲”、“重新開始”、“調(diào)整先后手”、“調(diào)整難度”等功能，獲取鼠標(biāo)的輸入以及顯示棋盤布局的功能也都正常，那么我們可以把精力放在五子棋AI類的具體實(shí)現(xiàn)上。

現(xiàn)在，問題被抽象成，在一個(gè)15*15的二維數(shù)組中，1表示黑棋，0表示白棋，-1表示還沒有落子的空格，AI程序要做的是分析當(dāng)前的局面，運(yùn)用啟發(fā)式評(píng)估函數(shù)進(jìn)行搜索，找到對(duì)自己最有利（包括對(duì)對(duì)手限制最多）的地方落子，找到以后AI類返回這個(gè)點(diǎn)的坐標(biāo)。

深度優(yōu)先搜索似乎是可以完成這個(gè)任務(wù)的，但是很明顯，就算是將大量的不可能是最佳落子點(diǎn)的部分去掉，形成的搜索樹也是龐大到不可能在短時(shí)間內(nèi)搜索完成。

人下棋的時(shí)候?qū)嶋H上用的是一種試探性的方法。

首先假定在這個(gè)位置走了一步棋，然后思考對(duì)方會(huì)采取哪些策略，或者對(duì)我的棋進(jìn)行圍追堵截，或者是繼續(xù)下他的棋，然后我再根據(jù)對(duì)方可能采取的方法，看看我是不是有更好的回應(yīng)……

這個(gè)過程一直持續(xù)下去，直到若干個(gè)輪回以后，找到了一個(gè)滿意的走法為止。然后我在滿意的地方落子。

初學(xué)者可能只能看一、兩個(gè)輪次，而高手可以看幾個(gè)甚至十幾個(gè)輪次。

極大極小搜索策略，就是模擬人的這樣一種思維過程。

算法描述

極大極小搜索策略

這個(gè)搜索策略是考慮雙方對(duì)弈若干步以后，從可能的走法中找到一個(gè)相對(duì)較好的來落子，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。

T:=(s,MAX)
把s加入到OPEN表
CLOSED表為空
LOOP1:
IF OPEN EQ ()
THEN GO LOOP2
n:=FIRST(OPEN)
并將n加入到CLOSED表
IF n可以判斷輸贏
THEN f(x):=INF OR -INF OR 0, GO LOOP1
ELSE EXPAND(n) to {n_i}, ADD({n_i},T)
IF d(n_i)<k
THEN ADD({n_i},OPEN), GO LOOP1
ELSE 計(jì)算f(n_i), GO LOOP1
LOOP2:
IF CLOSED EQ NIL
THEN GO LOOP3
ELSE n_p:=FIRST(CLOSED)
IF n_p in MAX AND f(n_ci) in MIN 有值
THEN f(n_p):=max{f(n_cj)}, 從CLOSED刪除n_p
IF n_p in MIN AND f(n_ci) in MAX 有值
THEN f(n_p):=min{f(n_cj)}, 從CLOSED刪除n_p
GO LOOP2
LOOP3:

image

前面的代碼都是分別用兩部分代碼處理了極大節(jié)點(diǎn)和極小節(jié)點(diǎn)兩種情況，其實(shí)，可以只用一部分代碼，既處理極大節(jié)點(diǎn)也處理極小節(jié)點(diǎn)。

不同的是，前面的評(píng)估函數(shù)是針對(duì)指定的一方來給出分?jǐn)?shù)的，這里的評(píng)估函數(shù)是根據(jù)當(dāng)前搜索節(jié)點(diǎn)來給出分?jǐn)?shù)的。

每個(gè)人都會(huì)選取最大的分?jǐn)?shù)，然后，返回到上一層節(jié)點(diǎn)時(shí)，會(huì)給出分?jǐn)?shù)的相反數(shù)。

int AI::MINMAX_Search_With_AlphaBetaCutOff(int depth, int player) {
    int best = NEGATIVE_INFINITY;
    if (depth == this->depth) {
        return heuristic(player); 
    }
    list<Point> children; 
    for (int i = 0; i < GRID_NUM; ++i)
        for (int j = 0; j < GRID_NUM; ++j) {
            if (chessBoard[i][j] == NONE && nearby(i, j)) {
                children.emplace_back(Point(i, j));
            }
        }
    for (list<Point>::iterator it = children.begin(); it != children.end(); it++) {
        setPos(*it, player);
        int val = -MINMAX_Search_With_AlphaBetaCutOff(depth + 1, 1 - player); // 注意這里有個(gè)負(fù)號(hào)
        setPos(*it, NONE);
        if (val > best) {
            best = val;
            next = *it;
        }
    }
    return best;
}

MINMAX搜索的過程是把搜索樹的生成和格局估值這兩個(gè)過程分開來進(jìn)行，即先生成全部搜索樹，然后再進(jìn)行端結(jié)點(diǎn)靜態(tài)估值和倒退值的計(jì)算，這顯然會(huì)導(dǎo)致低效率。

事實(shí)上，如果生成某個(gè)結(jié)點(diǎn)A以后，馬上進(jìn)行靜態(tài)估值，得知f(A)=-∞之后，就可以斷定再生成其余結(jié)點(diǎn)即進(jìn)行靜態(tài)計(jì)算是多余的，可以馬上對(duì)MIN結(jié)點(diǎn)賦倒推值-∞，而絲毫不會(huì)影響MAX的最好優(yōu)先走步的選擇。

Alpha-Beta剪枝用于裁剪搜索樹中沒有意義的不需要搜索的樹枝，以提高運(yùn)算速度。

它的基本思想是根據(jù)上一層已經(jīng)得到的當(dāng)前最優(yōu)結(jié)果，決定目前的搜索是否要繼續(xù)下去。

如果某個(gè)著法的結(jié)果小于或等于Alpha，那么它就是很差的著法，因此可以拋棄。

如果某個(gè)著法的結(jié)果大于或等于Beta，那么整個(gè)節(jié)點(diǎn)就作廢了，因?yàn)閷?duì)手不希望走到這個(gè)局面，而它有別的著法可以避免到達(dá)這個(gè)局面。因此如果我們找到的評(píng)價(jià)大于或等于Beta，就證明了這個(gè)結(jié)點(diǎn)是不會(huì)發(fā)生的，因此剩下的合理著法沒有必要再搜索。

如果某個(gè)著法的結(jié)果大于Alpha但小于Beta，那么這個(gè)著法就是走棋一方可以考慮走的，除非以后有所變化。

if  depth = 0 or node is a terminal node
    return the heuristic value of node
if  Player = MaxPlayer // 極大節(jié)點(diǎn)
    for each child of node // 極小節(jié)點(diǎn)
        alpha := max(alpha, alphabeta(child, depth-1, alpha, beta, not(Player) ))   
        if beta <= alpha // 該極大節(jié)點(diǎn)的值>=alpha>=beta，該極大節(jié)點(diǎn)后面的搜索到的值肯定會(huì)大于beta，因此不會(huì)被其上層的極小節(jié)點(diǎn)所選用了。對(duì)于根節(jié)點(diǎn)，beta為正無窮
            break                            
    return alpha
else // 極小節(jié)點(diǎn)
    for each child of node // 極大節(jié)點(diǎn)
        beta := min(beta, alphabeta(child, depth-1, alpha, beta, not(Player) ))        if beta <= alpha // 該極大節(jié)點(diǎn)的值<=beta<=alpha，該極小節(jié)點(diǎn)后面的搜索到的值肯定會(huì)小于alpha，因此不會(huì)被其上層的極大節(jié)點(diǎn)所選用了。對(duì)于根節(jié)點(diǎn)，alpha為負(fù)無窮
            break    
   return beta

啟發(fā)式評(píng)估函數(shù)

如果我們有一個(gè)評(píng)估函數(shù)，可以對(duì)棋局進(jìn)行評(píng)估，那么每次在我下棋的時(shí)候，我就可以用這個(gè)評(píng)估函數(shù)對(duì)棋面上所有的我可能下棋的點(diǎn)都進(jìn)行評(píng)估，然后根據(jù)這個(gè)函數(shù)的評(píng)估值，來選擇對(duì)我最有利的點(diǎn)落子。

一般的，在極大極小搜索中，這個(gè)評(píng)估函數(shù)可以根據(jù)勢(shì)態(tài)優(yōu)劣特征來定義（主要用于對(duì)端結(jié)點(diǎn)的“價(jià)值”進(jìn)行度量），有利于程序方的勢(shì)態(tài)，為正，有利于用戶方的勢(shì)態(tài)，為負(fù)，勢(shì)均力敵的情況，為，并且，若，表示程序方贏了，若，表示用戶方贏了。

首先明確兩種特殊情況的評(píng)估值。

1. 恒為0。

則每次落子都一定是與棋盤上棋子互為鄰居的那么多棋子中最左上角的那個(gè)。

2. 隨機(jī)。

則每次落子將完全隨機(jī)。

當(dāng)然這樣兩種情況在實(shí)際操作中是不會(huì)被采用的，但是在程序編寫過程中卻可以用來作為調(diào)試的手段，檢查函數(shù)的正確性。

同時(shí)，我們定義的評(píng)估方法，也要在這兩種特殊情況下有意義。

定義兩個(gè)數(shù)值，ally表示自己一方的所有棋子的評(píng)估值的和，enemy表示對(duì)手一方的所有棋子的評(píng)估值的和。

遍歷棋盤，如果某位置上有棋子，則不是自己的就是對(duì)手的，那分別對(duì)自己和對(duì)手的棋子的每一個(gè)位置計(jì)算f(x)，加到評(píng)估值中，空位置不管。

for (int i = 0; i < GRID_NUM; i++) {
        for (int j = 0; j < GRID_NUM; j++) {
            if (chessBoard[i][j] == player)
                ally += f(Point(i, j), player);
            else if (chessBoard[i][j] == 1 - player)
                enemy += f(Point(i, j), 1 - player);
        }
    }

對(duì)于每個(gè)位置，計(jì)算f(x)。

首先一個(gè)很明顯的結(jié)論，如果我在某個(gè)位置下棋，在每一行最多影響到它左邊的4個(gè)，一直到它右邊的4個(gè)，加上自己，這一行就一共是9個(gè)點(diǎn)，更遠(yuǎn)的點(diǎn)不受它的影響。

同樣地，對(duì)于列、對(duì)角線、反對(duì)角線，也是一樣。

那么，每個(gè)點(diǎn)，我都可以得到4個(gè)方向上的可能被影響的點(diǎn)。每個(gè)方向上是9個(gè)點(diǎn)。

如果對(duì)這9個(gè)點(diǎn)做如下編碼：如果這個(gè)點(diǎn)沒有超過棋盤范圍，是自己顏色就記為1，是空記為0，是對(duì)手記為-，超過棋盤的點(diǎn)記為#，那么就可以構(gòu)建出一個(gè)長(zhǎng)度為9的字符串。

每個(gè)點(diǎn)都可以構(gòu)建這樣4個(gè)長(zhǎng)度為9的字符串。

例如，“111001111”表示在這9個(gè)點(diǎn)中，左邊3個(gè)都是我的棋，中間空了2個(gè)沒人下，右邊4個(gè)都是我的棋。

如果下面要輪到我下棋，而我就想要下在這兩個(gè)空中的某一個(gè)，顯然，落子在右邊這個(gè)我就贏了，而落子在左邊那個(gè)，我贏不了，且下一步一定會(huì)被對(duì)手堵死。

那么很容易想到的是，對(duì)于不同的狀態(tài)，應(yīng)當(dāng)是有不同的分?jǐn)?shù)。

簡(jiǎn)單考慮，如果我在長(zhǎng)度為9的這個(gè)字符串中找到了“111”，我就給10分，而找到了“1111”我就給20分，那么對(duì)于每個(gè)點(diǎn)構(gòu)建的4個(gè)長(zhǎng)度為9的字符串，我都可以通過計(jì)分的方法來給每個(gè)點(diǎn)一個(gè)分?jǐn)?shù)。

如果把這個(gè)分?jǐn)?shù)乘上這個(gè)點(diǎn)所在位置的重要程度，正好是可以作為這個(gè)點(diǎn)的評(píng)估值。

image

image

代碼實(shí)現(xiàn)

首先給出一些術(shù)語的介紹：

成五：五顆同色棋子連在一起

image-20210331082042815

活四：有兩個(gè)點(diǎn)可以形成五

image-20210331082104908

沖四：只有一個(gè)點(diǎn)能夠形成五，要么是一頭被對(duì)手堵住，要么是只有中間能連起來

image-20210331082113622

image-20210331082117952

image-20210331082122169

更多的狀態(tài)也是類似的。

下表給出了不同狀態(tài)的得分。

與圍棋的“金角銀邊草肚皮”不一樣，五子棋還是越往中間下，贏的機(jī)會(huì)也就越大，這也就是為什么先手落子一般落在最中間的點(diǎn)上。

那么，根據(jù)這個(gè)特性，我對(duì)棋盤的不同位置定義了不同的權(quán)重，即越往中間，重要程度越大。

image-20210331082224673

int AI::heuristic(int player) {
    int ally = 0; // 表示自己的棋子的評(píng)估值
    int enemy = 0; // 表示對(duì)手的棋子的評(píng)估值
    // 遍歷棋盤，分別對(duì)自己和對(duì)手的棋子的每一個(gè)位置計(jì)算f(x)，加到評(píng)估值中，空位置不管
    for (int i = 0; i < GRID_NUM; i++) {
        for (int j = 0; j < GRID_NUM; j++) {
            if (chessBoard[i][j] == player)
                ally += f(Point(i, j), player);
            else if (chessBoard[i][j] == 1 - player)
                enemy += f(Point(i, j), 1 - player);
        }
    }
    // 棋盤遍歷完畢，至此，已經(jīng)分別求出每個(gè)黑子和白子的評(píng)估值，并對(duì)應(yīng)的加入到對(duì)應(yīng)玩家的評(píng)估值中
    int heuristic = 10 * ally - enemy;
    return heuristic;
}

int AI::f(Point p, int color) {
    int x = p.x;
    int y = p.y;
    int score = 0; // 分?jǐn)?shù)
    int weight = PosValue[p.x][p.y]; // 權(quán)重，距離中間越近，權(quán)重越高，表示越是好的地段
    // 分別構(gòu)造4個(gè)方向的局面的字符串表示
    for (int dir = 0; dir < 4; dir++) {
        string s = "";
        // 計(jì)算該方向上的起始點(diǎn)坐標(biāo)
        int rBegin = x + DIRECTION[dir][0] * 4;
        int cBegin = y + DIRECTION[dir][1] * 4;
        // 坐標(biāo)遞增的方向
        int rDir = DIRECTION[dir][2];
        int cDir = DIRECTION[dir][3];
        // 計(jì)算該方向上的終止點(diǎn)坐標(biāo)
        int rEnd = x + rDir * 4;
        int cEnd = y + cDir * 4;
        // 當(dāng)行列沒到終點(diǎn)的時(shí)候（表示沒有收集齊9個(gè)點(diǎn)），循環(huán)
        int r = rBegin;
        int c = cBegin;
        while (r != rEnd || c != cEnd) {
            // 如果這個(gè)點(diǎn)沒有超過棋盤范圍，是自己顏色就記為1，是空記為0，是對(duì)手記為-，超過棋盤的點(diǎn)記為#
            if (isValid(r, c))
                if (chessBoard[r][c] == color) s += "1";
                else if (chessBoard[r][c] == NONE) s += "0";
                else s += "-";
            else
                s += "#";
            r += rDir;
            c += cDir;
        }
        // 如果構(gòu)建出來的字符串中包含“成五”的子串，加上其分?jǐn)?shù)
        if (s.find(CHENG_5_STRING) != string::npos) {
            score += CHENG_5_SCORE;
        }
        // 如果包含“活四”的子串，加上其分?jǐn)?shù)
        if (s.find(HUO_4_STRING) != string::npos) {
            score += HUO_4_SCORE;
        }
        // “沖四”不止一種情況，如果包含任意一個(gè)子串，加上其分?jǐn)?shù)，下面的情況同理
        if (s.find(CHONG_4_STRING_1_1) != string::npos
            || s.find(CHONG_4_STRING_1_2) != string::npos
            || s.find(CHONG_4_STRING_2_1) != string::npos
            || s.find(CHONG_4_STRING_2_2) != string::npos
            || s.find(CHONG_4_STRING_3) != string::npos) {
            score += CHONG_4_SCORE;
        }
        if (s.find(DAN_HUO_3_STRING) != string::npos) {
            score += DAN_HUO_3_SCORE;
        }
        if (s.find(TIAO_HUO_3_STRING_1_1) != string::npos
            || s.find(TIAO_HUO_3_STRING_1_2) != string::npos) {
            score += TIAO_HUO_3_SCORE;
        }
        if (s.find(MIAN_3_1_1) != string::npos
            || s.find(MIAN_3_1_2) != string::npos
            || s.find(MIAN_3_2_1) != string::npos
            || s.find(MIAN_3_2_2) != string::npos
            || s.find(MIAN_3_3_1) != string::npos
            || s.find(MIAN_3_3_2) != string::npos
            || s.find(MIAN_3_4_1) != string::npos
            || s.find(MIAN_3_4_2) != string::npos
            || s.find(MIAN_3_5) != string::npos
            || s.find(MIAN_3_6) != string::npos) {
            score += MIAN_3_SCORE;
        }
        if (s.find(HUO_2_STRING_1) != string::npos
            || s.find(HUO_2_STRING_2) != string::npos
            || s.find(HUO_2_STRING_3) != string::npos) {
            score += HUO_2_SCORE;
        }
        if (s.find(MIAN_2_1_1) != string::npos
            || s.find(MIAN_2_1_2) != string::npos
            || s.find(MIAN_2_2_1) != string::npos
            || s.find(MIAN_2_2_2) != string::npos
            || s.find(MIAN_2_3_1) != string::npos
            || s.find(MIAN_2_3_2) != string::npos
            || s.find(MIAN_2_4) != string::npos) {
            score += MIAN_2_SCORE;
        }
    }
    // 四個(gè)方向的分?jǐn)?shù)都加起來，乘上權(quán)重
    return score * weight;
}

還有一些必要的說明。

第一，在互為鄰居的判斷標(biāo)準(zhǔn)中，我還是采用了一步以內(nèi)作為鄰居。

bool AI::nearby(int x, int y) {
    // 檢索周圍的8個(gè)點(diǎn)，是不是有棋子
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (i == 0 && j == 0) continue;
            if (isValid(x + i, y + j) && chessBoard[x + i][y + j] != NONE)
                return true;
        }
    }
    // 注：必要的時(shí)候，鄰居的定義可以放寬到2步以內(nèi)
    return false;
}

事實(shí)上，在高智能的AI中，往往會(huì)把鄰居的定義放寬到兩步以內(nèi)，即，某個(gè)點(diǎn)周圍的8個(gè)點(diǎn)和它是鄰居，而那8個(gè)點(diǎn)的鄰居也被認(rèn)為是自己的鄰居。

我的代碼中采取了一步以內(nèi)的點(diǎn)作為鄰居，即自己周圍的8個(gè)點(diǎn)，必要時(shí)，可以修改成兩步以內(nèi)。

這個(gè)地方不影響程序的正確性。

第二，啟發(fā)式函數(shù)的評(píng)估值為自己的評(píng)估值減去對(duì)手的評(píng)估值。

int heuristic = 10 * ally - enemy;

這里我加大了自己的權(quán)重，更加注重進(jìn)攻性，也就是對(duì)自己有利的部分所占比重更高。

修改這里的權(quán)重不影響程序正確性，也不影響AI的智能程度，只對(duì)采取策略的理解所有偏重。

（注重進(jìn)攻還是注重防守，只是策略的不同，沒有優(yōu)劣之分）。

這個(gè)地方也不影響程序的正確性。

實(shí)驗(yàn)結(jié)果

下面給出幾種落子的截圖。

image-20210331082416376

白子能夠堵住黑子，且順便將自己連成2個(gè)，所以堵在上面而不是下面

image-20210331082424417

因?yàn)橐呀?jīng)堵住了一頭，所以另一頭暫時(shí)沒有威脅，所以優(yōu)先連長(zhǎng)自己的

image-20210331082432973

已經(jīng)黑子沖4了，所以不得不堵住黑子，而不是再加長(zhǎng)自己從3變4

image-20210331082442625

image-20210331082451825

完整代碼

程序下載：

https://cloud.jxtxzzw.com/#/s/j1nhR

代碼倉庫：

https://github.com/jxtxzzw/gobang_ai

https://gitlab.jxtxzzw.com/jxtxzzw/gobang_ai