しりとりゲームの数理的解析 An Analysis of Word Chain Games

この論文にアクセスする

この論文をさがす

著者

    • 伊藤 隆 ITO TAKASHI
    • 東京大学大学院情報理工学系研究科数理情報学専攻 Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo
    • 胡振江 [他] HU ZHENJIANG
    • 東京大学大学院情報理工学系研究科数理情報学専攻 Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo
    • 武市 正人 TAKEICHI MASATO
    • 東京大学大学院情報理工学系研究科数理情報学専攻 Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo

抄録

``しりとり''を完全情報ゲームとして数学的に定義した``しりとりゲーム''を考えると,グラフ上のゲームとしてモデル化することができる.これは完全情報ゲームであるため理論上は解けることになるが,問題のサイズが大きくなるにつれ全探索は困難となる.本論文では,しりとりゲームに関する解析を行い,ゲームを効率的に探索する手法を提案する.この手法は数理的解析,探索の効率化の2つの部分から成っており,数理的解析としてグラフのより簡単な形への変形を行っている.加えて,しりとりゲームにおける先手の勝率に関して実験,考察を行う.The word-chain game (SHIRITORI in Japanese) in which two players are assumed to know all the words can be modeled as a game on graph.When given a set of words with a word to start,it is theoretically possible to decide whether the first player can win the game or not because it is a game with perfect information,but it is practically difficult to find the solution because of the huge searching space.In this paper,we propose a mathematical approach to finding a solution to the word-chain game.We show how to simplify the game by means of mathematical analysis,and give a more efficient searching algorithm.In addition, we examine the possibility for the first player to win the game.Our experimental results show that our approach is quite promising.

The word-chain game (SHIRITORI in Japanese) in which two players are assumed to know all the words can be modeled as a game on graph. When given a set of words with a word to start, it is theoretically possible to decide whether the first player can win the game or not because it is a game with perfect information, but it is practically difficult to find the solution because of the huge searching space. In this paper, we propose a mathematical approach to finding a solution to the word-chain game. We show how to simplify the game by means of mathematical analysis, and give a more efficient searching algorithm. In addition, we examine the possibility for the first player to win the game. Our experimental results show that our approach is quite promising.

収録刊行物

  • 情報処理学会論文誌

    情報処理学会論文誌 43(10), 3012-3020, 2002-10-15

    一般社団法人情報処理学会

参考文献:  4件中 1-4件 を表示

各種コード

  • NII論文ID(NAID)
    110002771154
  • NII書誌ID(NCID)
    AN00116647
  • 本文言語コード
    JPN
  • 資料種別
    Journal Article
  • ISSN
    1882-7764
  • NDL 記事登録ID
    6327883
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-741
  • データ提供元
    CJP書誌  NDL  NII-ELS  IPSJ 
ページトップへ