ボードゲームBAOのCCSによる記述と解析

情報処理学会

書誌事項

タイトル別名
  • Representation and Analysis of Board Game BAO Using CCS

この論文をさがす

説明

本論文では，ボードゲームBAO をプロセス代数CCS を使って記述し，盤面の状態変化に対する性質の形式的扱いについて述べる．BAO は2 人のプレーヤーが複数の穴に入った石を動かしながら取り合うボードゲームである．ルールは単純で探索空間も比較的狭い一方，1 手の間に盤面の状態が大局的に変化し，しかも1 つの穴の状態が何度も変化するため，人間が先読みを行うことは困難である．このゲームを実装して動きを解析した結果，特定の状態およびそのときに選択される穴によって，1 手の間の盤面の状態変化は停止せずしかも周期性を持つことが分かった．このゲームを穴をプロセス，石をプロトコルとする並行プロセスとしてとらえると，並行プロセスの周期性や停止性と関係が深く，非常に興味深い．本論文では，BAO の動きと性質をプロセス代数CCS を使って記述し，盤面の状態と選択する穴に対して一定の条件が満たされていれば盤面は周期的な状態変化を起こしその変化は停止しないことを示す．また，ある状態から動きを逆に解析することによって一連の動きの列をつくり，1 手による状態変化が停止するためにその列が満たすべき条件があることを示す．さらに，状態変化が停止するための必要十分条件となる性質についても議論する．

In this paper, we show a representation of a board game BAO in a process algebra CCS, and a formal treatment of a state transition of the board. BAO is a board game in which two players are taking seeds in turn by moving them from hole to hole. While the rule is simple and search space is rather small, it is hard for a human player to look ahead, since the state of the board changes globally, and the state of a hole may change several times during one turn. Implementing the game and analysing the behavior, we have found that the state transition may not terminate during one turn and constructs a cyclic behavior depending on a selected hole in a specific state. It is interesting to consider the relationship between the game and a concurrent process, by regaring a hole and a seed as a process and a protocol, respectively. In this paper, we represent the bahavior and characterstics of BAO in a process algebra CCS, and show that the state changes cyclically if the selected hole and the initial state satisfy a specific condition. We also make behavioral sequences by roling back from a state to explore the condition for the termination. Furthermore, we also discuss the sufficient condition for the termination.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ