著者
大久保誠也 小林 正人 本多 武尊 眞鍋秀聡 青木 輝人 柿下 容弓 小松原 頌之 西野 哲朗
出版者
一般社団法人情報処理学会
雑誌
情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)
巻号頁・発行日
vol.2007, no.20, pp.25-32, 2007-03-05
被引用文献数
7

本稿では,2006年11月18日にUEC(電気通信大学)で開催された,第1回UECコンピュータ大貧民大会(UECda-2006)の概要を報告する.大貧民は,日本で広く行なわれているトランプ・ゲームのひとつである.本大会は大貧民をプレイするコンピュータ・プログラムを対戦させる大会である.以下では,本大会の概要,本大会で採用した大貧民のルール,大会規模,使用したプログラム,および決勝戦の結果について述べる.In this talk, we give a summary report of the First UEC computer DAIHINMIN championship (UECda-2006) held at UEC (The University of Electronic-Communications) on November 18, 2006. DAIHINMIN is one of the most popular card game played in Japan. In this championship, computer DAIHINMIN engines compete against each other. We present the outline of the championship, the adopted rules, number of participants, used programs, and the result of the final match.

3 0 0 0 OA P=NP?問題

著者
西野 哲朗
出版者
一般社団法人 日本数学会
雑誌
数学 (ISSN:0039470X)
巻号頁・発行日
vol.54, no.1, pp.86-99, 2002-01-30 (Released:2008-12-25)
参考文献数
16
著者
門 裕太 大久保 誠也 若月 光夫 西野 哲朗
雑誌
研究報告ゲーム情報学(GI) (ISSN:21888736)
巻号頁・発行日
vol.2019-GI-41, no.12, pp.1-6, 2019-03-01

コンピュータ大貧民の研究がUEC標準ルールに基づいて行われている.しかし,ローカルルールの効果に関する研究は,ほとんど行われていない.本研究では,ローカルルールが各種指標にどのような影響を与えるかについて検討を行った.特に,平均終了手数や平均合法手数といった指標について検討した.また,UEC標準ルールに基づいた大貧民は,戦略的複雑さが,他の現代のゲームと比べて非常に単純であることが示されている.そこで,ローカルルールによって複雑にすることができるかについて検討した.さらに,大貧民は,交換ルールによる順位の格差が大きいことや,席順によって得点に差があることも知られている.そこで,各種ローカルルールが席順と得点に与える影響について調査した.具体的には,代表的な大貧民プログラムを11バックや5飛び,6リバースに対応させ,それらを用いた計算機実験によりデータを収集し,その分析を行った.その結果,11バックは,階級の格差を改善するが,平均合法手数や戦略的複雑さは変化させないこと.また,5飛びや6リバースは,席順に応じた得点の差に影響を与えることがわかった.
著者
西野 順二 西野 哲朗
雑誌
研究報告数理モデル化と問題解決(MPS)
巻号頁・発行日
vol.2011, no.9, pp.1-6, 2011-09-08

展開型の多人数不完全情報ゲームであるカードゲーム大貧民を対象として,相手手札の推定とその利用について検討した.2010 年 UEC コンピュータ大貧民大会で優勝したクライアントプログラム snowl の相手手札推定パラメータを変更して実験し,特定のクライアントの手札残存挙動を推定できること,強さの向上に効果があることを示した.また,強いクライアントの挙動をもとに推定パラメータを獲得した snowl クライアントは,シンプルな比較基準用のルールベース型クライアントである base に特化して推定パラメータを獲得した vsbase より,良い成績をあげることを示した.これらの手札推定と着手決定との関係について,5 枚を 3 人に分配するモデルによって,手札推定が必ずしも必要でない,あるいは重要性のない状況があることを示した.以上から,実際に推定されている相手手札の正確さそのものではなく,モンテカルロ探索など最終的な着手決定過程も経たときの,シミュレーション確度をあげる効果が重要であることを示した.In this paper, we show a characteristics of a model for opponent hand estimation algorithms for the Daihinmin that is a multi player imperfect information extensible game. To show the capability of opponent hand estimation algorithm, we have had experiments with the snowl that is the 2010 champion on the UECda : Computer Daihinmin Programming competitions. The opponent hand estimation ability of snowl is better than the vsbase client that is made to beat a specific program the 'base' which employs a rule based thinking algorithm. The snowl has universal strength for other type of thinking program. We show these imcompatibility in a mini model of Daihinmin that has 5 cards and 3 players, since we discuss the situation that have less importance of opponent hand estimations than total reasoning process.
著者
秋元 優太 西野 哲朗
出版者
国公私立大学図書館協力委員会
雑誌
大学図書館研究 (ISSN:03860507)
巻号頁・発行日
vol.122, pp.2142, 2022-11-30 (Released:2022-12-15)

司書の労働負担軽減や図書館の遠隔サポートの拡大を目的に,図書推薦をチャット形式で行うことができるシステムを提案する。本システムは,利用者に対しおすすめの図書と書架の位置を提示することができる。また,システムの実現手法を提案する上で,司書が図書案内する際にNDCに落とし込む手法に着目し,その手法を機械学習により実現することを試みた。提案システムと既存システムであるOPACとのそれぞれで,ある条件を満たす図書を探すという被験者実験を行い,提案システムが有効であることを示した。
著者
伊藤 毅志 保木 邦仁 西野 哲朗 棟方 渚 片寄 晴弘 池田 心
出版者
電気通信大学
雑誌
基盤研究(B)
巻号頁・発行日
2013-04-01

本研究では、ゲームにおける人間のミスに着目し、人間らしいミスを犯すゲームAIの構築を目指し、以下の研究成果を得た。1)ゲームにおける人間の犯すミスの原因に着目した分類。2)人間の生物学的成約を考慮したモデルを持ったゲームAIの構築。3)ゲームにおける技量を自動的に調整して良い勝負を演出できるゲームAIの提案と評価。4)人間の思考の特徴である「流れ」を持たせ、人間らしいプレイを実現するゲームAIの提案。これらの研究の成果は、人間と対戦するゲームAIに「強さ」という方向性以外の新しい評価基準をもたらし、多様なゲームAIの指針となると考えられる。
著者
西野 順二 西野 哲朗
雑誌
情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)
巻号頁・発行日
vol.3, no.2, pp.11-21, 2010-03-17

本論文では簡略化した評価値を導入することで,不決定性を持つため探索がしにくい多人数ゲームの終盤データベースを構築した.さらに,これを用いて多人数不完全情報ゲームの意思決定を行うプレイヤモデルへ適用し,コンピュータ大貧民大会サーバを用いた実験によりデータベースの有効性を示した.多人数ゲームには自己の判断によって利得を制御できず,第三者の合理的でない判断によって左右される不決定という状態を持つ.これに対して大貧民のサブセットである単貧民化を行って手の縮約を施し局面を限ったうえで,シングルトンにより単純化した評価を用いることで最終 10 枚の終盤データベースの構築を行い,3 人の場合で 38%,4 人で 25% の場合について必勝手を発見した.不完全情報の局面を必勝手に帰着することで着手決定を行うプレイヤモデルを構築し,対戦実験によりパフォーマンスの向上がみられ,有効なモデルであることを示した.
著者
西野 哲朗
雑誌
情報処理
巻号頁・発行日
vol.35, no.3, 1994-03-15
著者
中西 裕陽 富田 悦次 若月 光夫 西野 哲朗
出版者
一般社団法人情報処理学会
雑誌
研究報告アルゴリズム(AL) (ISSN:09135685)
巻号頁・発行日
vol.2014, no.14, pp.1-8, 2014-06-06

NP 完全である最大クリーク問題に対し,"節点数 n≧1 のグラフにおいて,グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば,最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である." ことを示す.これは,先に発表した結果 (信学論 (D),vol.J97-D,no.6,June 2014) の定量的改良である.This paper presents a further improved extended result for polynomial-time solvability of the maximum clique problem, that is: for any adjacent pair of vertices p and q where the degree of p is less than or equal to that of q in a graph with n vertices, if the degree of p is less than or equal to 3.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm.
著者
金山 貴泰 浅野 久美子 西野 哲朗 若月 光夫
出版者
一般社団法人情報処理学会
雑誌
研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
巻号頁・発行日
vol.2013, no.8, pp.1-6, 2013-05-16

発達障害児教育においては,児童の学習に関する動機の喚起・維持が困難な場合が多い.この問題を解決するために,近年,発達障害児教育の現場において,ICT(情報通信技術)を用いた教育支援システムの活用が注目されている.本研究では,発達障害児の興味を引くように,学習ゲームの仕組みを取り入れた,文字学習支援システム『おとかな!』を開発した.その際,教員とのディスカッションを通して,本システムに難易度設定,問題設定,学習記録の自動化といった機能も組み込んだ.本システムの有効性を検証するために,開発したシステムを特別支援学校の授業で実際に使用した.その結果,本システムは,発達障害児の興味を引き出し,学習への集中時間を増加させる効果があることがわかった.さらに,ICT教材の機能を活用することで,教材の準備にかかる教員の負担を大幅に軽減できることもわかった.In this study, we developed a learning support system for children with physical or mental disabilities. In order to reduce the burden of supervisors in education of these children. Educating these children is a burden for teachers. Because these children difficult to maintain the motivation for learning Therefore we developed this system to apply learning game for pull these child's interest. Through discussions with teachers, I incorporated the function difficulty settings, question setting, and automatic recording. In order to verify the validity of this system, it experimented in the special support school. As a result, this system which pull these child's interest and concentration time was increased. Furthermore, it turned out that the burden placed on preparation of teaching materials is mitigable by employing the feature of ICT teaching materials efficiently.
著者
小沼 啓 西野 哲朗
出版者
情報処理学会
雑誌
研究報告ゲーム情報学(GI) (ISSN:21862583)
巻号頁・発行日
vol.2011, no.3, pp.1-4, 2011-02-26

モンテカルロ法による最善手の推定にε-GREEDY 法を用いた,コンピュータ大貧民のプレイヤープログラムを開発した.さらに,最善手を得る確率を高めるために推定回数を増やす手法を採用し拡張した.この手法は, 従来のプレイヤープログラムより強いことが示された.In this paper, we propose ε-GREEDY method for finding the best legal move in computer Daihinmin while applying the Monte Carlo method. Furthermore, we increase the number of estimation of our ε-GREEDY method. Our result suggests that our method is the strongest among computer Daihinmin methods.
著者
綾部孝樹 大久保誠也 西野哲朗
出版者
一般社団法人情報処理学会
雑誌
研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
巻号頁・発行日
vol.2013, no.2, pp.1-6, 2013-05-16

本論では,人気の高い不完全情報カードゲームである大貧民をプレイするプログラムの特徴を明らかにする.はじめに,n-gram統計を用いた特徴量の抽出法,ならびに得られた特徴量を用いたクラスタ分析法を提案する.次に,いくつかの実験により,その提案手法が大貧民プログラムを,高い確率で正しくクラスタリングできる事を示す.
著者
西野順二 西野哲朗
雑誌
研究報告ゲーム情報学(GI)
巻号頁・発行日
vol.2013, no.5, pp.1-8, 2013-02-25

大貧民プレイヤプログラムなど不完全情報ゲームでは他プレイヤの手の情報を推定することが重要と考えられるが,局面によっては推定の必用が無い場合もある.本稿では不完全情報ゲームの性質を計る指標として偶然手番感度を提案し,これを用いて多人数不完全情報ゲームの大貧民の特性を調べることを目的とする.偶然手番感度は,相手手札の可能性を決める偶然手番がある場面での着手の利得に与える影響度であり,情報集合に含まれる局面可能性による利得の振れ幅を数値化したものである.大貧民を縮小した単貧民について,2人から5人に2から5枚を配布し合計12枚の全ての配布パターンについてその完全探索結果から,相手手札の可能性に対して最適着手は変わらず,偶然手番感度が低いことを示した.53枚5人プレイヤにおいても,モンテカルロシミュレーションによる推定利得から偶然手番感度を求める実験によってやはり偶然手番感度が低いことを示した.
著者
若月 光夫 富田 悦次 西野 哲朗
出版者
電気通信大学
雑誌
基盤研究(C)
巻号頁・発行日
2011-04-28

決定性プッシュダウン変換器のスタック記号を1種類に限定した決定性限定1カウンタ変換器について,それが最終状態受理式の場合,より一般的なε-推移を持つ場合についてもその等価性判定及び包含性判定が多項式時間で行えることを明らかにした.また,実時間最終状態受理式決定性限定1カウンタ変換器に対して,所属性質問及び等価性質問を用いた多項式時間の学習アルゴリズムを開発した.更に,正則言語の部分クラスに対する正例からの極限同定を組み込んだジュウシマツの歌構造解析ツールEUREKAを利用することによって,コンピュータ上でトランプゲームの大貧民の対戦を行うプログラムの挙動の規則性が抽出可能なことを示した.
著者
田中 圭介 西野 哲朗
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. COMP, コンピュテーション
巻号頁・発行日
vol.94, no.26, pp.51-60, 1994-04-27

否定数限定回路とは,回路中で使用できるNOTゲートの個数をlog(n+1)に制限した組合せ回路である.本稿では,n変数を反転する否定数限定回路(反転回路)の複雑さについて考察する.本研究以前に知られている反転回路のサイズの最良の上界は,O(n^2(logn)^2)である.本稿ではまず,この上界をO(n(logn)^2)に改良できることを示す.次に,反転回路のサイズと深さに関してそれぞれ,5n+3log(n+1)-6および4log(n+1)+2の下界を示す.さらに,n変数を反転する否定数限定回路にある種の制約を加え,その回路サイズが超線形下界をもつような二つの特殊な場合を紹介する.
著者
西野 順二 西野 哲朗
雑誌
研究報告バイオ情報学(BIO)
巻号頁・発行日
vol.2011, no.31, pp.1-4, 2011-11-24

不完全情報多人数ゲームのうち大貧民を含むトリック型ゲームでは冒頭の偶然手番で選ばれたカードの分配状態が明らかでなく、ゲームの進展に応じて徐々に情報が明らかになる。このようなゲームを対象としてモンテカルロ木探索によって最良な決定をしようとするとき未知情報である相手情報すなわち状態の推定は重要と考えられる。しかし実験的には状態の推定を行わないときと比較して、その効果はあまり大きな寄与がみとめられなかった。本論文ではこの事実にもとづいて、不完全情報ゲームの状態推定が、多人数ゲームのモンテカルロ木探索において果たす効果について、状態の集合を最適な着手による同値類に分けることで、定性的な分析を行った。とりうる状態数が選択可能な合法手に対して非常に大きいため、複数の状態を仮定して探索するモンテカルロ木探索にたいして、状態の確定的な推定はあまり重要ではないことを示した。A trick based card game is an imperfect information game that has a chance move at the beginning of the game and then the whole situation is closed for each other players. This information is partially reveal as the game goes on. A situation estimation process is thought as a very important factor to make program playing the game using Monte Carlo tree search. In this paper grouping analysis on the situation set according to similarity of derived moves from the situation group, in order to discusses the effectiveness of the situation estimation process with UCT search. As a result, we show that the mass of situations causes ineffectiveness of the situation detection and its usage.
著者
若月 光夫 富田 悦次 西野 哲朗
出版者
電気通信大学
雑誌
基盤研究(C)
巻号頁・発行日
2008

決定性プッシュダウン変換器のスタック記号を1 種類に限定した決定性限定ワンカウンタ変換器について,それが空スタック受理式及び実時間最終状態受理式の場合,その等価性判定が多項式時間で行えることを証明した.また,決定性限定ワンカウンタオートマトンのある部分クラス等が,正例から多項式時間で極限同定可能なことを証明した.更に,正則言語の部分クラスに対する正例からの極限同定を利用した,ジュウシマツの歌文法の解析手法を改良し,自動化を図った.
著者
富田 悦次 高橋 治久 西野 哲朗 若月 光夫 垂井 淳
出版者
電気通信大学
雑誌
基盤研究(C)
巻号頁・発行日
2007

最大クリークを抽出する新しいアルゴリズムMCSを開発し,格段に高速であることを明らかにした.これにより,従来では100日以上かかっても解けなかった幾つかの問題を100秒以内で解くことに成功した.最大クリーク問題が多項式時間的に可解となる基本的結果も確立した.また,最大クリーク抽出アルゴリズムがハイパーグラフにおいても効率的に稼働する様に拡張した.更に,これらのアルゴリズムをデータマイニングなどの実問題に応用して有効な結果を得た.