|
教计算机玩Tic-Tac-Toe 相对于西洋跳棋、国际象棋和围棋，我们的Tic-Tac-Toe游戏可要简单得多，虽然手动构造游戏树也不是不可行，但那样的做法实在太逊了啦！我们要砍树！ 这里给大家介绍的方法是MiniMax算法。所谓MiniMax算法，就是从当前棋局出发生成一颗n层深的游戏树，从树根开始轮流给每层结点赋予Max和Min的称号，并且按照一定的估计函数给最底层的结点赋值。然后，从下向上依次给每个结点赋值，若一个结点是Max结点，则把它子结点中的最大值赋给它，若是Min结点，则把它子结点中的最小值赋给它。如此这般，便可以得知树根选择哪个子结点才能得到最大效益。 实际，估计函数是用来限制游戏树深度的。这里介绍的估计函数是自己可能赢棋的通道数减去对手可能赢棋的通道数。以图1举例，假设计算机执圆圈，则圆圈可能赢的通道数是4个，而大叉可能赢的通道数只有2个，所以棋局对应的估计值＝4-2＝2(见图1)。
下面我们手动模仿计算机执大叉在开局时进行MiniMax算法的演算过程，让大家有个直观的理解。其中，MiniMax算法的估计函数就是上文介绍的，游戏树的深度为三层(见图2)。
|
正在阅读：Java咖啡馆(13): 终结者Java咖啡馆(13): 终结者
2005-09-07 09:55
出处：
责任编辑：moningfeng
键盘也能翻页，试试“← →”键
