关于前端: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/...