多线程技术在博奕程序中的应用
禹晓辉蒋晓冬
摘要：如何在传统的博奕程序中引入Java多线程机制，以提高博奕树搜索效率，并给出了1个具体的应用实例。
关键词：Java多线程机制博奕树
线程是操作系统的一种新概念，是比传统进程粒度更小的可并发执行的单位。C和C++采用单线程体系结构，而Java却提供了多线程支持。一方面，Java环境本身就是多线程的；另一方面，Java语言内置多线程控制，提供了1个类Thread，由它负责启动、运行和终止线程，并可检查线程状态。Java的线程还包括了用于对多线程实行并发控制的同步原语。利用Java的多线程编程接口，可方便地构筑支持多线程的应用，提高程序的并发度和执行效率。
笔者曾参与开发了基于IBM Visual Age for Java环境的黑白棋博奕程序。通过将Java多线程机制引入博奕树搜索，明显加大了搜索平均深度，取得了很好的效果。
1线程的概念及生命周期
所谓“线程”是“进程”中某个单一顺序的控制流。新兴的操作系统，如Macos、Windows NT等，均把线程视为其基本执行单位。线程也是Java中相当重要的组成部分，如任何1个Java Applet的Paint()和update()方法均由AWT绘图与事件处理线程所调用。图1表示了线程在它的生命周期中的任何时刻所能处的状态以及引起状态改变的方法。
图1线程生命周期
2博奕
博奕就是对策或斗智，它不仅存在于棋类游戏中，而且存在于政治、经济、军事和生物竞争之中。在人工智能领域，大多以下棋为例来研究博奕规律。博奕为人工智能提供了1个很好的试验场所，人工智能中的许多概念和方法都是从棋类程序中提炼而得，博奕的许多研究成果现已用于军事指挥和经济决策系统之中。
博奕问题的状态空间——博奕树是1种特殊的与/或树，结点代表格局。所谓格局就是反映下棋态势的全部信息，如棋子位置、轮到谁走下一步等，可用状态变量表示。图2是1棵博奕树的局部。
图2博奕树局部
在2人零和非偶然性全信息博奕中(即对奕双方利益完全对立)，对奕双方都力图在状态空间中找到1条使自己得分最多的路径。设所有使甲方获胜的终局为可解端结点，得分为+b；所有使乙方获胜的终局为不可解端结点，得分为-b；分别按甲方与乙方走法，从端结点向根可一步步推算出各中间结点和根结点的得分，这就是对博奕树的极小极大化分析法。
然而，即使1个很小的博奕状态空间，也可能生成十分庞大的博奕树，它可能有的终局数也很大。企图对它们采用完整的极小极大化分析是不可能的，实际可行的办法是：在1个被分析的结点下面，只生成“似合理的”博奕树的一部分(给定深度限制，除去重复和希望不大的分枝)，并用得分函数f对树的各叶结点进行得分估值，然后用极大极小化分析计算树中各结点及根结点的得分估值，以便选择当前估计的最佳策略。这些计算所得的估值称为倒推估值(Back up Value)，其精度有赖于得分函数。
显然，如何在限定的时间内(本系统为5s)尽量提高搜索的深度是至关重要的。一般认为这有待硬件设施的提升，然而研究后发现，在传统的单线程博奕程序中，对手用于思考棋步的时间对己方而言是闲置的，而且也很难被利用。但在引入多线程机制后，采用“时间窃取”的技术，将对方的思考时间转变为我方的可利用时间，用于增加搜索深度，或在搜索深度不变条件下，提高得分函数的精度，从而显著改善了博奕程序的整体性能。
3应用实例
基于上述思想，我们在IBM Visual Age for Java环境下开发了黑白棋博奕程序。下面给出该程序的主体架构及涉及多线程应用的相关代码。为便于理解有必要先将黑白棋规则作一下简要介绍。
1.黑白棋规则
(1)棋盘为8×8方格，双方分别执黑白2色棋子。
(2)初始状态：棋盘中间4格放入黑、白各2棋子，如图3(a)。
(3)投子、吃子规则(以黑子为例)：
①当黑棋落子时，以此格为中心分别沿8个方向(上、下、左、右、左上、右上、左下、右下)来寻找原有的黑白子，若在某个方向上找到的第一个黑子与刚投下的黑子间无空格，则这2个黑子间的所有白子变为黑子，如图3(b)、图3(c)。
图3黑白棋规则
②黑子若找不到使白棋变为黑色的走法，则必须放弃一步，由对方走棋；若找得到，则不能放弃该步。
③胜负判定，当双方均放弃一步或棋盘上放满棋子时，清点棋盘上的两色棋子，多者获胜。
2.程序设计要求
(1)由计算机和玩家各执一色棋子，在棋盘中放棋。玩家可选择先手或后手。
(2)程序走每一步棋的计算时间限制为5s(Pentium 75,32MB RAM)，超时则由程序强制落子。
3.程序设计
(1)本软件是1个Applet，程序中定义实现了4个类：
Reversi：是整个Applet的骨架，负责用户界面的管理；
RevBoard：负责与棋局相关的各程序成分，如搜索器、棋局存储等程序的调度；
RevSearch：搜索器；
RevPlate：定义了棋局的内部存储结构及1组维护方法。
(2)本软件运行过程中，将有2个线程th-search,th-sleep并行执行，如图4所示(假定玩家先手)。
图4th-search 和 th-sleep 的运行状态
当Applet开始运行时，启动th-search线程，开始搜索；当玩家落子后，即启动th-sleep线程，并立刻执行sleep(5000)，进行睡眠状态。th-search执行搜索。5s后，th-sleep醒来，要求th-search提供搜索结果，并由相关程序据此落子，而th-sleep则转为suspend状态，此时玩家在思考，而th-search的搜索也在进行。当对方落子后，又重新启动th-sleep线程，如此周而复始，直到程序结束。可以看出th-sleep实际上起到了1个计时器的作用。
(3)程序代码
public class Reversi extends Applet Revboard board;
{
//界构造部分程序略
}
public class RevBoard extends Panel
{
RevPlate plate;//棋局
RevSearch searcher;//搜索器
public RevBoard();
plate=new RevPlate();
Plate,Init();//创建棋局并初始化
searcher=new RevSearch();
search.Search(plate)//启动搜索线程
Thread th-sleep;
public boolean mouseDown(Event evt,int x,int y)
{
//玩家落子时所做处理
if(plate.valid(x,y)//如果落子位置有效
//落子记录，重画棋盘
//Searcher针对落子情况作相应调整
if(th-sleep==null)//若th-sleep未创建
{
th-sleep=new Thread(this);
th-sleep.start();
}
else
th-sleep resume();
}
Public void run()//th-sleep线程的主要执行部分
{
while(true)
{
try{
Thread sleep(5000);
}catch(Exception e);
getAnswer();//取搜索结果
th-sleep suspend();
}
}
}
Class RevSearch implements Runnalbe
{
RevBoard board;
Thread th-search;//搜索线程
void search(RevPlate plate)
{
if(th-search==null)//若th-search尚未创建
{
th-search=new Thread(this);
th-search.start();
}
}
Public Void run()//th-search 的实际执行部分
{
}
}
class RevPlate
{//略}
4结束语
由于引入了多线程技术，本软件取得了很好的效果。在IBM Pentium 75、32MB内存机器上，利用α—β剪枝方法构造博奕树，结果5s内平均搜索深度达4层，访问状态结点达7000个，与没采用多线程技术的程序相比，效率提高了1.5～2倍。实践证明，Java多线程机制具有很高的实用价值。事实上，由于多线程的核心思想即并行，因此，在基于多处理机的系统上，多线程机制的威力必将得到更大程度的发挥。此外，Java多线程技术的应用也不仅仅局限于上述的博奕领域，如何将Java多线程技术广泛应用到分布式系统中，是需要深入探讨的问题。
作者单位：南京大学计算机科学与信息系(210093)
