欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

五子棋AI算法简易实现（三）

程序员文章站 2024-03-16 22:30:52
...

电脑AI篇

（1）评估函数

对当前局面的评估函数在实现五子棋的AI算法的过程中是十分重要的，它能够帮助电脑很好的进行对当前棋盘中双方优势的评估，以便于电脑采取更优的下棋策略，是后面的minimax算法和AlphaBeta剪枝算法中作为一个节点权值的重要评估标准。

当前版本下，我将评估函数分成了五个部分：评估标准、棋盘的切分、评估函数针对各种棋型的定义、对棋盘上每一个位置的点估值、统计估值总和。

（1）评估标准

对五子棋的棋型进行量化，每种棋型对应一个分值，评估函数可根据这一标准对不同的棋型进行估值

const judge_standard = {
    //连五
    FIVE: 300000,
    //活四
    FOUR: 10000,
    //活三
    THREE: 1000,
    //活二
    TWO: 100,
    //活一
    ONE: 10,
    //眠四
    BLOCK_FOUR: 1000,
    //眠三
    BLOCK_THREE: 100,
    //眠二
    BLOCK_TWO: 10,
    //眠一
    BLOCK_ONE: 1
};
（2）棋盘的切分

棋盘上的每个点都有横，竖，右上斜线，右下斜线四个有效方向。在估值的过程中，为了方便计算，可将每个方向提取出来分别放到四个一维数组中。此函数的参数分别为：当前位置所在行（row），当前位置所在列（col），当前棋盘（matrix）

_pointDirection: function( row, col, matrix) {

    //公用部分
    var result = new Array(4);
    var count;
    var a = row;
    var b = col;

    //按四个方向划分四个一维数组
    //横线
    var horizon = [];
    for(var i = 0; i < 15; i++)
        horizon[i] = matrix[row][i];

    //竖直线
    var vertical = [];
    for(var i = 0; i < 15; i++)
        vertical[i] = matrix[i][col];

    //右上斜线
    var rightTop = [];
    while(a < 14 && b > 0){ a++; b--; };
    for(var i = 0; a >= 0 && b < 15; i++)
        rightTop[i] = matrix[a--][b++];

    //右下斜线
    a = row;
    b = col;
    var rightDown = [];
    while(a > 0 && b > 0){ a--; b--; };
    for(var i = 0; a < 15 && b < 15; i++)
        rightDown[i] = matrix[a++][b++];

    //统计部分
    //横线
    var horizonCheck = 'b'+horizon.join('')+'b';

    //竖直线
    var verticalCheck = 'b'+vertical.join('')+'b';

    //右上斜线
    var rightTopCheck = 'b'+rightTop.join('')+'b';

    //右下斜线
    var rightDownCheck = 'b'+rightDown.join('')+'b';

    return [horizonCheck, verticalCheck, rightTopCheck, rightDownCheck];
}
（3）评估函数针对各种棋型的定义

五子棋的各种棋型的样式可参考这篇文章，本文在这个基础上修改并增加了部分内容

/*  color代表当前颜色, -1表示空位
连五：color+color+color+color+color

活四：(-1)+color+color+color+color+(-1)

眠四：(!color)+color+color+color+color+(-1) || 
      color+color+color+(-1)+color || 
      color+color+(-1)+color+color

活三：(-1)+color+color+color+(-1) ||
      color+color+(-1)+color

眠三：(!color)+color+color+color+(-1)+(-1) ||
      (!color)+color+color+(-1)+color+(-1) ||
      (!color)+color+(-1)+color+color+(-1) 

活二：(-1)+(-1)+color+color+(-1)+(-1) || 
      (-1)+color+(-1)+color+(-1) ||
      color+(-1)+(-1)+color

眠二：(!color)+color+color+(-1)+(-1)+(-1) ||
      (!color)+color+(-1)+color+(-1)+(-1) ||
      (!color)+color+(-1)+(-1)+color+(-1)

活一：(-1)+color+(-1)

眠一：(!color)+color+(-1)

*/

我们将以上的情况用代码翻译一下就是下面的这些正则表达式

//b代表边界，e代表空位，color代表当前颜色，ncolor代表相反的颜色
_regExpConstructor: function ( chessColor ){
    var regex = new Array(31);
    var color = parseInt(chessColor);
    var ncolor = color == 1? 0 : 1;

    //连五
    regex[0] = new RegExp(color+''+color+''+color+''+color+''+color, 'g');
    //活四
    regex[1] = new RegExp('e'+color+''+color+''+color+''+color+'e', 'g');
    //眠四
    regex[2] = new RegExp(('('+ncolor+'|b)')+''+color+''+color+''+color+''+color+'e', 'g');
    regex[3] = new RegExp('e'+color+''+color+''+color+''+color+''+('('+ncolor+'|b)'), 'g');
    regex[4] = new RegExp(color+''+color+'e'+color+''+color, 'g');
    regex[5] = new RegExp(color+'e'+color+''+color+''+color, 'g');
    regex[6] = new RegExp(color+''+color+''+color+'e'+color, 'g');
    //活三
    regex[7] = new RegExp('e'+'e'+color+''+color+''+color+'e'+'e', 'g');
    regex[8] = new RegExp(('('+ncolor+'|b)')+'e'+color+''+color+''+color+'e'+'e', 'g');
    regex[9] = new RegExp('e'+'e'+color+''+color+''+color+'e'+('('+ncolor+'|b)'), 'g');
    regex[10] = new RegExp('e'+color+'e'+color+''+color+'e', 'g');
    regex[11] = new RegExp('e'+color+''+color+'e'+color+'e', 'g');
    //眠三
    regex[12] = new RegExp(('('+ncolor+'|b)')+'e'+color+''+color+''+color+'e'+('('+ncolor+'|b)'), 'g');
    regex[13] = new RegExp(('('+ncolor+'|b)')+''+color+''+color+''+color+'e'+'e', 'g');
    regex[14] = new RegExp('e'+'e'+color+''+color+''+color+''+('('+ncolor+'|b)'), 'g');
    regex[15] = new RegExp(('('+ncolor+'|b)')+''+color+''+color+'e'+color+'e', 'g');
    regex[16] = new RegExp('e'+color+'e'+color+''+color+''+('('+ncolor+'|b)'), 'g');
    regex[17] = new RegExp(('('+ncolor+'|b)')+''+color+'e'+color+''+color+'e', 'g');
    regex[18] = new RegExp('e'+color+''+color+'e'+color+''+('('+ncolor+'|b)'), 'g');
    //活二
    regex[19] = new RegExp('e'+'e'+color+color+'e'+'e', 'g');
    regex[20] = new RegExp('e'+color+'e'+color+'e', 'g');
    regex[21] = new RegExp('e'+color+'e'+'e'+color+'e', 'g');
    //眠二
    regex[22] = new RegExp(('('+ncolor+'|b)')+''+color+''+color+'e'+'e'+'e', 'g');
    regex[23] = new RegExp('e'+'e'+'e'+color+''+color+''+('('+ncolor+'|b)'), 'g');
    regex[24] = new RegExp(('('+ncolor+'|b)')+''+color+'e'+color+'e'+'e', 'g');
    regex[25] = new RegExp('e'+'e'+color+'e'+color+''+('('+ncolor+'|b)'), 'g');
    regex[26] = new RegExp(('('+ncolor+'|b)')+''+color+'e'+'e'+color+'e', 'g');
    regex[27] = new RegExp('e'+color+'e'+'e'+color+''+('('+ncolor+'|b)'), 'g');
    //活一
    regex[28] = new RegExp('e'+color+'e', 'g');
    //眠一
    regex[29] = new RegExp(('('+ncolor+'|b)')+''+color+'e', 'g');
    regex[30] = new RegExp('e'+color+('('+ncolor+'|b)'), 'g')

    //console.log(regex);

    return regex;
}
（4）对棋盘上每一个位置的点估值

目前的版本，我采用了字符串正则表达式的形式进行棋型的匹配，效果感觉还可以。

_pointCounter: function( strList, regExpList ){
    var count = 0;
    var size = 0; 
    for( var i = 0; i < 4; i++){
        for(var j = 0; j < 31; j++){
            size = strList[i].match(regExpList[j]) == null? 0: strList[i].match(regExpList[j]).length;
            if(j == 0){
                count += (size) * judge_standard.FIVE;
            }
            else if(j == 1){
                count += (size) * judge_standard.FOUR;
            }
            else if(j >= 2 && j <= 6){
                count += (size) * judge_standard.BLOCK_FOUR;
                if( j >= 4)
                    count += (size) * judge_standard.FOUR / 5;
            }
            else if(j >= 7 && j <= 11){
                count += (size) * judge_standard.THREE;
            }
            else if(j >= 12 && j <= 18){
                count += (size) * judge_standard.BLOCK_THREE;
            }
            else if(j >= 19 && j <= 21){
                count += (size) * judge_standard.TWO;
            }
            else if(j >= 22 && j <= 27){
                count += (size) * judge_standard.BLOCK_TWO;
            }
            else if(j == 28){
                count += (size) * judge_standard.ONE;
            }
            else{
                count += (size) * judge_standard.BLOCK_ONE;
            }
            strList[i].replace(regExpList[j], "-");
        }
    }
    return count;
}

PS：正则表达式的匹配要从五连开始，眠一结束，在匹配完成后要将匹配到的字段用特殊符号（这里使用“-”）替代，避免因为重复计算所导致的估值误差过大。

（5）统计估值总和

这一步思路非常简单，就是将前一步中同一方在棋盘上每个位置下子所得到的估值加起来即可。

//1表示黑棋，0表示白棋，也就是正则表达式生成函数_regExpConstructor中的参数chessColor
const BLACK_REG = ModuleEvaluate._regExpConstructor(1);
const WHITE_REG = ModuleEvaluate._regExpConstructor(0);
//matrix 表示当前棋盘
evaluate: function( matrix ){
    var black_value = 0; //黑棋的估值总和
    var white_value = 0; //白棋的估值总和
    for(var i = 0; i < 15; i++){
        for(var j = 0; j < 15; j++){
            if(matrix[i][j] == 1){
                black_value += this._pointCounter(this._pointDirection(i, j, matrix), BLACK_REG);
            }
            else if(matrix[i][j] == 0){
                white_value += this._pointCounter(this._pointDirection(i, j, matrix), WHITE_REG);
            }
            else{
                continue;
            }
        }
    }

    return (black_value - white_value); //返回双方权值之差，正数表示黑棋的局势比较有利，负数表示白棋的局势有利，0表示双方不分伯仲
}

以上就是目前版本的评估函数，虽然有点简陋，但是效果暂时看来还行，有待改进。

项目地址：https://github.com/huangzhutao/Gomoku.git

相关标签： 五子棋AI javascript

上一篇： MySQL45讲读书笔记 36讲为什么临时表可以重名

下一篇： 214最短回文串（KMP算法——困难）

推荐阅读