適用於電腦對局遊戲之志願型計算系統及其應用問題

Abstract

本整合型計畫主要目的是為電腦對局遊戲(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!