博弈树(二)

蓝冰大侠

上篇中提到的程序 运行时间太长,进行了一些优化

首先,减小了棋盘大小,五列,四行.

其次,使用了A*算法,每次优先搜索最有希望取胜的子树.

源代码如下:

<?php

//设置执行时间无限
set_time_limit ( 0 );

echo "begin!!!\n";

$width = 5; //棋盘宽度
$height = 4; //棋盘高度


//初始棋盘(x:0->6;y:0-5)
$board = array (array (' ', ' ', ' ', ' ', ' ', ' ' ), array (' ', ' ', ' ', ' ', ' ', ' ' ), array (' ', ' ', ' ', ' ', ' ', ' ' ), array (' ', ' ', ' ', ' ', ' ', ' ' ), array (' ', ' ', ' ', ' ', ' ', ' ' ), array (' ', ' ', ' ', ' ', ' ', ' ' ), array (' ', ' ', ' ', ' ', ' ', ' ' ) );

//当前棋手:红
$oper = 'R';

//计算最优结果
print process ( $oper, '' );

//计算当前状态最优结论
//返回值:1 我胜了, -1 无论如何,对方胜了, 0 最终会平局
function process($oper, $path) {
    global $board, $width, $height;
   
    //记录每一种落子方式的估计值及落子点
    $every = array ();
   
    //所有可能的落子处
    for($x = 0; $x < $width; $x ++) {
        //本列已经满
        if ($board [$x] [$height - 1] != ' ')
            continue;
           
        //找到本列的一个最低的落子位
        for($y = 0; $y < $height - 1; $y ++) {
            if ($board [$x] [$y] == ' ')
                break;
        }
       
        //计算4种直线方向的最大连续棋子数
        list ( $max, $sum ) = max4 ( $oper, $x, $y );
       
        //当前棋手有一种落子方法可以取胜,其它方法不用继续计算
        if ($max >= 4) {
            echo $path . ' ' . $oper . '!' . "\n";
            flush ();
            return 1;
        }
       
        //记录每一种落子时的估计值(八向合计再加上最大值,以增加最大值的作用)
        $every [] = array ($max + $sum, $x, $y );
    }
   
    //按估计值排序
    $every = sortArrayDesc ( $every );
   
    //按估计值先后开始尝试
    foreach ( $every as $k => $once ) {
        $x = $once [1];
        $y = $once [2];
       
        //落子,并计算对方的计算结果,之后恢复棋盘
        $board [$x] [$y] = $oper;
        $other = process ( $oper == 'R' ? 'G' : 'R', $path . $x );
        $board [$x] [$y] = ' ';
       
        //如果对方计算结果为1(取胜),那么表明自己不能在此落子
        if ($other == 1)
            continue;
           
        //如果对方计算结果为-1(必输),那么自己一定要在此落子
        if ($other == - 1)
            return 1;
    }
   
    //自己无论在哪里落子,都是平局
    return 0;
}

//根据数组中的第0个元素对整个二维数组进行从大到小排序(交换排序)
function sortArrayDesc($array) {
    $count = count ( $array );
    if ($count < 2) {
        return $array;
    }
    for($i = 0; $i < $count - 1; $i ++) {
        if ($array [$i] [0] < $array [$i + 1] [0]) {
            $temp = $array [$i];
            $array [$i] = $array [$i + 1];
            $array [$i + 1] = $temp;
        }
    }
    return $array;
}

//判断4种直线方向的最大连续长度(包括自己)
function max4($oper, $x, $y) {
    $n = max8 ( $oper, $x, $y, 0, 1 );
    $s = max8 ( $oper, $x, $y, 0, - 1 );
   
    $nw = max8 ( $oper, $x, $y, - 1, 1 );
    $se = max8 ( $oper, $x, $y, 1, - 1 );
   
    $w = max8 ( $oper, $x, $y, - 1, 0 );
    $e = max8 ( $oper, $x, $y, 1, 0 );
   
    $sw = max8 ( $oper, $x, $y, - 1, - 1 );
    $ne = max8 ( $oper, $x, $y, 1, 1 );
   
    $max = max ( array ($n + 1 + $s, $nw + 1 + $se, $w + 1 + $e, $sw + 1 + $ne ) );
    $sum = $n + $s + $nw + $se + $w + $e + $sw + $ne;
   
    //返回最大值及合计
    return array ($max, $sum );
}

//判断8种射线方向有几个连续同色棋子
function max8($oper, $x, $y, $x_offset, $y_offset) {
    global $board;
    for($i = 1; $i <= 3; $i ++) {
        $xx = $x + $x_offset * $i;
        $yy = $y + $y_offset * $i;
        if (! inRange ( $xx, $yy ))
            return $i - 1;
        if ($board [$xx] [$yy] != $oper)
            return $i - 1;
    }
    return 3;
}

//判断坐标是否在棋盘内
function inRange($x, $y) {
    global $width, $height;
    if ($x < 0 or $x >= $width or $y < 0 or $y >= $height)
        return false;
    return true;
}