梅姬之環(Rings of the Magi)遊戲的電腦解法研究

作者／賴信全　(國立台灣師範大學資訊教育系)
　　　林順喜　(國立台灣師範大學資訊工程所)

摘要

在本文中，我們嘗試利用電腦的高速運算能力及龐大的記憶空間，配合資料結構 及適當的演算法來求出梅姬之環(Rings of the Magi)遊戲各種盤面的可行解。 一般人在玩此遊戲時並無一定的規則可循，大多以直覺、本能判斷及經驗來求解 ，大多數人類的專注力及推理力很難判斷下一步所有的狀況並記憶所有走過的盤 面，而且也無法週詳的考慮如何走對盤面的影響會有解或無解。而且此遊戲有許 多盤面的解法步數極大，且盤面狀態總數極為龐大，不能以暴力法或尋常方法搜 尋求解，因此我們構思如何解決此困難的問題。在此論文中，我們發展了一些有 用的技術，目標是能求出一些矩形無障礙盤面的解答，並實際撰寫程式測試，要 求在可忍受的時間內求得可行解。希望拋磚引玉，藉此論文引起大家對此問題進 一步研究的興趣。

關鍵詞
暴力法、遊戲樹、雜湊表　　　　《詳全文》

Hsin-Chuan Lai　(Department of Information and Computer Education, NTNU)
Shun-Shii Lin　(Graduate Institute of Computer Science and Information Engineering, NTNU)

Abstract

In this paper, we will use computers to design data structures as well as algorithms to derive the solutions for the game "Rings of the Magi". Since many initial configurations of this game need lots of steps to reach the final configurations, its game tree grows very rapidly. We could not search the entire game tree with the "brute force" approach. Previously, there are no computer solutions for this hard problem, but there are many manual trials that are found in many software documents. In this paper, we will explore some useful techniques for solving this game. The results show that we can get available solutions for most boards in a reasonable amount of time. We hope that this paper can introduce the interest of subsequent researchers.

Key Words

brute force approach game tree hash table