博弈树(二)

野性酷女 2022-09-19 10:52 130阅读 0赞

上篇中提到的程序 运行时间太长,进行了一些优化  
  
首先,减小了棋盘大小,五列,四行.  
  
其次,使用了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;  
\}

阅读(174) | 评论(0) | 转发(0) |

上一篇：博弈树

下一篇：\[转\]快速构建实时抓取集群