六子棋程式平行化之研究

Abstract

本實驗室所研發的六子棋程式-交大六號(NCTU6)以及其延伸版本，曾獲得三屆電腦奧林匹亞賽局競賽六子棋項目的金牌，以及在多次人機競賽中擊敗過許多棋士。這篇論文的目的是平行化交大六號以增強程式的強度。首先設計一個平行程式架構透過平行迫著空間搜尋的方式來平行NCTU6，稱為基本平行版。更進一步採用dovetailing的概念來強化NCTU6的迫著空間搜尋以及alpha-beta search，為dovetailing平行版。Dovetailing對於現有複雜遊戲程式的平行化是相當有用也相較容易的。 實驗結果顯示，基本平行版程式以12核的資源對上本來的交大六號可達到約79.6%的勝率，平均時間約為本來的110%左右。Dovetailing平行版以12核心對上交大六號有77.5%的勝率，對上基本平行程式也達到61.9%的勝率，在時間上只需本來單核程式的80%，並可搜尋到更多的必勝必敗結果。本篇論文也是第一個將dovetailing的概念套用在非找尋解的搜尋演算法(alpha-beta search)上。

NCTU6 is a Connect6 AI program developed in our lab. NCTU6 and its variations won gold medals in ICGA tournaments three times and also defeated many expert players in Man-Machine Connect6 championships. The objective of this thesis is to improve the program’s strength by parallelization. First, this thesis designs the architecture of parallel program for NCTU6. Based on this architecture, we modified NCTU6 into a baseline parallel program by parallelizing some threat-space searches (TSSs). Second, this thesis applies the technique of dovetailing to parallelize NCTU6 by dovetailing two search algorithms, TSSs and alpha-beta search. The technique of dovetailing is useful and relatively easy especially for parallelizing programs which are already very complicated. The result of the experiment shows that the baseline parallel program with 12 cores reaches about 79.6% win rate against NCTU6, and, the time taken by the baseline parallel program is about 110% of the time taken by the original program. Appling the technique of dovetailing, the dovetailing parallel program with 12 cores reaches 77.5% win rate against NCTU6, and 61.9% win rate against the baseline parallel program, and, the time taken by the dovetailing parallel program is about 80% of the time taken by the original program. Besides, the version with dovetailing finds more winning solutions. This thesis is also the first one that applies the technique of dovetailing to the non-proof search algorithms such as alpha-beta search.