適用於電腦對局遊戲之志願型計算系統及其應用問題---志願型計算系統中之桌機格網設計

Abstract

本整合型計畫主要目的是為電腦對局遊戲(Computer Games)應用問題，提出並發展一套新的志願型計算系統(Volunteer Computing System;簡稱為VCS)，及利用此志願型計算系統，解決許多過去無法解決的電腦對局遊戲應用問題，如利用VCS來解出Othello（黑白棋）、組合對局遊戲問題；建構六子棋、圍棋、象棋的開局系統；設計強大的圍棋程式（達到高段棋士程度）。 志願型計算(Volunteer Computing)，主要是利用現有許多多餘的電腦計算資源(Computing Resources)來共同完成需要大量計算的應用問題。然而，我們的研究顯示過去的志願型計算系統，如Berkeley發展的BOINC等，無法適用於電腦對局遊戲應用問題。主要的問題是︰電腦對局遊戲應用問題通常需要(a)設定高度動態工作優先權(Job Priority)、(b)要求低延遲、(c)處理MapReduce計算模式、(d)大量的資料儲存空間與傳輸、(e)與現有的高速計算系統整合。 本子計畫（代號子計畫V1）是設計此志願型計算系統(VCS)之桌機格網部份。本子計畫的目的是利用過去成功建構六子棋開局庫所發展的Desktop Grid系統經驗，設計一般化VCS之桌機格網部份。本子計畫主要是解決上述五項問題，如最後一項問題所述，本子計畫將與子計畫V2（負責叢集及HPC格網部份）整合；並提供子計畫A1~A5（解電腦對局遊戲應用問題之子計畫），解決或計算電腦對局遊戲應用問題。 本整合型計畫預計三年完成。  第一年研究工作之主要目標是︰建置環境、研究規劃技術及界面規格，並完成基本之桌機格網系統，但不含MapReduce計算模式；子計畫A1~A5已可運用此桌機格網系統，設計無須MapReduce計算模式之應用問題。  第二年研究工作之主要目標是︰完成基本之桌機格網系統，並含支援MapReduce計算模式；子計畫A1~A5已可運用此桌機格網系統，設計須MapReduce計算模式之應用問題。  第三年研究工作之主要目標是︰由於子計畫A1~A5開始大量運用VCS，將設計更有效地資源管理及分配、高穩定性之執行（利用容錯機制）、跨桌機格網間之連結。 由於現有的志願型計算系統，無法適用於電腦對局遊戲之應用，本計畫之桌機格網加上子計畫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 clusters and high performance computing (HPC) grids. This subproject V1 is to design 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 in the past. This subproject will support the above five features as described above. For the last feature, this subproject will collaborate with Subproject V2, responsible for clusters and HPC grids. In addition, this subproject will support the applications designed by Subprojects A1~A5, responsible for solving computer games problems. This subproject is a 3-year project.  In the first year, the research work items include: Build the environment, study the related technology, define the specification, design the basic desktop grid, but does not support the MapReduce model yet. Using the desktop grid, Subprojects A1~A5 can design the computer game applications that does not require MapReduce.  In the second year, the research work items include: Design the basic desktop grid that support the MapReduce model. Using the desktop grid, Subprojects A1~A5 can design the computer game applications that require MapReduce.  In the third year, the research work items include: Since Subprojects A1~A5 start using the VCS heavily to solve computer game problems, design resource management to manage resources fairly and efficiently and implement fault tolerance to make the VCS more stable. 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. And, many interesting and exciting new results for computer game applications will be expected to be solved using this VCS.