Morpion Solitaire 5D# 的分數上界探討

A study of the upper bound on the score of Morpion Solitaire 5D#

郭之琪(TZU-CHI KUO)

指導教授 ： 王弘倫 ； 楊東育

國立臺北商業大學/管理學院/資訊與決策科學研究所/碩士(2019年)

摘要

Morpion Solitaire 是一種單人玩家的紙筆遊戲，這個遊戲流行於法國與比利時。證明 Morpion Solitaire 的分數上界與突破得分記錄是計算與數學領域中有趣的挑戰，本論文主要探討的版本是 Morpion Solitaire 5D#，採用的策略改編自 Henryk Michalewski、Andrzej Nagorko 與 Jakub Pawlewicz 在 2016 年對於 Morpion Solitaire 5D 的研究，藉由線性約束的條件來描繪這個遊戲，我們使用數學規劃求解工具Gurobi Optimizer ，並且運用開源叢集運算框架 Apache Spark 加快求解速度。

關鍵字

Morpion Solitaire ； 分數上界 ； 分散式運算 ； 整數規劃

並列摘要

Morpion Solitaire is a pencil-and-paper game for a single player. This game is popular in France and Belgium. Providing lower and upper bounds on the maximum score for Morpion Solitaire is a computational and mathematical challenge. In this thesis, we investigate this problem for the version 5D#. The strategy we adopt is modified from [Henryk Michalewski, Andrzej Nagorko and Jakub Pawlewicz:An upper bound of 84 for Morpion Solitaire 5D, CCCG, 2016], in which the game is depicted by linear constraints. We solve the integer programs using Gurobi Optimizer and speed up the computation by the distributed framework Apache Spark.

並列關鍵字

Morpion Solitaire ； Upper bound ； Distributed computing ； Integer programming

參考文獻

[1] Apache Spark. http://spark.apache.org, 2014.

[2] Gurobi Optimization. www.gurobi.com, 2008.

[3] C. Boyer: Morpion Solitaire. http://www.morpionsolitaire.com, 2008.

[4] C. Boyer: Morpion Solitaire le record est enn battu! Science & Vie, August

2010, Mondadori France, pp. 144-147.