愛因斯坦棋英文原名EinStein würfelt nicht!，在2004年由德國一位數學教授Ingo Althöfer所發明。這是一個包含擲骰子的機率性遊戲，走步會由骰子點數而有很大的影響。也因此要如何從被動地受到骰子點數而影響走步，變為主動影響棋子的分佈來控制骰子的機率就是一大學問。

　　本研究主要是將此種遊戲中的兩種不同架構進行比較：其一為使用增強學習架構，利用自我對下產生棋譜之後對類神經網路進行訓練，以增加蒙地卡羅樹節點展開以及盤面分數評估的精準度；另一個則是使用傳統的期望最小最大算法(expectiminimax)並且搭配各種剪枝手段降低搜索時間，並且在節點最後以人類經驗法則賦值的方式給予盤面分數。在使用兩種不同實作的情況之下，以自動化平台的方式來進行對弈的實驗。同時，此研究也透過提升處理器頻率提升兩者單位時間內運算量，也減少了類神經網路產生棋譜所需要的時間。

　　此次使用的增強學習架構為使用開放原始碼的專案進行改良，使用直譯式的Python語言；而期望最小最大算法的實作則是從無到有自行開發的程式，使用的是Crystal語言，能夠編譯成原生的x86機器碼執行。如此兩相比較的實驗可以視為新舊技術的對抗，使用新工具來實作傳統演算法是不是還有奮力一搏的機會？期待未來設備升級之後能兩者都能有改進的機會。

EinStein würfelt nicht! was invented in 2004 by Ingo Althöfer, a German professor. In the game, a dice is used to decide which pieces can be moved. Therefore, the game strategy is all about probability. We should not be confined by the dice and we can focus on how the pieces' moves should be chosen.
　　This research will compare with two kinds of implementations of EinStein würfelt nicht!. One is reinforcement learning framework, which uses self-playing to generate training data for improving the neural networks. The other is expectiminimax implementation using heuristic and preforms alpha-beta pruning and further pruning in chance nodes. We introduce a platform that can automatically do game plays and record the results. We also improve the performance of our programs by overclocking the processor.
　　The reinforcement learning framework is based on an open-source project in Python. The expectiminimax implementation is developed in Crystal language and then codes are compiled to native machine codes for execution. By comparing the two implementations, we can know the pros and cons of each of them.

[1] 　陳昱廷，電腦暗棋程式Dancing的設計與實作，國立國立台灣師範大學資工所碩士論文，2013。
[2] 　曹少剛，深度學習用於愛因斯坦棋研發之初步探討，國立國立台灣師範大學資工所碩士論文，2017。
[3] 　謝昌龍、林順喜，電腦愛因斯坦棋自動對弈平台的設計與開發，台灣電腦對局學會論文集，2017。
[4] 　謝昌龍、林順喜，電腦愛因斯坦棋程式Meowdero的設計與實作，第二十一屆人工智慧與應用研討會，2016。
[5] 　Bruce W.Ballard, ”The *-minimax search procedure for trees containing chance nodes”, Artificial Intelligence Volume 21 Issue 3. Sep 1983, pp. 327-350.
[6] 　D.J. Edwards and T.P. Hart, ”The α-β Heauristic”, Artificial Intelligence Project--RLE and MIT Computation Center, Oct 1963.
[7] 　David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel & Demis Hassabis, “Mastering the game of Go with deep neural networks and tree search”,Nature volume 529, JAN 2016, pp. 484-503.
[8] 　David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel & Demis Hassabis, “Mastering the game of Go without human knowledge”, Nature volume 550, OCT 2017, pp. 354–359.　
[9] 　EinStein würfelt nicht!，https://3-hirn-verlag.de/MasterGame/regel.html。
[10] Emanuel Oster, ”AN MCTS AGENT FOR EINSTEIN ẄURFELT NICHT”, Master Thesis DKE 15-19, Maastricht University Department of Knowledge Engineering, The Netherlands, 2015.
[11] James R. Slagle, James R. Slagle, ”Experiments With Some Programs That Search Game Trees”,JACM,Volume 16 Issue 2, April 1969, pp.189-207.
[12] Samuel H. Fuller, John G. Gaschnig ; and Gillogly, ”Analysis of the alpha-beta pruning algorithm”,Computer Science Department, Carnegie-Mellon University, 1973.
[13] Shi-Jim Yen, Cheng-Wei Chou, Jr-Chang Chen, I-Chen Wu, Kuo-Yuan Kao, ” Design and Implementation of Chinese Dark Chess Programs”, IEEE Transactions on Computational Intelligence and AI in Games, June 2014, pp. 66-74.
[14] Surag Nair, Shantanu Thakoor, Megha Jhunjhunwala, ”Learning to Play Othello Without Human Knowledge”