著者
野瀬 彰大 深川 大路
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2011-GI-25, no.4, pp.1-8, 2011-02-26

本研究では,トレーディングカードゲームにおけるカードのシャッフルを扱う.まず,シミュレーションプログラムを用いてシャッフル手法について分析し,理想的なシャッフル手法の提案を目的とする.また,シャッフル手法の分析を行うために,シャッフルの結果を視覚的に表示する方法を提案する.分析の結果,各シャッフル手法の特徴が分かった.また,制限時間の長短に応じて適切なシャッフル手法が変わる可能性が示唆された.複数のシャッフル手法の組合せも行い,同じ組合せであっても実行順序が結果に大きな影響を与えることを実験的に示した.
著者
野瀬 彰大 深川 大路
出版者
情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:21862583)
巻号頁・発行日
vol.2011, no.4, pp.1-8, 2011-02-26

本研究では,トレーディングカードゲームにおけるカードのシャッフルを扱う.まず,シミュレーションプログラムを用いてシャッフル手法について分析し,理想的なシャッフル手法の提案を目的とする.また,シャッフル手法の分析を行うために,シャッフルの結果を視覚的に表示する方法を提案する.分析の結果,各シャッフル手法の特徴が分かった.また,制限時間の長短に応じて適切なシャッフル手法が変わる可能性が示唆された.複数のシャッフル手法の組合せも行い,同じ組合せであっても実行順序が結果に大きな影響を与えることを実験的に示した.In this paper, we consider shuffles in trading card games. First we analyze shuffles by computer simulations. The purpose of this study is to develop an ideal shuffle methods. Furthermore, we propose a visualization method for results of the simulation programs. The analyses suggest that what matters includes tyoe of shuffles, the time limit, and ordering of the methods.
著者
田中 哲朗
出版者
情報処理学会
雑誌
研究報告ゲーム情報学(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.
著者
田中 哲朗
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2009-GI-22, no.3, pp.1-8, 2009-06-19

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

人工知能の研究の題材としてゲームをプレイするプログラムが用いられる.日本では将棋と囲碁が題材としてよく取り上げられてきた.本論文は,コンピュータ将棋の初期の歴史についての調査結果の報告である.調査の結果,将棋プログラムのはじめては 1967 年の詰将棋プログラムであることがわかった.
著者
竹内 聖悟
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2015-GI-33, no.14, pp.1-4, 2015-02-26

強さの指標となるレーティングについて,対戦結果からの計算以外にも棋譜とプログラムの読み筋から計算する手法が研究されてきた.これらの手法ではプログラムに探索させて計算するため,計算コストがかかることが問題であった.本稿では,コンピュータ将棋対局場 Floodgate で指された棋譜を利用して悪手の計算を行う.Floodgate の棋譜には対局したプログラムによって評価値と最善手がコメントとして付記されており,これを利用することで計算コストを削減する.山下により提案された悪手率や好手率を Floodgate の棋譜向けに変更して実験を行ったがレーティングとの相関はあまりなかった.さらに,評価値に関する条件の緩和や悪手率の計算方法の変更を行ったところ,レーティングとの間に相関のある結果が得られた.
著者
鳥海不二夫 稲葉通将 大澤博隆 片上大輔 篠田孝祐 松原仁
出版者
一般社団法人情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:09196072)
巻号頁・発行日
vol.2014, no.5, pp.1-1, 2014-06-28

不完全情報コミュニケーションゲームである「人狼」を題材にした研究プロジェクトの概要を紹介し,ゲーム情報学という観点からこのプロジェクトの将来について展望していく.
著者
小場隆行 中所武司
出版者
情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:21862583)
巻号頁・発行日
vol.2011, no.8, pp.1-6, 2011-02-26

数独とは,ナンバープレイスとも呼ばれるペンシルパズルの一種である.長年,この数独に対して数学・情報科学等の様々な分野から研究がなされ,近年では高性能な自動解法プログラムや問題の自動生成プログラムなどが作られるようになっている.本研究では,その中でも数独の研究分野の一つである問題の難易度判定の手法に関して述べるものである.既存の数独の難易度判定アプリケーションは,問題の難易度判定の基準を予め定義している難易度埋め込み型であるのに対し,本研究ではユーザに問題の難易度判定の基準の定義を委ねる難易度定義型のアプリケーションを提案し,前述した難易度埋め込み型アプリケーションとの比較検証を行う.比較検討は,一般の書店で販売されているパズル誌二誌を使用し,難易度埋め込み型と難易度定義型における難易度判定の精度を比較した結果,難易度定義型を採用したことによって,判定結果のばらつきを減らすことができた.Recently, Sudoku solvers and Sudoku generators have been studied in the fields of mathematics and information science. In this paper, a method of difficulty level ranking by using application programs is described. Most of conventional applications for difficulty level ranking have given the fixed definition of the difficulty level criteria. This paper proposes a new method in which the difficulty level criteria are defined by users. An application supporting this method is developed and used for feasibility studies with two articles on difficulty level ranking in the popular journals. As a result, it is confirmed that the new method reduces dispersion of difficulty level ranking by using application programs.
著者
佐藤 諒 西村 夏夫 保木 邦仁
出版者
一般社団法人情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:09196072)
巻号頁・発行日
vol.2014, no.11, pp.1-6, 2014-03-10

本研究では,シャンテン数が下がるような牌を有効牌とし,数手先の有効牌を数え上げることによって牌効率を向上させた麻雀 AI の性能を評価することを目的とした.簡単のために副露や降りをしない面前全ツッパに麻雀AIの戦略を制限した.性能評価は,インターネット雀荘 「東風荘」 で人間のプレイヤーと対局させ,安定レートや他の統計情報を利用して行った.In this work, we analyze the performance of Mahjong AI programs that count the number of effective legal moves. Here, an effective legal move decreases Shanten numbers (the number of tiles away from tempai). For the sake of simplicity, we limit the strategy of AI programs to Menzen-Zentsupa strategy (no open melds by calling and no defense by discarding safe tiles). The performance is measured in the internet Mahjong server, Tonpu-So, with human players and it is analyzed in terms of rating and other statistic information.
著者
西野 順二
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2015-GI-33, no.18, pp.1-5, 2015-02-26

多人数不完全情報ゲームの人狼においてその自然な勝率を算出した.人狼は,代表的な会話にもとづくゲームである.このため,推論機能を持つ人工知能エージェントによる,会話と信頼創出のテストベッドとして研究されている.村人の人数に対して人狼側が有利であり,ゲームが拮抗する人数は全体の平方根に従うことが明らかになっている.本研究はこれに対し,人狼がより自然な戦略を取った場合に人狼側の有利さがさらに高いことを示した.勝率を算出し示すことで,人工エージェントの能力が有意に高いことを測る具体的な基準値を示した.
著者
鎌田 真人
出版者
一般社団法人情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:09196072)
巻号頁・発行日
vol.2009, no.27, pp.25-32, 2009-03-02

9路盤囲碁は,囲碁の入門用に使われているだけでなく,プロ棋士同士の対局やコンピュータ囲碁大会でも行われている。今回,1968年~2009年1月に行われたプロ棋士対プロ棋士の9路盤囲碁の棋譜846局の序盤の変化を分析した。19路盤に比べると棋譜の数が非常に少なく,また持ち時間も少ないが,プロ棋士の長年の研究の成果が窺える。当初は,初手天元が多かったが,コミが5目半から6目半に変わった頃から,初手3四,4四,4五が増えてきた。ほとんど打たれなくなった手や,結論が出ているのに打たれている手も見られる。また,初手から同じ手順の棋譜が多く見られ,定石化されてきたと思われる手順もある。Go on the 9x9 board is played not only by beginner Go players, but also in computerized Go championships and in games between professional players. I examined the 846 game records by professional players on the 9x9 board held over the period of 1968-Janaury 2009 to analyze changes in the opening moves of the game. Compared with Go on the 19x19 board, there are far fewer game records, and the players are allotted less "thinking time"; however, the records do give us an idea of the achievements of professional Go players in their study of the game over many years. Previously, the game was started by tengen. However, due to the shift from 5.5 to 6.5 Komi, 3-4, 4-4, and 4-5 first moves have become more common. Some moves are rarely used anymore, and other moves are used even when it is clear to the players what will happen next. Game records also show that players are using the same patterns, starting with the opening move, indicating a solidification of certain patterns.
著者
三塩 武徳 小谷 善行
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2014-GI-31, no.4, pp.1-6, 2014-03-10

ゲームの不完全情報の推定を行うアルゴリズム Using Past Playout(UPP) を提案する.UPP はモンテカルロ法において過去のシミュレーション結果のうち現在局面に至るものを取り出し,仮定した情報の間の勝率を比較する.相手側の勝率が高い部分は実際の局面と等しい可能性が高い.これを使って不完全情報の推定を行う.アレックス・ランドルフ (Alex Randolph) [1] によって発表された二人零和確定不完全情報ゲームである 「ガイスター」 において UPP を用いたプログラムと既存手法の猪突戦法,および通常のモンテカルロ法とで対局を行った.結果,猪突戦法に対しては思考時間 0.25 秒で 94%の勝率,モンテカルロ法との対局ではお互いの思考時間 1 秒で 55%の勝率を挙げた.これらの結果より,ガイスターにおける UPP の有効性を示した.
著者
小谷 善行
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2009-GI-22, no.8, pp.1-8, 2009-06-19

古来からある計算パズルの一つである虫食い算について,解記述の候補における制約を用いて虫食い算パズルを非探索的に解く方法を示した.それに最小分岐を行う探索アルゴリズムを付加することにより,普通の問題がみな解ける効率的な虫食い算解法アルゴリズムを作った.さらにそれを用いて虫食い算を作成するシステムを設計し,巨大な虫食い算を作った
著者
小松 智希 成澤 和志 篠原 歩
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2012, no.8, pp.1-8, 2012-07-06

探索空間が非常に広く,評価関数が作りにくいゲームにおいて行動決定を行う手法にモンテカルロ法があり,囲碁や大貧民などのゲームに対して有効な手法であることがわかってきた.しかし,麻雀のように探索空間全体に対して得点が得られる組み合わせが少ないゲームでは,モンテカルロ法は報酬を得ることができるプレイアウトの回数が少ないため,十分な効果を発揮することができない.本論文では,麻雀におけるモンテカルロ法の非効率性を実験的に検証する.また,プレイアウトにおいて効率的に報酬を得ることができる手法を提案し,モンテカルロ法と比較することで実験的に有効性を示す.Monte Carlo methods have been successfully applied for playing games, and have outperformed previous algorithm in such games as Go and Daihinmin. However, as we will experimentally show, it is not very effective for some games like Mahjong, where random simulation can rarely get rewards. Without positive rewards, players have little reason to choose better actions. In this paper, we propose a new algorithm to overcome this difficulty. It virtually simulates many play-outs in each trial simultaneously, so that many of play-outs can get positive rewards, even for this kind of games. We show some preliminary experiments that convinced us that the approach is promising.
著者
澤 宣成 伊藤 毅志
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2011-GI-26, no.3, pp.1-8, 2011-06-24

将棋における棋風を形成する要素に関する統計的分析
著者
清 愼一
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2013-GI-29, no.9, pp.1-8, 2013-02-25

日本におけるコンピュータ囲碁の初期の歴史について調査したので,ここに報告する.囲碁プログラムのはじめては1968年の「碁とコンピュータの会」で実演された詰碁プログラムであることがわかった.
著者
田中 哲朗
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2012-GI-27, no.12, pp.1-6, 2012-02-24

完全に解析を終わったゲームで完全プレイをおこなうためのデータベースは,完全ハッシュ関数とウェーブレット木を用いて,小さな記憶容量で実現できる.本研究では局面のノードを一段展開することで,更に記憶容量を減らす方法を提案する.これにより,「どうぶつしょうぎ」 の完全プレイのデータベースを 54.8MB の記憶容量で実現できた.これは,単純な実装と比較して 1/15 の容量となっている.
著者
西谷 崇志 原 慎平 井上 真郷
出版者
一般社団法人情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:09196072)
巻号頁・発行日
vol.2009, no.27, pp.101-108, 2009-03-02

本研究ではダーツ01(301)ゲームを対象に研究を行った。ダーツゲームは状態遷移確率がプレイヤーのスキルに依存する不確定ゲームであるため、未だその戦略的側面についてはあまり詳しく研究されていない。本研究ではプレイヤーが狙った点からダーツが二次元正規分布に従って当たるとするモデルで解析を行った。また、01ゲームの状態遷移には様々な経路が存在する点に着目し、動的計画法を用いることでプレイヤーのスキルに応じて平均的に最も少ないラウンド数で終了条件を満たす戦略を得ることに成功した。また、対戦相手が前述の戦略をとるものと仮定した上での、勝率を最大化する戦略も求め、結果を得た。本手法はより一般的な501ゲームにも容易に適用可能である。We investigated the 301 darts game. The strategic aspects of this game have not been fully studied yet due to the complexity of its state transition equations depending on players' skills. In this research, we adopted a simple model of two-dimensional Gaussian distribution for the gap between targeted point and actual hit point. Then, we analyzed this game by using the dynamic programming techniques because it has numerous transition pathways. As the results, we successfully obtained the optimal strategy which minimizes the expected number of rounds needed to reach the goal. Besides, we also successfully obtained the optimal strategy which maximizes the probability of the winning assuming the opponent player adopting the above strategy. Our analysis method can be easily applied for more popular 501 darts game.
著者
坂元 香菜美 篠田 正人
出版者
情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:09196072)
巻号頁・発行日
vol.2010, no.7, pp.1-8, 2010-06-18

神経衰弱とよばれるカードゲームに,ある特別なカードを取ったほうが勝ちというルールを導入する.2 人のプレーヤーがこのゲームをするときの勝率を最大化する戦略について考察し,両者が最善を尽くしたときこのゲームが後攻有利であることを述べる.We consider a modified version of The Memory Game, where we define that the winner of the game is the player possessing the pair of special cards. We study the optimal strategies which maximize the winning probability in the case of 2-player game, and we show that the player to flip second has an advantage over the opponent.
著者
五十嵐 治一 森岡 祐一 山本 一将
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2013-GI-30, no.6, pp.1-8, 2013-06-21

本論文では強化学習の一手法である方策勾配法をコンピュータ将棋に適用する方法を考察した.方策勾配法は,報酬や方策にマルコフ性の制限なく自由に設計することができるという大きなメリットがある.本論文では,最初に全 leaf 局面の局面評価値をその局面への遷移確率値で重み付けた期待値を用いた指し手評価方式を提案する.これをベースに,探索木の各ノードにおける指し手の選択法として Boltzmann 分布に基づくソフトマックス戦略を採用した場合の局面評価関数に含まれるパラメータの学習則を導出した.しかし,探索や学習時の計算量が膨大となるため,3 つの近似計算法を考案した.次に,探索時にシミュレーション方策を用いてモンテカルロ探索を行う場合や,探索の深さを制御する場合のために,局面評価関数とシミュレーション方策の両者を同時に学習する学習則を方策勾配法により導出した.さらに,この方策勾配の計算法を利用すると,局面ごとに正解手が既知の場合の教師付学習も可能であることを示し,実際に学習則を導出した.