著者

田中 哲朗

出版者

情報処理学会

雑誌

研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.3, pp.1-8, 2009-06-19

参考文献数

4

被引用文献数

1

---

「どうぶつしょうぎ」¹⁾ は 2008 年に女流棋士の北尾まどか初段によって考案されたボードゲームである.将棋に類似しているが,将棋と比べて非常に簡潔なルールになっている.「どうぶつしょうぎ」 は二人完全情報零和ゲームであり,すべての局面の理論値 (勝ち,負け,引き分けのいずれか) が決定可能である.本論文では,後退解析 (Retrograde analysis) をベースにしたプログラムを用いて初期局面から到達可能なすべての局面の理論値を求め,初期局面が後手必勝であり勝ちに要する手数が 78 手であるという結果を得た.また,「敵陣へのひよこ打ち」 が有効である局面が存在することなど,いくつかの興味深い性質を確認することができた."Doubutsu Shogi" is a board game invented in 2008 by a professional shogi player Madoka Kitao. Although "Doubutsu shogi" is similar with shogi, its rule is far simpler than that of shogi. Since "Doubutsu shogi" is a two-player zero-sum game with perfect information, it is possible to determine theoretical values (Win, Lose, Draw) of all positions. In this article, we computed theoretical values of all positions reachable from the initial position, by means of making a program based on retrograde analysis. As a consequence, we confirmed that the theoretical value of the initial position is win by white( the second player ) with 78 moves. We also obtained some interesting results such that there are positions in which "dropping a hiyoko piece on the promote zone" is the only winning move.

著者

田中 哲朗

出版者

一般社団法人 日本数学会

雑誌

数学 (ISSN:0039470X)

巻号頁・発行日

vol.65, no.1, pp.93-102, 2013-01-25 (Released:2016-11-25)

参考文献数

9

著者

水野 秀一 田中 哲朗

出版者

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

雑誌

情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.28, pp.53-59, 2008-03-12

参考文献数

5

被引用文献数

1

---

I.Q はよく知られたパズルゲームであるが,その計算量の議論はこれまで行われてこなかった.本論文では,I.Q のクリアにおいて重要な概念であるターン数に着目し,決められたターンにすべてのキューブを捕獲することができるかどうかというターン数判定問題が NP 完全であることを証明した.Up to now, the computational complexity of I.Q has not been discussed though it is a puzzle game known well. In this paper, wo proofed NP-completeness of the turn number decision problem which is whether to catch all cube in given turns.

著者

山本 一成 竹内 聖悟 金子 知適 田中 哲朗

雑誌

ゲームプログラミングワークショップ2010論文集

巻号頁・発行日

vol.2010, no.12, pp.42-48, 2010-11-12

---

本稿では,将棋においてMagicBitboardを適用する手法を提案する.Bitboardはチェスなどの二人ゲームのゲーム木探索で盤面を表現するのに適した手法であり,チェスや将棋の強いプログラムで広く使われている.MagicBitboardは従来のBitboardの手法に比べ,よりシンプルなデータ構造を管理するだけで利きを算出することが可能となる近年開発された手法である.MagicBitboardはチェスの盤面が一つの64ビット整数で表現できることに依存した手法であり,盤面のマス目の数が81マスの将棋で,MagicBitboardを使う方法は知られていなかった.しかし我々は初めて,複数の整数で表現された盤面においてMagicBitboardを使って利きを算出する手法を発明し,Bonanzaを使った実験で我々の手法の効果を示した.

著者

田中 哲朗

雑誌

研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2009-GI-22, no.3, pp.1-8, 2009-06-19

---

「どうぶつしょうぎ」¹⁾ は 2008 年に女流棋士の北尾まどか初段によって考案されたボードゲームである.将棋に類似しているが,将棋と比べて非常に簡潔なルールになっている.「どうぶつしょうぎ」 は二人完全情報零和ゲームであり,すべての局面の理論値 (勝ち,負け,引き分けのいずれか) が決定可能である.本論文では,後退解析 (Retrograde analysis) をベースにしたプログラムを用いて初期局面から到達可能なすべての局面の理論値を求め,初期局面が後手必勝であり勝ちに要する手数が 78 手であるという結果を得た.また,「敵陣へのひよこ打ち」 が有効である局面が存在することなど,いくつかの興味深い性質を確認することができた.

著者

金子 知適 田中 哲朗

雑誌

情報処理

巻号頁・発行日

vol.54, no.9, pp.914-922, 2013-08-15

著者

金子 知適 田中 哲朗 山口 和紀 川合 慧

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.48, no.11, pp.3438-3445, 2007-11-15

参考文献数

17

被引用文献数

2

---

将棋の評価関数として,駒(所有者,種類,位置を含む)の2 項関係を評価するモデルと,棋譜を使った自動的な調整方法を提案する.将棋の評価関数では駒の損得を基本としたうえで,駒の働きや玉の危険度など様々な評価項目が用いられている.しかしそのような駒の損得以外の評価項目は設計が難しく,また自動的な値の調整も困難であった.本稿では,駒の関係という単純な評価項目を提案し,既存の評価項目の多くが駒の関係により表現可能であることを示す.さらに,棋譜で指された指手と指されなかった手の差分に注目した判別分析を行うことで,重みを自動的に調整することを提案する.実際に評価関数を作成したところ,形を評価する実験で良い結果が得られた.さらに,対戦でも提案した評価関数を使ったプログラムが有為に勝ち越し,提案手法の有効性が示された.New evaluation function in shogi, based on pairwise piece relations, and a method for automated tuning of their weights are presented. Existing evaluation functions treat a lot of specific aspects, as well as material balance, of the game. Most of such aspects can, we show, be handled by the proposed method. Then, we automatically adjust the weights of pairwise piece relations, by means of discriminant analysis of many game records. Our experiments showed that reasonably accurate evaluation functions for preferable configuration of pieces can successfully be constructed. Moreover, significant improvement on strength was confirmed in self-play.

著者

畢 暁恒 田中 哲朗

雑誌

ゲームプログラミングワークショップ2015論文集

巻号頁・発行日

vol.2015, pp.25-30, 2015-10-30

---

これまでの人狼ゲームの戦略に関する研究の多くは村人と人狼しかいない場合を扱ってきた.占い師のいる先行研究もあったが,占い師が吊られた時に人狼でないことが分かるという異なるルールが適用されていた.本研究では,本来のルールの元で占い師と狩人を導入した上で,双方に制約を加え,最適の戦略を計算することを試みた.双方の最適な戦略は純粋戦略ではなく,混合戦略となるため,ϵ-ナッシュ均衡を計算するのにCFR+アルゴリズムを用いる.この結果,ゲームに関していくつかの考察を得た.

著者

伊藤 隆 田中 哲朗 胡振江 武市 正人

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.10, pp.3012-3020, 2002-10-15

---

``しりとり''を完全情報ゲームとして数学的に定義した``しりとりゲーム''を考えると,グラフ上のゲームとしてモデル化することができる.これは完全情報ゲームであるため理論上は解けることになるが,問題のサイズが大きくなるにつれ全探索は困難となる.本論文では,しりとりゲームに関する解析を行い,ゲームを効率的に探索する手法を提案する.この手法は数理的解析,探索の効率化の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.

著者

滝瀬 竜司 田中 哲朗

雑誌

ゲームプログラミングワークショップ2011論文集

巻号頁・発行日

vol.2011, no.6, pp.25-31, 2011-10-28

---

現在の将棋プログラムの多くは入玉が絡む局面の扱いを不得意としているが,トッププロに勝つためには,入玉が絡む局面を正しく扱い「自玉が入玉できそうな時は入玉を目指す」,「敵玉の入玉を正しく阻止する」将棋プログラムの作成が不可欠だと考えられる.本稿ではオープンソースの将棋プログラムBonanzaの評価関数と定跡を変更することにより入玉志向の将棋プログラムを作成する試みをおこなう.その結果,元のBonanzaの評価関数に「入玉ステップ数」という特徴を加えて学習した評価関数を用いることにより,勝率を落とさずに入玉率を大幅に上げることができた

著者

田中 哲朗

出版者

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

雑誌

情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2006, no.23, pp.65-72, 2006-03-07

被引用文献数

1

---

「シンペイ(SIMPEI)」は高橋晋平氏が考案し株式会社バンダイが2005年7月に発売したボードゲームである.縦横斜めに駒を並べることを目標とする点は,n目並べの多くのバリエーションと共通しているが,盤面を「上の世界」と「下の世界」の2つに分けている点や,挟んだ駒を自由に移動できる点に特徴があり,高いゲーム性を有している.この点が評価されて,2006年度のGPCC(Games and PuzzlesCompetitions on Computers)の課題問題に選ばれた.「シンペイ」は二人完全情報零和ゲームなので,すべての局面の理論値(勝ち,負け,引き分けのいずれか)を決定することが可能である.本論文では,後退解析(Retrograde analysis)をベースにしたプログラムを用いてすべての局面の理論値を求めた.そして,「シンペイ」の公式ルールの初期配置が後手必勝であること,1手目を自由に置くことが許されれば先手必勝であることを確かめた.また,勝ちに要する最長手数が49手であること,「シンペイ」のゲームにツークツワンク(ZugZwang)が存在することや,単純なサイクルが存在し,その周期は1 3 4の3通りしかないことなど,いくつかの興味深い性質を求めることができた.SIMPEI is a board game, which was designed by Simpei TAKAHASHI. It was released in Jul. 2005 by BANDAI. Although it is similar to other n-stones-in-a-row games, it has two unique features. The first one is the two separated worlds in a board, the upper world and the lower world. And the second one is to move in free the opponents piece which is clipped by one player's pieces. This game is selected one of the problems of this year in the GPCC(Games and Puzzles Competitions on Computers). Because "SIMPEI" belongs to perfect information two player zero-sum games, in a theoretical sense, all states in the game can be decided as winning, losing or in draw. We practically analyzed all game states with a program based on retrograde analysis. In this paper, we show the result of the analysis. We found that the second player can always win in the "SIMPEI" official rule. And we present some other interesting features of the game.

著者

田中 哲朗

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.48, no.11, pp.3470-3476, 2007-11-15

---

「シンペイ(SIMPEI)」は高橋晋平氏が考案し株式会社バンダイが2005 年7 月に発売したボードゲームである.縦横斜めに駒を並べることを目標とする点は,n 目並べの多くのバリエーションと共通しているが,盤面を「上の世界」と「下の世界」の二つに分けている点や,挟んだ駒を自由に移動できる点に特徴があり,高いゲーム性を有している.この点が評価されて,2006 年のGPCC(Games and Puzzles Competitions on Computers)の課題問題に選ばれた.「シンペイ」は二人完全情報零和ゲームなので,すべての局面の理論値(勝ち,負け,引き分けのいずれか)を決定することが可能である.本論文では,後退解析(Retrograde analysis)をベースにしたプログラムを用いてすべての局面の理論値を求めた.そして,「シンペイ」の公式ルールの初期配置が後手必勝であること,1手目を自由に置くことが許されれば先手必勝であることを確かめた.また,勝ちに要する最長手数が49 手であること,「シンペイ」のゲームにツークツワンク(ZugZwang)が存在することや,単純なサイクルが存在し,その周期は1,3,4 の3 通りしかないことなど,いくつかの興味深い性質を求めることができた.

著者

田中 哲朗

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.48, no.11, pp.3470-3476, 2007-11-15

参考文献数

4

被引用文献数

1

---

「シンペイ(SIMPEI)」は高橋晋平氏が考案し株式会社バンダイが2005 年7 月に発売したボードゲームである.縦横斜めに駒を並べることを目標とする点は,n 目並べの多くのバリエーションと共通しているが,盤面を「上の世界」と「下の世界」の二つに分けている点や,挟んだ駒を自由に移動できる点に特徴があり,高いゲーム性を有している.この点が評価されて,2006 年のGPCC(Games and Puzzles Competitions on Computers)の課題問題に選ばれた.「シンペイ」は二人完全情報零和ゲームなので,すべての局面の理論値(勝ち,負け,引き分けのいずれか)を決定することが可能である.本論文では,後退解析(Retrograde analysis)をベースにしたプログラムを用いてすべての局面の理論値を求めた.そして,「シンペイ」の公式ルールの初期配置が後手必勝であること,1手目を自由に置くことが許されれば先手必勝であることを確かめた.また,勝ちに要する最長手数が49 手であること,「シンペイ」のゲームにツークツワンク(ZugZwang)が存在することや,単純なサイクルが存在し,その周期は1,3,4 の3 通りしかないことなど,いくつかの興味深い性質を求めることができた."SIMPEI" is a board game, which was designed by Simpei TAKAHASHI. It was released in July 2005 by BANDAI. Although it is similar to other n-stones-in-a-row games, it has two unique features. The first one is the two separated worlds in a board, the upper world and the lower world. And the second one is to move in free the opponents piece which is clipped by one player's pieces. This game is selected one of the problems of this year in the GPCC (Games and Puzzles Competitions on Computers). Because "SIMPEI" belongs to perfect information two player zero-sum games, in a theoretical sense, all states in the game can be decided as winning, losing or in draw. We practically analyzed all game states with a program based on retrograde analysis. In this paper, we show the result of the analysis. We found that the second player can always win in the "SIMPEI" official rule. And we present some other interesting features of the game.

著者

田中 哲朗

雑誌

研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2012-GI-27, no.12, pp.1-6, 2012-02-24

---

完全に解析を終わったゲームで完全プレイをおこなうためのデータベースは,完全ハッシュ関数とウェーブレット木を用いて,小さな記憶容量で実現できる.本研究では局面のノードを一段展開することで,更に記憶容量を減らす方法を提案する.これにより,「どうぶつしょうぎ」 の完全プレイのデータベースを 54.8MB の記憶容量で実現できた.これは,単純な実装と比較して 1/15 の容量となっている.

著者

水野 秀一 田中 哲朗

雑誌

情報処理学会研究報告ゲーム情報学(GI)

巻号頁・発行日

vol.2008, no.28(2008-GI-019), pp.53-59, 2008-03-12

---

I.Q はよく知られたパズルゲームであるが,その計算量の議論はこれまで行われてこなかった.本論文では,I.Q のクリアにおいて重要な概念であるターン数に着目し,決められたターンにすべてのキューブを捕獲することができるかどうかというターン数判定問題が NP 完全であることを証明した.

著者

大渡 勝己 田中 哲朗

雑誌

ゲームプログラミングワークショップ2016論文集

巻号頁・発行日

vol.2016, pp.180-187, 2016-10-28

---

本研究では連続空間のMDPに対するモンテカルロ木探索を基にした行動決定手法を提案する.提案手法を,カーリングの戦略を議論するために作成された「デジタルカーリング」システムにおける対戦プログラムに適用した.実験の結果,単純なシミュレーション方策を用いた場合だけでなく,カーリングの知識を用いた複雑なシミュレーション方策を用いた場合にも提案手法が有効に働くことを確認した.

著者

副田 俊介 田中 哲朗

出版者

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

雑誌

情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.79, pp.31-38, 2003-08-04

---

最中限は竹内郁雄によって提案された3人プレイヤのカードゲームである.本研究は最中限をプレイする強いプログラムを作ることを目的とする.最中限は提案されたばかりのゲームであるため,人間のプレイにおいても,有効な戦略は確立されていない.そこで,人間の知識を使わずに計算機を用いて最中限を分析することにより,有効な戦略を求めることを試みる.この目的のために,最中限をプレイするプログラムを自動対戦させる実験を行い,点数に注目して分析を行った.プログラムは途中まではランダムプレイ,最終ラウンドでは検索によって手を生成するものを用いた.このプログラムは最終ラウンドの検索では相手プレイヤがランダムプレイヤ,つまりどの手も等しい確率で選ぶプレイヤであると仮定して全幅検索を行っている.この実験の結果,最終ラウンドに入る時点で点数が最も高かったプレイヤのゲーム終了時の得点の期待値は -0.56,2番目のプレイヤは0.91,3番目のプレイヤは-0.54となり,最終ラウンドに入る時点で最も中間の位置にいるプレイヤが最も有利であるという経験則と,この条件の元では一致することが確かめられた.Saichugen is a three player card game introduced by Ikuo Takeuchi. As it is a fairly new game, no good playing strategies are well known yet for Saichugen. We have analyzed Saichugen endgames by using Saichugen playing programs. We have used programs that play randomly up to the middle of the game, and plays by searching in the last round of the game. The programs assumes that the opponents players play randomly when searching. We had this programs play each other for 1000 games and analyzed the results. For these playes. We were able to show that the player with the most middle points when entering the endgame tends to keep his place - win the game.

著者

田中 哲朗

雑誌

ゲームプログラミングワークショップ2021論文集

巻号頁・発行日

vol.2021, pp.138-143, 2021-11-06

---

R-Rivals はカナイセイジ氏がデザインした 2 人用カードゲームで 2014 年に発売された.R-Rivalsはサイコロのようなランダムな要素を含まない 2 人零和ゲームだが,同時手番ゲームなのでじゃんけんと同様にナッシュ均衡が存在するのは双方のプレイヤが混合戦略を用いたときになる.本研究では,同値な状態は同じであるとみなして,R-rivals のすべての状態を数えた.そして,得られた約 54 万の状態すべてのゲーム値を計算した.その結果,初期状態で出せる 8 枚のカードのうち,道化,姫,将軍を除く 5 枚のカードをある確率で出すのが最適な戦略であること,ポイントが 0-3 から勝てる状態があることなどの性質をみつけることができた.

著者

田中 哲朗

雑誌

ゲームプログラミングワークショップ2020論文集

巻号頁・発行日

no.2020, pp.194-201, 2020-11-06

著者

伊藤 隆 田中 哲朗 胡振江 武市 正人

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.10, pp.3012-3020, 2002-10-15

---

``しりとり''を完全情報ゲームとして数学的に定義した``しりとりゲーム''を考えると,グラフ上のゲームとしてモデル化することができる.これは完全情報ゲームであるため理論上は解けることになるが,問題のサイズが大きくなるにつれ全探索は困難となる.本論文では,しりとりゲームに関する解析を行い,ゲームを効率的に探索する手法を提案する.この手法は数理的解析,探索の効率化の2つの部分から成っており,数理的解析としてグラフのより簡単な形への変形を行っている.加えて,しりとりゲームにおける先手の勝率に関して実験,考察を行う.