工作層級演算法用於解Hex

Job-Level Search for Solving Hex

梁熙(Liang, Xi)

指導教授 ： 吳毅成

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2015年)

https://doi.org/10.6842/NCTU.2015.00654

摘要

Pawlewicz和Hayward於2013年成功證明出全部9x9 Hex開局盤面，以及一個特定的10x10開局盤面，其用來證明的程式只能使用單台機器的運算資源，因此無法更進一步並行化。在此研究中我們嘗試將該程式套用到工作層級UCT演算法上從而使其可以利用更多運算資源提高其並行度。在將其套用到工作層級系統之後，我們通過使用共享記憶體和資料庫技術使不同工作間的資訊可以被共享以提高搜尋效率。實驗結果顯示工作層級演算法可以提高並行度，而通過我們提出的這些技術，在單台機器上套用到工作層級框架上的程式可以比原本的程式證明同樣4個開局盤面中的3個花費更少的時間。當使用6台機器時，證明同樣的4個盤面，使用工作層級框架的程式效率是原本只能使用單台機器程式的1.6， 1.9， 1.8和2.6倍。

關鍵字

工作層級 ； 搜尋演算法 ； 人工智慧

並列摘要

Recently, Pawlewicz and Hayward successfully solved many Hex openings based on the Scalable Parallel Depth-First Proof-Number Search algorithm (SPDFPN), which was performed in a single machine with multiple threads. However, further parallelization is limited by the number of cores a single machine can possess. This paper investigates adapting this SPDFPN solver to a distributed computing environment, using the previously proposed job-level upper-confidence tree algo-rithm (JL-UCT) in order to further increase parallelism. To improve on the adapted JL-UCT solver system, we make a new attempt to support transposition information sharing among jobs in JL implementations. A mix of shared-memory and database techniques was used to achieve this improvement. Our experiments show that the adapted JL-UCT solver scales for larger problems. Additionally, using a single machine with 24 cores, the adapted method is able to solve Hex openings with less time than the previous SPDFPN solver in five of six test cases. Overall, for the six test cases, the adapted JL-UCT solver, using 6 nodes each with 24 cores, obtained speedups of 1.6, 1.9, 1.8, 2.6, 2.2 and 2.0 over those for the SPDFPN solver using one node with 24 cores.

並列關鍵字

Job ； Search ； Hex ； AI

參考文獻

1. Hayward, R., et al., Solving 7× 7 Hex: Virtual connections and game-state reduction, in Advances in Computer Games. 2004, Springer. p. 261-278.

4. Wu, I.-C., et al. A Volunteer-computing-based grid environment for Connect6 applications. in Computational Science and Engineering, 2009. CSE'09. International Conference on. 2009. IEEE.

5. Saffidine, A., N. Jouandeau, and T. Cazenave, Solving breakthrough with race patterns and job-level proof number search, in Advances in Computer Games. 2012, Springer. p. 196-207.

6. Wu, I.-C., et al., Job-level proof number search. Computational Intelligence and AI in Games, IEEE Transactions on, 2013. 5(1): p. 44-56.

7. Wu, I.-C., et al., Job-level proof-number search for connect6, in Computers and Games. 2011, Springer. p. 11-22.