标题: 适用于电脑对局游戏之志愿型计算系统及其应用问题---适用于电脑对局游戏之志愿型计算系统及其应用问题
A Volunteer Computing System for Computer Games and Its Applications
作者: 吴毅成
WU I-CHEN
国立交通大学资讯工程学系(所)
关键字: 电脑对局游戏;志愿型计算;MapReduce计算模式;丛集;高效能计算格网;桌机格网;黑白棋;组合对局游戏;对秤数游戏;微数字游戏;三角杀棋;冷却骨牌游戏;围棋;象棋;六子棋;alpha-beta搜寻;证明数目搜寻;蒙地卡罗树状搜寻;Computer Games;Volunteer Computing;MapReduce Programming Model;Clusters;High-Performance Computing (HPC) Grids;Desktop Grids;Othello;Combinatorial Games;Nimber Games;Infinitesimal Games;Triangle Nim;Chilled Domineering;Go (Weichi);Chinese Chess;Connect6;Alpha-Beta Search;Proof-Number Search;Monte-Carlo Tree Search.
公开日期: 2011
摘要: 本整合型计画主要目的是为电脑对局游戏(Computer Games)应用问题,提出并发展一套新的志愿型计算系统(Volunteer Computing System;简称为VCS),及利用此志愿型计算系统,解决许多过去无法解决的电脑对局游戏应用问题,如利用VCS来解出Othello(黑白棋)、组合对局游戏问题;建构六子棋、围棋、象棋的开局系统;设计强大的围棋程式(达到高段棋士程度)。
志愿型计算(Volunteer Computing),主要是利用现有许多多余的电脑计算资源(Computing Resources)来共同完成需要大量计算的应用问题。然而,我们的研究显示过去的志愿型计算系统,如Berkeley发展的BOINC等,无法适用于电脑对局游戏应用问题。主要的问题是∶电脑对局游戏应用问题通常需要(a)设定高度动态工作优先权(Job Priority)、(b)要求低延迟、(c)处理MapReduce计算模式、(d)大量的资料储存空间与传输、(e)与现有的高速计算系统整合。
本整合型计画分为两个大部份∶(1)此志愿型计算系统(VCS)及(2)运用此系统来解决及计算电脑对局游戏应用问题。在VCS部份,有两个子计画如下。
 子计画V1∶设计此系统的桌机格网部份。本子计画的目的是利用过去成功建构六子棋开局库所发展的Desktop Grid系统经验,设计一般化VCS之桌机格网部份。本子计画主要是解决上述五项问题,如最后一项问题所述,本子计画将与子计画V2整合;并提供子计画A1~A5,解决或计算电脑对局游戏应用问题。
 子计画V2∶设计此系统的丛集与HPC格网。本子计画的目的是设计一般化VCS之丛集与HPC格网部份。一直以来,常见的志愿型计算系统,并未纳入如丛集与HPC格网等适合用来进行沟通频繁之高速平行计算的架构。但实际上确实有许多电脑对局游戏应用问题需要进行该类平行计算,因此本计画将为丛集与HPC格网设计一管理系统,使其能利用其剩余计算资源或是拨出特定比例之计算能量来参与志愿型计算。本子计画将与子计画V1整合;并提供子计画A1~A5,解决或计算电脑对局游戏应用问题。尤其地,本计画将提供子计画A3及A4所整合之围棋、象棋程式比赛时,稳定之计算资源。
在电脑对局游戏应用问题部份,将运用子计画V1及V2所设计的VCS,来解决许多过去无法解决(或无法解的好)的电脑对局游戏应用问题,有五个子计画如下∶
 子计画A1∶运用VCS解黑白棋问题。在2007年,由加拿大的学者Schaeffer,花了很长的时间解出西洋跳棋(Checkers)。此结果具有相当大的震撼,并刊登于极高学术权威的科学期刊(Science)。而接下来大家预期的下一项重要挑战,就是解出黑白棋(Othello)。黑白棋目前可以弱解(weakly solved;只有解游戏起始之盘面)6*6的盘面,但尚未有人强解(strongly solved;解出所有盘面)6*6的盘面。本子计画将解出6*6黑白棋的强解与弱解7*7黑白棋及解部分8*8黑白棋盘面,这也有助于未来弱解8*8黑白棋。
 子计画A2∶运用VCS解组合对局游戏问题。组合对局游戏有两个重要的子类,Nimbers及Sumbers,其中三角杀棋、冷却骨牌分别是代表性问题。本子计画将强解8路三角杀棋之对局值、弱解9路三角杀棋、9路以上之三角杀棋对局程式、强解6路冷却骨牌之对局值、弱解7路冷却骨牌、7路以上之冷却骨牌对局程式。
 子计画A3∶运用VCS设计蒙地卡罗围棋程式。最近,电脑围棋的棋力有极为快速的成长。主要原因是发展出蒙地卡罗树状搜寻(Monte-Carlo Tree Search)演算法,成功地提升棋力。很明显地,现在是围棋程式发展的一个重要时间点,台湾不应缺席。
 子计画A4∶运用VCS建构围棋开局库问题。可藉由联合多台电脑之计算资源,以建
构围棋开局库,其中九路围棋开局库可接近完美。预计可于三年内帮助围棋程式(九路)击败世界棋王。
 子计画A5∶运用VCS建构象棋开局库问题。本子计画的目的是在不需要专家知识介入下或专家仅提供少数知识下,自动产生象棋开局库。我们预期将有助于大幅提升程式棋力到九段(原约七段强),并能与特级大师相抗衡。
本整合型计画预计三年完成。
 第一年研究工作之主要目标是∶建置环境、研究规划技术及界面规格;子计画V1及V2完成基本之VCS,但不含MapReduce计算模式;子计画A1~A5运用此VCS,设计无须MapReduce计算模式之应用问题。
 第二年研究工作之主要目标是∶子计画V1及V2完成基本之VCS,含MapReduce计算模式;子计画A1~A5运用此VCS,设计须MapReduce计算模式之应用问题。
 第三年研究工作之主要目标是∶子计画A1~A5大量运用此VCS;在VCS部份,子计画V1及V2设计更有效地资源管理及分配、高稳定性之执行(利用容错机制)、跨桌机格网间之连结。
在志愿型计算系统方面,由于现有的志愿型计算系统,无法适用于电脑对局游戏之应用,本计画之志愿型计算系统,将比这些系统更为一般化,可适用更广的应用。这将是国际上,第一个可适用于电脑对局游戏应用且提供MapReduce计算模式之志愿型计算系统。此外,此计画的成功,未来预计在台湾即能整合出万核以上之电脑资源,这将有机会成为台湾研究领域的一个强大计算资源。
在电脑对局游戏应用问题部份,由于可利用志愿型计算系统,来协助解决需要大量计算之电脑对局游戏应用问题,我们预计将会获致许多令人振奋的新成果。例如解黑白棋、组合游戏对局;设计强的围棋、象棋程式。尤其是,值此围棋正在大幅接近围棋高段棋士之际,象棋程式亦然,极有机会在最近的将来创造类似深蓝击败世界西洋棋棋王的历史,台湾不应该在此方面缺席,而本整合型计画将有助于这个研究的成功,提升台湾在此领域的研究成就。
The main goal of this integrated project is to propose and design a new volunteer computing system (Abbr. VCS), and to apply this system to the applications of computer games to solve many difficult problems that were not solved or not well solved in the past. For example, use the VCS to solve Othello game problems and combinatorial game problems etc, to construct openings of the games such as Connect6, Go (WeiChi), Chinese Chess, and to design strong game programs such as Go programs.
Volunteer computing is to exploit spare resources such as computing powers and memory storages of desktops or some personal computers for the applications requiring huge amount of computation. However, from our research, the systems for volunteer computing in the past such as BOINC are not well suited for computer game applications. The key reason is that for these applications we need to support: (a) highly dynamic job priorities, (b) low latency among jobs, (c) MapReduce computing model, (d) huge amount of data storage and transmissions, and (e) integration with high performance systems such as clusters and grids.
This integrated project is divided into two parts: (1) the design of the volunteer computing system (VCS) and (2) the application to computer games using VCS. In the first part, there are two subprojects as follows.
 Subproject V1: The design of desktop grids in the VCS. The goal of this subproject is to design the desktop grids in the VCS, based on our successful experiences on building openings of Connect6. This subproject will support the above five features as above. For the last feature, this subproject will collaborate with Subproject V2. In addition, this subproject will support the applications designed by Subprojects A1~A5.
 Subproject V2: The design of clusters and high-performance computing (HPC) grids in the VCS. In many common VCSs, clusters and HPC grids are not included. However, these may still act as an important donators, especially in the case of the need of stable resource requests, such as the computer game tournaments for Go or Chinese Chess.
In the second part, there are five subprojects as follows.
 Subproject A1: Solving Othello problems by using the VCS. In 2007, Schaeffer solved Checkers. This highly impact result was published in the prestigious Science Journal. And, Othello is the next game researchers would like to solve. Currently, the 6x6 Othello game can be weakly solved (only the initial position solved), but not strongly solved (all positions solved) yet. Using the VCS, this subproject plans to strong solve 6x6 Othello, weakly solve 7x7 Othello game, and solve some 8x8 Othello game positions.
 Subproject A2: Solving combinatorial game problems by using the VCS. Combinatorial games include two important subclasses, Nimber and Sumber, where Triangle Nim and Chilled Domineering are two typical games respectively. Using the VCS, this subproject plans to strong solve 8x8 Triangle Nim, weakly solve 9x9 Triangle Nim, design a more than 9x9 Triangle Nim program, strong solve 6x6 Chilled Domineering, weakly solve 7x7 Chilled Domineering, design a more than 7x7 Chilled Domineering program,
 Subproject A3: Designing Monte-Carlo Go programs by using the VCS. Using the VCS, this subproject plans to implement a strong Go programs based on Monte-Carlo UCT algorithms.
 Subproject A4: Building Go openings by using the VCS. Using the VCS, this subproject can build strong Go openings, especially nearly perfect for 9x9 Go openings. We expect to help (9x9) Go programs to beat World Champion within three years.
 Subproject A5: Building Chinese Chess openings by using the VCS. This subproject automatically builds Chinese Chess openings with no knowledge or limited knowledge from experts. We expect to raise the levels of our Chinese Chess programs from 7 dan (七段) to 9 dan (九段), close to the Chinese Chess top players.
This integrated project is a 3-year project.
 In the first year, the research work items include: Build the environment, study the related technology and define the specification. Subprojects V1 and V2 design the basic VCS, but does not support the MapReduce model. Using the VCS, Subprojects A1~A5 design the computer game applications that does not require MapReduce.
 In the second year, the research work items include: Subprojects V1 and V2 design the basic VCS that support the MapReduce model. Using the VCS, Subprojects A1~A5 design the computer game applications that require MapReduce.
 In the third year, the research work items include: Subprojects A1~A5 start using the VCS heavily to solve computer game problems. Subprojects V1 and V2 design resource management to manage resources fairly and efficiently, implement fault tolerance to make the VCS more stable, and design virtualizations to make the usage more flexible.
In the VCS, when compared with other VCSs, our VCS is more general, especially for computer game applications. This VCS could be the first volunteer computing systems that support MapReudce programming and fit the need of computer game applications. In addition, the success of this project would be able to integrate over tens of thousands of CPU-cores. This brings great and huge computer resources to the research society in Taiwan.
In the area of computer game applications, since we can leverage the computing resources from the VCS, we expect to solve many interesting and exciting new results, such as solving Othello and combinatorial games, designing strong Go and Chinese Chess programs. Especially when the strength of Go program is approaching the level of professional Go players, there are high chances to make a history in Computer Go. Taiwan should not be absent!
官方说明文件#: NSC99-2221-E009-102-MY3
URI: http://hdl.handle.net/11536/99269
https://www.grb.gov.tw/search/planDetail?id=2212477&docId=353754
显示于类别:Research Plans