著者

地曳隆将 松崎公紀

出版者

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

雑誌

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

巻号頁・発行日

vol.2014, no.15, pp.1-7, 2014-03-10

---

棋譜を教師データとした評価関数の学習は,特にコンピュータ将棋において有効とされている.本研究では,コンピュータ大貧民を対象として,棋譜を教師データとした提出手役評価関数の学習を行いその性能を評価した.提出手役評価関数には 3 層ニューラルネットワークを用いた.提出手役評価関数の性能を評価するため,棋譜で提出した手役との一致率を調査した.その結果,学習に使用する教師データを増やすことで一致率が上昇したが,教師データ数 15000 程度で一致率が頭打ちになることが確認された.教師データ数 15000 の棋譜評価関数では,未知の盤面に対する提出手役一致率が 69%であった.

著者

森田茂彦 松崎公紀

出版者

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

雑誌

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

巻号頁・発行日

vol.2014, no.14, pp.1-5, 2014-03-10

---

チェスや将棋などにおいて,プレイヤの強さを数値として表すレーティングシステムが広く用いられている.レーティングアルゴリズムとして良く知られるイロレーティングでは,プレイヤ間のレート差と勝敗によってレートの増減が計算される.特に,弱いプレイヤが強いプレイヤに勝つと,レートの増分が大きくなる.本研究では,大貧民を対象としたレーティングアルゴリズムを提案する.大貧民では,プレイヤの強さに加えて,初期手札の良さが勝敗に大きく影響する.そのため,初期手札の良し悪しに差がある場合,従来のレーティングアルゴリズムを用いるとレートの増減が過剰であったり不足することが起こりうる.この問題を解決するため,初期手札の不均等性を考慮に入れたレーティングアルゴリズムを提案し,そのアルゴリズムについて評価を行う.

著者

岡 和人 松崎 公紀

雑誌

第57回プログラミング・シンポジウム予稿集

巻号頁・発行日

vol.2016, pp.9-18, 2016-01-08

---

「2048」のプレイヤとして,TD 学習を用いて作成した盤面評価関数を用いるプレイヤが有効であることが示されている.盤面評価関数には,盤面から特徴点の情報を抽出して部分評価値を計算する,部分評価関数の組が用いられている.これまでの研究では,盤面評価関数の性能は,数通りしか検討されていない.十分な学習が行えると仮定すれば,部分評価関数の特徴点の個数を増やし,部分評価関数の個数を増やすことで,より高性能なプレイヤを作ることが出来ると予想されるが,記憶容量をより多く消費する.また,盤面評価関数は部分評価関数の組み合わせによって得られるため,全ての盤面評価関数を調べ上げることは計算時間や記憶容量の問題から困難である.よって,記憶容量と性能とのバランスに優れる盤面評価関数を効率よく調べ,得られた盤面評価関数を用いるプレイヤがより強くなるかを調査する必要がある.本稿では,考えられる部分評価関数を列挙し,特徴点数が6 の場合で部分評価関数の性能を調査した.この結果,特徴点集合が連結成分数1 の形をとる部分評価関数の性能が高いとが見込まれることを示した.得られた高性能な部分評価関数を用いて,盤面評価関数を作成した.作成した盤面評価関数を用いたプレイヤの得点は,500 万ゲームを学習することで平均203769 点となった.また,性能の高い部分評価関数から,盤面からバランス良く特徴点を抽出するような盤面評価関数を作成した.個の盤面評価関数を用いるプレイヤの得点は,500 万ゲームを学習することで平均224562 点となり,これまで報告されているTD 学習のみを用いるプレイヤの中で最も高い得点となった.性能の高い部分評価関数を用いて,盤面からバランス良く特徴点を抽出するような盤面評価関数を用いて,GPCC(Games and Puzzles Competitions on Computers; プログラミング・シンポジウムの分科会)で提案されている「対戦型2048」で,提案する盤面評価関数をTD 学習によって作成したプレイヤが,既存のプレイヤよりも強いことを示した.

著者

那須 律政 松崎 公紀

雑誌

第54回プログラミング・シンポジウム予稿集

巻号頁・発行日

vol.2013, pp.173-180, 2013-01-11

---

ペンシルパズルのうちでも,数独に対してさまざまな研究が行われている.そのうち,最少ヒント問題とは,唯一解を持つ盤面を構成できる最少のヒント数はいくつかという問題である.通常のサイズが9×9の数独については,2012年1月にMcGuireらによって,ヒント数16の盤面がない,すなわち,最少ヒントが17であることが示された.GPCCの2011年問題では,サイズが16×16の数独に対する最少ヒント問題がとりあげられ,そのなかで白川によってヒント数56の盤面が発見された.著者らもこの数独の少数ヒント問題に対して研究を行っている.数独の少数ヒント盤面を効率良く生成するには,広大な探索空間の中から適切に探索を行う必要がある.著者らは,ゲーム分野で近年活発に研究されているモンテカルロ木探索手法をこの問題に適用し,少数ヒント問題を効率良く生成することを目指している.本論文では,数独少数ヒント盤面生成にモンテカルロ木探索手法を適用するにあたり必要であった工夫と,得られた少数ヒント盤面について報告する.

著者

松崎 公紀 江本 健斗

雑誌

情報処理

巻号頁・発行日

vol.56, no.5, pp.482-488, 2015-04-15

---

BSP (Bulk Synchronous Parallel) モデルは,L.G.Valiant (2010年ACM Turing賞)によって1990年に提案されたモデルであり,抽象並列計算機モデルと並列計算モデルとを与えるものである.近年,Google Pregelなど,BSPの計算モデルに倣った大規模グラフ処理フレームワークが提案され,BSPモデルにも注目が寄せられている.本解説では,BSPの提案に至った歴史やBSPの計算モデルについて説明するとともに,BSPに基づく実際の並列プログラミングについて,コードを交えて紹介する.

著者

柳澤 佑介 松崎 公紀

雑誌

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

巻号頁・発行日

vol.2015-GI-33, no.9, pp.1-6, 2015-02-26

---

近年,コンピュータ大貧民においてモンテカルロ法プレイヤが広く用いられ,その改良についてさまざまな研究が行われている.大貧民のモンテカルロ法プレイヤでは,各プレイアウト (シミュレーション) のはじめに,相手手札を仮想的に生成・推定する処理を行う.本研究では,この相手手札の生成・推定を行う方法を4つ提案し,対戦実験を通してその効果を評価する.特に相手手札の推定は,既存のプレイヤから得た札譜に加えて,相手プレイヤの提出手役履歴をもとに行う.実験の結果,手札生成および手札推定の手法によりモンテカルロ法プレイヤが強化されることを確認した.しかし,本研究で提案した手札推定では負の効果を持つこともあるという問題点も見られた.

著者

松崎 公紀

雑誌

情報処理

巻号頁・発行日

vol.58, no.6, pp.488-495, 2017-05-15

---

報処理学会の会員の中には,論文をLaTeXで書いて人も多くいるだろう.論文そのものをLaTeXを用いて書いている場合でも,他のWYSIWIGなソフトウェアで作成した図を取り込んでいることが多い.論文で用いるような線画にラベルを組み合わせた図,とくにその図に規則性がある場合には,本稿で説明するプログラミングにより図を描く(生成する)ことが便利である.本稿では,MetaPost言語を用いて,プログラミングにより図を描く方法について解説する.簡単なMetaPostプログラムから始めて,繰り返しやマクロ,ラベルの使い方を説明する.さらに,実際の利用に役立つGnuplotの出力グラフの書き換えについてのヒントも述べる.

著者

松崎 公紀

雑誌

情報処理

巻号頁・発行日

vol.58, no.6, pp.466-467, 2017-05-15

著者

森田茂彦 松崎公紀

雑誌

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

巻号頁・発行日

vol.2014-GI-31, no.14, pp.1-5, 2014-03-10

---

チェスや将棋などにおいて,プレイヤの強さを数値として表すレーティングシステムが広く用いられている.レーティングアルゴリズムとして良く知られるイロレーティングでは,プレイヤ間のレート差と勝敗によってレートの増減が計算される.特に,弱いプレイヤが強いプレイヤに勝つと,レートの増分が大きくなる.本研究では,大貧民を対象としたレーティングアルゴリズムを提案する.大貧民では,プレイヤの強さに加えて,初期手札の良さが勝敗に大きく影響する.そのため,初期手札の良し悪しに差がある場合,従来のレーティングアルゴリズムを用いるとレートの増減が過剰であったり不足することが起こりうる.この問題を解決するため,初期手札の不均等性を考慮に入れたレーティングアルゴリズムを提案し,そのアルゴリズムについて評価を行う.

著者

森田 茂彦 松崎 公紀

雑誌

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

巻号頁・発行日

vol.2013, no.4, pp.1-6, 2013-02-25

被引用文献数

4

---

多人数ゲームでは,自分のプレイが自分の利得と関係なく他プレイヤの利得のみに影響する状態が発生する.そのため,多人数ゲームでは,他のプレイヤのプレイアルゴリズムに影響を受けて各プレイヤの強さが変動する可能性がある.本研究では,多人数不完全情報ゲームである大貧民を用いて,他プレイヤのプレイアルゴリズムの違いがプレイヤの強さに与える影響について調査した.同程度の強さを持つプレイヤとして,ヒューリスティックなルールに基づいてプレイするルールベース型,手役につけた評価値をもとにプレイする評価値型,モンテカルロ法により手役を決定するモンテカルロ型の3種類を用意した.さらに,これらよりも強いものを1種類,弱いものを1種類用意した.これらのプレイヤによる組合せを複数つくり対戦させ,対戦結果を比較した.その結果,自身と同じプレイヤが増えると,増えた分だけ得点を下げていく組合せを発見した.また,異なる強さのプレイヤの存在により,同程度の強さのプレイヤの得点差が変化することを確認した.In multi-player games, one's play may bring no gain to oneself but do some gain to others. This means the strength of a player can be affected by play algorithms of other players. In this study, we made a survey, for a multi-player imperfect-information game Daihinmin, how the difference of play algorithms of other players affect the strength of a player. We have made many experiments on several combinations of five players: three of them, rule-based player, evaluation-value-based player and naive Monte-Carlo player, are of almost the same strength; one is weaker than these three; the other is the strongest. From the experiments, we found some interesting results. First, in some combinations, the more players of the same algorithm attend, the less points the players get. Second, the strength of the three players varies when weaker or stronger players attend to the game.

著者

松崎 公紀 江本 健斗 劉 雨

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.4, no.4, pp.1-11, 2011-09-22

---

正規表現は広く用いられており,文章が正規表現にマッチするかどうかの問合せ (クエリ) を効率的に実行することは重要である.これまで,正規表現マッチングを高速に行う逐次的な手法について多くの研究がある.正規表現マッチングを並列に行う方法についても研究があるが,その多くは,複数の文章に対するクエリの並列実行や,複数のクエリの並列実行というような自明な並列実行について扱うものである.一方で,巨大な 1 つの文章に対して 1 つのクエリを行う場合には,正規表現マッチングそのものを並列化する必要が発生する.本稿では,正規表現マッチングを並列化する手法について議論を行う.また,本稿で提案する正規表現の並列マッチングの計算効率を評価するため,Hadoop を用いて実験を行いその結果を報告する.Hadoop は,大規模分散データに対して効率的に処理を行うことができる MapReduce フレームワークのオープンソース実装である.Regular expressions are now widely used and efficient implementation of regular expression matching is an important issue for efficient manipulation of data. There have been many studies for efficient implementation of regular expression matching. There have also been studies on parallel implementations of regular expression matching, but these implementations exploit parallelism only in executing a single query on multiple documents or in executing multiple queries on a single document. In this paper, we discuss a technique to parallelize a regular expression query itself. In other words, with this technique we can execute a regular expression query on a single document in parallel. We evaluate efficiency of regular expression matchings parallelized by the proposed method on the Hadoop; the Hadoop is an open-source implementation of the MapReduce framework that enables efficient processing of large-scale data.