利用志願型運算解決電腦遊戲問題

Abstract

電腦遊戲是人工智慧(Artificial Intelligence)中一項非常重要的研究領域，其中有些問題需要非常大量的運算才能解出，而志願型運算(Volunteer Computing)非常適合用來解決這些問題。由於電腦遊戲的特性，大部份問題需要即時地產生及取消工作，這在傳統的志願型運算上會非常沒有效率，因為傳統的志運型運算為非連線模式，無法即時更改工作。本論文提出工作層級運算模式(Job-level Computing Model)，並以此模式為基礎發展一套新的且具有一般化之工作層級志願型運算系統，此系統使用的是連線模式，以避免傳統志願型運算解決電腦遊戲效率不佳的問題。本論文利用傳統型志運型運算與工作層級志願型運算分別解決兩個電腦遊戲問題：數獨最小提示數問題(Minimum Sudoku Problem)與六子棋開局問題(Connect6 Opening Problem)。 在解決數獨最小提示數問題中，本論文亦改善了2006年的數獨Checker程式，加快了約128倍效率，使用此改善程式可將原本需要約30萬年單核時間的數獨最小提示數問題減少成約2417年可解。而在解決六子棋開局問題中，成功地將證明數搜尋演算法應用於工作層級志運型運算系統中，並提出了延遲兄弟節點產生法及假設證明數相同之方法來展開搜尋樹節點，成功地解出許多六子棋盤面的勝敗，其中包含多個開局，例如米老鼠開局，此開局在過去是很受歡迎的開局之一。根據實驗數據顯示，在16核的環境下其速率可提升8.58倍。

Computer game is an important field of research in artificial intelligence, while some computer game problems take huge amount of computation time to solve, which is suitable to use volunteer computing to solve. However, due to the property of computer games, most computer game problems generate or abort jobs dynamically when solving, which makes computer game problems cannot be solved efficiently on traditional volunteer computing, which uses connectionless model and cannot support the function. This thesis proposes job-level computation model, and based on this model to propose a new generic job-level volunteer computing system, which is a connection model, to solve compute game problems efficiently. This thesis uses traditional volunteer computing and job-level volunteer computing to solve the minimum Sudoku problem and Connect6 game openings, respectively. For solving the minimum Sudoku problem, this thesis speedups the Sudoku program Checker written by McGuire in 2006 by a factor of about 128, and reduce the computation time for solving the minimum Sudoku problem from about 300 thousand year on a one-core machine to about 2417 years. For solving Connect6 openings, this thesis successfully incorporates proof number search into the job-level volunteering computing system, and proposes postponed sibling generation and virtual-equivalence methods to generate nodes in search trees. Based on this system, many new Connect6 game positions are solved efficiently, including several Connect6 openings, especially the Mickey-Mouse Opening, which was one of the popular openings. The experiments showed 8.58 speedups in a system with 16 cores.