臺灣國際科展

Generalized Quantum Tic-Tac-Toe

科展類別
臺灣國際科展作品
屆次
2012年
科別
電腦科學
得獎情形
二等獎
學校名稱
NUS High School
作者
Ananya Kumar
關鍵字
unique game ,GQT3

摘要或動機

Early physicists such as Newton thought that all objects have definite positions. For example, they thought that an apple is either inside a fruit bowl, or outside of it. The advent of quantum physics in the early 20th century proved this viewpoint wrong. There is an uncertainty in the position of any object; we can find a set of possible locations where the object might be. This concept was termed superposition. Quantum tic-tac-toe (QT3) elegantly extends the popular game of tic-tac-toe by adding this quantum physics concept of superposition. Each turn, 1 piece is simultaneously played into 2 distinct squares of a 3-by-3 grid. Eventually, however, every piece will occupy exactly one square, like in tic-tac-toe. Yet, despite this intriguing addition, not much research has been done on the game. Hence in this paper we explore the game in terms of extension, analysis and solution. Firstly, we note that the quantum extension proposed by Alan Goff in QT3 is incomplete. In reality, there can be more than 2 possible locations for any object. Unfortunately, the QT3 game rules do not allow for this extension. Thus we non-trivially generalize the game (GQT3) by proposing a new set of rules. We show that the original QT3 is a subset of GQT3 and prove that our generalized game can always be successfully played from start to finish in a finite number of moves. Then, we begin our analysis of GQT3. Firstly, we investigate the game tree complexity, state space complexity and computational complexity of the game; indicators of how complicated the game is. Notably, we find here that QT3 has a total of about 18 trillion possible games, which is substantially higher than tic-tac-toe’s 400 thousand. Then we examine the Nash Equilibrium of the game; the result if two ‘Gods’ play the game against each other. We find that in this scenario, the first player will win by 0.5 points. To make the game fairer, we suggest minor variations on the scoring, which make the Nash Equilibrium a draw. Note that standard methods to analyze all of these would take at least a year, but we bring down the time to about a minute using symmetry considerations and other optimizations. Finally, we extend our programs into an artificial intelligence that is a perfect solution to the game. We then supplement this with a utility function to make the run-time performance pragmatic for more time-consuming versions of GQT3. Ultimately, GQT3 is a challenging and unique game with myriads of exploration possibilities; we have only scratched the surface here.


「為配合國家發展委員會「推動ODF-CNS15251為政府為文件標準格式實施計畫」,以及 提供使用者有文書軟體選擇的權利,本館檔案下載部分文件將公布ODF開放文件格式, 免費開源軟體可至LibreOffice 下載安裝使用,或依貴慣用的軟體開啟文件。」

檔案名稱 檔案大小 格式
Generalized Quantum Tic-Tac-Toe 207 KB Adobe Reader(Pdf)檔案