如何評估它？

Update2: Tricont建議我在這里使用Minmax演算法。但我認為這對這個問題來說可能是一種矯枉過正。這不是人類與AI的游戲。我只需要確定導致x被迫獲勝的位置。如果不存在這樣的位置，那么肯定不是被迫獲勝（這可能是x輸掉比賽或平局）。

uj5u.com熱心網友回復：

每一個欄位都被玩家1覆寫，被玩家2覆寫，或者空著。這有3^{16}$的可能性，這比1億要少得多。

根據X與Y所覆寫的場數，將每個位置標記為X、Y或 "不允許"：相同的數字->；X在下，多一個X場->；Y在下，其他都->；不允許。

將每個允許的位置標記為贏、輸、平或未知。對手的四個顏色=輸了，自己的四個顏色=不允許，所有填上的東西=平局，否則就是未知。

現在遍歷所有未知位置。任何走到 "丟失"（對對手而言）位置的棋步-->；贏。任何走到 "未知 "位置的棋步--> 未知。任何走到 "平局 "的棋步--gt；平局。否則，所有的棋步都是為對手贏得的--> 失去的。

uj5u.com熱心網友回復：

Minimax是這個問題的解決方案。

這里最重要的想法是，棋手O可以對平局感到滿意，而且當它在網格上任何可能的四線中至少放了一個O單元格時，它就可以確定至少是平局。有10條這樣的線（4條水平線，4條垂直線，2條對角線）。要讓O在這10條線上都出現并不難。例如，如果O占據了這4個位置，那么X就不可能贏：

...o
.o..
..o.
o...

這意味著O很容易阻止X獲勝，因此預計在棋盤完全被填滿之前，搜索不必下棋，因為雙方中的一個棋手已經在對局中更早地達到了他們的目標。

評估功能

• X的目標是獲勝。
• O的目標是贏或平。

因此，評估函式可以檢查所有10條四線，看看最后下棋的棋手是否完全占據了這樣一條線。如果發現了，評估函式應該回傳1--表示該玩家已經達到了他們的目標。

接下來，評估函式應該檢查O是否是最后下棋的玩家。如果是的話，它可以再次檢查所有10條四線，看看O是否在每條線中至少有一個存在。如果是這樣的話，它也應該回傳1--表明O已經達到了他們的目標。

在所有其他情況下，評估函式可以回傳 0 --表明還沒有明確的答案。

由于唯一的結果是0或1，評估函式也可以回傳一個布林值。我將把這個函式稱為happy。

Minimax

• -1
• -1：最后出牌的玩家不能達到他們的目標
。
• 0：未決定
。
• 1：最后出場的玩家可以強行達到他們的目標
。

Minimax將執行所有對手的棋步，并找出哪個棋步給出了 "最佳 "結果，在本例中，評估值為1。如果找到了這樣的棋步，那么前一個棋手將得到他們最后一步棋的否定評估值，即-1。類似的邏輯也發生在其他可以從minimax的遞回呼叫中得到的評估值上。

棋盤表示法

四線也可以用位圖來表示，這樣通過將棋手的位圖與之疊加，就可以很容易地檢測到勝利。

棋步以數字表示，從0到15.

記憶法

具體實施

class TicTacToe {
    static memo = new Map; // for memoization

    constructor(str) {
        str = str.toLowerCase().replace(/[^.xo]/gi, "")。
        if (str.length !== 16) throw "Invalid board size" 。
        this.players = [0x0000, 0x0000]; //為兩位玩家提供位圖。
        this.lines = [ //贏錢線的位圖].
            0xF000, 0x0F00, 0x00F0, 0x000F,
            0x1111, 0x2222, 0x4444, 0x8888,
            0x1248, 0x8421。
        ];
        this.turn = 0; //0 or 1.
        //收集移動到位圖。
        let bit = 1;
        let balance = 0;
        for (let ch of str) {
            let player = "xo".indexOf（ch）。
            if (player >= 0) {
                this.players[player] ^= bit;
                balance  = player || -1;
            }
            bit *= 2;
        }
        if (balance != 0) throw "X和O的數量應該相等"。
    }
    doMove（move） {
        this.players [this.turn] ^= 1 << move;
        this.turn ^= 1;
    }
    undoMove（move） {
        this.turn ^= 1;
        this.players [this.turn] ^= 1 << move;
    }
    happy（）{
        ///回傳玩家（最后一次移動）是否達到了他們的目標（布林值）。
        //對于 "X "來說，這意味著他們有4排。
        // 對于 "O"，這意味著他們有4個在一排或在所有10行都有出現。
        let mask = this. players[1 - this.turn] 。
        for (let line of this.lines) {
            if ((line & mask) === line) return true; //游戲結束。最后一步是贏家。
        }
        if (this.turn ==1) return false。
        //檢查最后一個玩家（"O"）是否不能輸：
        for (let line of this.lines) {
            if ((line & mask) == 0) return false; //對手仍然可以在這里獲勝。
        }        
        return true; // Second player is happy with draw 
    }
    getMoveList（）{
        let occupied = this. players[0] ^ this.players[1] 。
        let moveList = []; 
        for (let move = 0; move < 16; move  ) {
            if ((( occupied >> move) & 1) == 0) moveList.push（move）。
        }
        return moveList;
    }
    minimax() { // return value for player that just played（-1, 0 or 1）.
        let key = (this.players[0] < < 16)   this.players[1] 。
        let value = TicTacToe.memo.get（key）; // Using memoization.
        if (value ==undefined) { // Not encountered before
            value = 1;
            if (!this.happy()) { // Undecided?
                for (let move of this.getMoveList() ） {
                    this.doMove（move）。  
                    //對對手有利的是對當前玩家不利的是：。
                    value = Math.min(value, -this.minimax()）。)
                    this.undoMove（move）。
                    if (value == -1) break; //對手可以達到目標。
                }
            }
            TicTacToe.memo.set(key, value); // Memoize... }
        }
        return value。
    }
    bestMove() { // Returns winning move (0...15) for X or -1 if none found.
        if (this.happy() return -1; //"O "已經確保了至少一個平局。
        for (let move of this.getMoveList()) {
            this.doMove（move）。
            let value = this.minimax（）。
            this.undoMove（move）。
            if (value == 1) return move; // forced win: return this winning move.
        }
        return -1; //沒有發現強制勝利。
    }
    toString() { // 為了方便列印。
        let str = ""/span>;
        for (let bit = 1; bit < 0x10000; bit *=  2) {
            if (this.players[0] & bit) str  = "x" /span>。
            else if (this. players[1] & bit) str  = "o"/span>。
            else str  = "。"。
            if (bit & 0x8888) str  = " 。
"。
        }
        return str。
    }
}

let game;

//測驗案例1:
game = new TicTacToe(`)
o...
.ox.
.xxx
xooo`）。)
console.log(game.toString())。
console.log("bestMove() returned", game.bestMove() ）。)

//測驗案例2:
game = new TicTacToe(`)
....
.ox.
.xo.
....`）。)
console.log(game.toString())。
console.log("bestMove() returned", game.bestMove() ;

人們可以想到許多優化措施，但由于這已經在可接受的時間內運行，所以我讓它像這樣。

標籤：

上一篇：使用SpringBoot的ArrayBlockingQueue

下一篇：ESP-IDF MQTT 示例入門