关于前端:FEGAME五子棋AI博弈算法实践

最终目标

应用 nodejs 实现控制台人机对战五子棋，人先着，一方赢后进行交互。（如下图 gif）

程序次要形成局部

本篇按由易到难的程序别离讲述以下次要局部的实现

• drawBoard 棋盘场面绘制
• isEnd 判断该局完结
• getMark 以后场面评分
• abnegamax 一个 minimax 算法，用于单方对弈的决策树搜寻

drawBoard 棋盘场面绘制

通过映射 1: '●', '-1': '○', 0: '+' 场面绘制输入到控制台

function drawBoard(board, cursor) {if (typeof board === 'string')
        board = board.replace(/(\d{16})/g, "$1,").slice(0, -1).split(',').map(v => v.split('').map(v => v == 2 ?'-1' : v))
    console.log((cursor ? "人" : "机") + "0 1 2 3 4 5 6 7 8 9 A B C D E F")
    for (let i = 0; i < board.length; i++)
        console.log((i > 9 ? i : '' + i) +' ' + board[i].map((v, j) => {if (cursor && cursor.x === j && cursor.y === i)
                return '◎'
            return ({1: '●', '-1': '○', 0: '+'})[v]
        }).join(''))
}

人着子时，通过方向键管制 '◎' 代表将落子的地位, 当按回车时确定落子

process.stdin.on('keypress', (str, key) => {if (key.name === 'return') { } else {switch (key.name) {
            case 'up': cursor.y = cursor.y - 1; break;
            case 'down': cursor.y = cursor.y + 1; break;
            case 'left': cursor.x = cursor.x - 1; break;
            case 'right': cursor.x = cursor.x + 1; break;
        }
        cursor.x = Math.min(15, Math.max(0, cursor.x))
        cursor.y = Math.min(15, Math.max(0, cursor.y))
        drawBoard(chessBoard.join(''), cursor)
    }

isEnd 判断该局完结

每当落子后，通过统计以后落子地位为终点的 4 条线（横竖撇捺）是否有五子连珠

function isEnd(x, y, chessBoard) {let vect = [[-1, 0], [-1, 1], [0, 1], [1, 1]]
    let qi = chessBoard[y][x]
    for (let i = 0; i < 4; i++) {
        let a = 1; let b = 1;
        while (chessBoard[y + vect[i][0] * a] && chessBoard[y + vect[i][0] * a][x + vect[i][1] * a] === qi) 
            a++
        while (chessBoard[y - vect[i][0] * b] && chessBoard[y - vect[i][0] * b][x - vect[i][1] * b] === qi) 
            b++
        if (a + b > 5) return true
    }
    return false;
}

getMark 以后场面评分

遍历每个格子的 4 条线（横竖撇捺）的连子数评分求和作为场面分
打分参考：

function getScore(cnt, flag) {
    flag = flag ? 0 : 1;
    switch (cnt) {case 5: return 1 << (15 + flag)
        case 4: return 1 << (11 + flag)
        case 3: return 1 << (7 + flag)
        case 2: return 1 << (5 + flag)
        default: return 1
    }
}

minimax 决策算法相干

能够间接看视频 https://www.bilibili.com/vide… 学习
以下为 nodejs 实现形容

对于节点的数据结构

class Nod {constructor({ board, cur, nxt, deep, pos}) {
        this.board = board;
        this.cur = cur;
        this.nxt = nxt;
        this.deep = deep;
        this.pos = pos;
        this.mark = getMark(this.board);
    }
    children() {const arr = [];
        const reg = /0/g;
        while (reg.exec(this.board) != null) {
            arr.push(new Nod({board: this.board.slice(0, reg.lastIndex - 1) + this.nxt + this.board.slice(reg.lastIndex),
                cur: this.nxt,
                nxt: this.cur,
                deep: this.deep + 1,
                pos: [...this.pos, reg.lastIndex - 1]
            }));
        }
        return arr;
    }
}

minimax

又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法。

这个算法就是一个树形构造的递归算法，每个节点的孩子和父节点都是对方玩家，所有的节点被分为极大值（我方）节点和极小值（对方）节点。

也就是每次对方玩家都做最佳决策的状况下的决策门路下，我方仍旧是劣势最大的那个

function minimax(node, MAXDEEP) {if (node.deep >= MAXDEEP) return node;
    let arr = node.children().map(v => minimax(v, MAXDEEP));
    if (node.deep % 2)//min
        return arr.sort((a, b) => a.mark - b.mark)[0]
    else
        return arr.sort((a, b) => b.mark - a.mark)[0]
}

negamax

“ 负极值 (Negamax) 算法 ” 是在 ” 极大极小值 (MiniMax) 算法 ” 提出近 20 年后才做一个小改良, 在程序性能和效率上是没有区别的 … 惟一不同之处是前者更看起来简洁 (后者一会儿取极大, 一会儿取极小). 你能够发现 NegaMax 在传递参数时用 -alpha, 来起到反向取极大(也就是负极大值) 的作用, 因而不须要一次判断取极大, 一次判断取最极小, 实际上它也是在 ” 正极大 ” 和 ” 负极大 ” 间互相交替进行, 原理是一样而实现手法不同。

function negamax(node, MAXDEEP) {if (node.deep >= MAXDEEP) return node;
    let arr = node.children();
    let bestV = arr.map(v => {const n = negamax(v, MAXDEEP);
        n.mark = -n.mark
        return n;
    }).sort((a, b) => b.mark - a.mark)[0];
    return bestV;
}

minimax 做 alpha-beta 剪枝

在上述的极大极小算法中，MIN 和 MAX 过程将所有的可能性省搜寻树，而后再从端点的估计值倒推计算，这样的效率十分低下。而 α - β 算法的引入能够进步运算效率，对一些非必要的估计值进行舍弃。

其策略是进行深度优先搜寻，当生成结点达到规定深度时，立刻进行动态预计，一旦某一个非端点的节点能够确定倒推值的时候立刻赋值，节省下其余分支拓展到节点的开销。

const MAXN = 1 << 28;
const MINN = -MAXN;
function abminimax(node, MAXDEEP, a, b) {if (node.deep >= MAXDEEP) return node
    let arr = node.childrenit();
    let bestV;
    if (node.deep % 2) {//min
        bestV = {mark: MAXN};
        for (let child of arr) {const val = abminimax(child, MAXDEEP, a, b)
            if (val.mark < bestV.mark) {
                bestV = val;
                b = bestV.mark
                if (a >= b) break;
            }
        }
    } else {bestV = { mark: MINN};
        for (let child of arr) {const val = abminimax(child, MAXDEEP, a, b)
            if (val.mark > bestV.mark) {
                bestV = val;
                b = bestV.mark
                if (a >= b) break;
            }
        }
    }
    return bestV;
}

negamax 做 alpha-beta 剪枝

联合两者劣势，代码精简且剪枝优化

const MINN = -(1 << 28);
const MAXDEEP = 2;
function abnegamax(node, a, b) {if (node.deep >= MAXDEEP) return node
    let arr = node.childrenit();
    let bestV = {mark: MINN};
    for (let child of arr) {const val = abnegamax(child, -b, -Math.max(a, bestV.mark));
        val.mark = -val.mark
        if (val.mark > bestV.mark) {
            bestV = val;
            if (bestV.mark >= b) break;
        }
    }

    return bestV;
}

源码

https://github.com/Seasonley/…