多线程技术在博奕程序中的应用

多线程技术在博奕程序中的应用

禹晓辉　蒋晓冬

　　摘　要：如何在传统的博奕程序中引入Java多线程机制，以提高博奕树的搜索效率，并给出一个具体的应用实例。　　关键词：Java　多线程机制　博奕树

　　线程是操作系统的一个新概念，是一个可并发执行的单位，粒度小于传统进程。C和C++Java采用单线程系统结构，提供多线程支持。一方面，Java环境本身是多线程的；另一方面，Java语言内置多线程控制，提供一种负责启动、运行和终止线程的Thread，并可以检查线程状态。Java的线程还包括同步原语，用于并发控制多线程。采用Java多线程编程接口，方便构建支持多线程的应用程序，提高程序的并发性和执行效率。　　作者参与了基于IBM的开发 Visual Age for 黑白棋博弈程序，Java环境。将Java多线程机制引入博奕树搜索，显著增加了平均搜索深度，取得了良好的效果。

1　线程的概念和生命周期

　　所谓“线程”，是“过程”中单一顺序的控制流。Macoss等新兴操作系统、Windows NT等，均将线程视为其基本执行单位。线程也是Java的重要组成部分，如任何Java AppletPaint()和update()方法均由AWT绘图和事件处理线程调用。图1显示了线程在其生命周期中的任何时刻都能处于状态以及导致状态变化的方法。

图1　线程生命周期

2　博奕

　　博奕是对策或斗智，它不仅存在于棋类游戏中，也存在于政治、经济、军事和生物竞争中。在人工智能领域，大多数人以下棋为例来研究博奕规律。博弈为人工智能提供了一个很好的实验场所。人工智能中的许多概念和方法都是从国际象棋程序中提炼出来的。博弈的许多研究成果现在用于军事指挥和经济决策系统。　　博奕问题的状态空间——博奕树是一种特殊的和/或树，结点代表格局。所谓格局，就是所有反映下棋情况的信息，比如棋子的位置，轮到谁走下一步，可以用状态变量来表示。图2是一棵博奕树的局部。

图2　博奕树局部

　　在两人零和非偶然的全信息博奕中(即双方利益完全对立)，双方都试图在状态空间中找到一条得分最多的路径。将甲方获胜的所有终局设置为可解端结点，分为+b；乙方获胜的所有终点都是不可解的终点，分为-b；根据甲乙双方的行走方式，每个中间结点和根结点的得分可以从端结点逐步计算到根部，这是博奕树的最小最大分析方法。　　然而，即使是一个非常小的博奕状态空间，也可能会产生一棵非常大的博奕树，其中一些可能会有大量的终局。试图对它们进行完整的最小分析是不可能的，实际可行的方法是：在一个分析点下，只生成“合理”的部分（给定深度限制，去除重复和希望的分支），用得分函数f评分树叶结点，然后用最小分析计算树结点和根点评分估值，以选择当前估计的最佳策略。这些计算所得的估值称为倒推估值(Back up Value)，其精度取决于得分函数。　　显然，在有限的时间内(本系统为5s)尽可能提高搜索深度是非常重要的。一般认为这需要硬件设施的改进。然而，研究发现，在传统的单线程博奕程序中，对手思考棋步的时间对自己来说是闲置的，很难使用。然而，在引入多线程机制后，利用“时间窃取”技术将对方的思维时间转化为我们的可用时间，以增加搜索深度，或在搜索深度不变的情况下提高得分函数的准确性，从而显著提高博奕程序的整体性能。

3　应用实例

　　基于上述思想，我们在IBM Visual Age for 黑白棋博弈程序是在Java环境中开发的。以下是涉及多线程应用的程序的主体架构和相关代码。有必要简要介绍一下黑白棋的规则，以便于理解。　　1.黑白棋规则　　(1)棋盘为8×八方格，双方分别持有黑白两色棋子。　　(2)初始状态:将黑白棋子放入棋盘中间4格，如图3所示(a)。　　(3)投子、吃子规则(以黑子为例)：　　①当黑棋落子时，以此格为中心，沿着8个方向(上、下、左、右、左、右、左、右)寻找原来的黑白子。如果在某个方向上找到的第一个黑子和刚投下的黑子之间没有空间，那么这两个黑子之间的所有白子都会变成黑子，如图3所示(b)、图3(c)。

图3　黑白棋规则

　　②如果黑子找不到让白棋变黑的方法，就必须放弃一步，让对方下棋；如果找到了，就不能放弃这一步。　　③胜负判断，当双方放弃一步或棋盘上摆满棋子时，清点棋盘上的两色棋子，多者获胜。　　2.程序设计要求　　(1)计算机和玩家各执一色棋子，在棋盘上放棋。玩家可以选择先手或后手。　　(2)程序走每一步棋的计算时间限制为5s(Pentium 75,32MB RAM)，如果超时，程序将被迫落子。　　3.程序设计　　(1)本软件为Applet，在程序中定义了四个类别:　　Reversi：负责用户界面管理的整个Applet骨架；　　RevBoard：负责与棋局相关的各种程序成分，调度搜索器、棋局存储等程序；　　RevSearch：搜索器；　　RevPlate：定义了棋局的内部存储结构和一组维护方法。　　(2)在这个软件的运行过程中，会有两个线程th-search,th-如图4所示，sleep并行执行(假设玩家先行)。

图4　th-search 和 th-sleep 的运行状态

　　当Applet开始运行时，启动th-search线程并开始搜索；当玩家落后时，启动th-slep线程，并立即执行sleep（5000）进行睡眠。th-search执行搜索。5s后，th-当sleep醒来时，它要求th-search提供搜索结果，并由相关程序执行，而th-sleep则转换为suspend状态，此时玩家正在思考，th-search的搜索也在进行中。另一方落子后，再次启动th-slep线程，如此周而复始，直到程序结束。可见th-sleep实际上起到了一个计时器的作用。　　(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-slep线程的主要执行部分　　{　　　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)