証明数と反証数を用いたλ探索(探索,<特集>ゲームプログラミング)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では脅威度と証明数・反証数の双方を利用するdf-pn λ探索を提案する.脅威度と証明数・反証数は,両者ともAND/OR木探索を効率的に行うための指標であり,脅威度を利用するλ探索と,証明数・反証数を利用するdf-pn探索は,どちらも優れた探索アルゴリズムである.脅威度と証明数・反証数の双方を用いることで,探索をさらに効率的に行うことは自然なアイデアである.脅威度と証明数・反証数の関係を結び付けるために,本論文では各節点ごとに,各脅威度に対応する疑似節点をモデル化する.そのうえで,疑似節点上の証明数・反証数を用いて,元の節点の証明数・反証数を定義することを提案し,それにより探索が制御されることを示す.さらに,性質の異なる複数のゲームを対象に,df-pn λ探索とdf-pn探索の性能を比較する実験を行った.その結果,将棋や囲碁においてdf-pn λ探索はdf-pn探索よりも性能が良いことを確認した.
- 一般社団法人情報処理学会の論文
- 2007-11-15
著者
-
田中 哲朗
東京大学情報基盤センター
-
金子 知適
東京大学大学院総合文化研究科
-
副田 俊介
産業技術総合研究所
-
田中 哲朗
東京大学工学部
-
岸本 章宏
公立はこだて未来大学システム情報科学部情報アーキテクチャ学科
-
美添 一樹
東京大学大学院情報理工学系研究科コンピュータ科学専攻
-
ミュラー マーティン
アルバータ大学コンピューティング・サイエンス学科
-
副田 俊介
公立はこだて未来大学
-
美添 一樹
中央大学研究開発機構
-
田中 哲朗
東京大学
-
岸本 章宏
公立はこだて未来大学
-
金子 知適
The University Of Tokyo
-
田中 哲朗
the University of Tokyo
-
副田 俊介
グーグル株式会社
関連論文
- 3 災害情報学(新しい○○情報学)
- 4 大規模クラスタシステムでの実行 : GPS将棋の試み(コンピュータ将棋の不遜な挑戦)
- ボードゲーム「シンペイ」の完全解析(解析,ゲームプログラミング)
- ボードゲーム「シンペイ」の完全解析
- CBRテロを想定した避難シミュレータ(社会システムにおける知能,「社会システムにおける知能」および一般)
- モンテカルロ木探索 : コンピュータ囲碁に革命を起こした新手法
- チェッカー解明秘話
- 歩行者間の距離を利用した一次元人流モデル (特集 「知識発見の生命科学への応用」および一般)
- 分岐因子が一様な探索空間のためのAND-OR木探索アルゴリズム(基礎・理論,人工知能分野における博士論文)
- 部分ゲームの解析結果を用いたカルキュレーションの戦略(ゲームプログラミング)
- 脅威度を用いたゲーム木探索アルゴリズム(研究会推薦博士論文速報)
- 3 最近のコンピュータ将棋の技術背景とGPS将棋(コンピュータ将棋の新しい波)
- 棋譜から学ぶ将棋プログラム(平成20年度論文賞の受賞論文紹介)
- 新規節点で固定深さの探索を行うdf-pnの拡張
- I.Q Intelligent QubeのNP完全性の証明
- 将棋の棋譜を利用した大規模な評価関数の学習
- 特集「ゲームプログラミング」の編集にあたって
- 学生による授業評価に基づいた図形科学講義の分析
- CBRテロを想定した避難シミュレータ(社会システムにおける知能,「社会システムにおける知能」および一般)
- 避難シミュレータを利用した避難誘導計画の検証及び立案支援の提案
- 将棋プログラムの大規模並列実行
- パズルにまつわる最近の話題(思考ゲーム)
- 最適解を求める2つの探索アルゴリズムのスーパーパズにおける性能比較について(各種ゲーム)
- AP1000へ移植したUtiLisp
- 一次元歩行者モデルを用いた高速避難シミュレータの開発
- 一次元歩行者モデルを用いた高速避難シミュレータの開発
- 「どうぶつしょうぎ」 の完全解析
- プログラム肉付けによる複数漢字書体間のスケルトンデータの共有
- SPARC の特徴を生かしたUtiLisp/C の実現法
- NetBootによる端末を用いた教育用計算機システムの開発と評価(分散システム構築運用技術,ユーザ指向の分散システム/インターネットの運用・管理)
- 囲碁の部分問題における両利きの探索(Session 3)
- 証明数と反証数を用いたλ探索(探索,ゲームプログラミング)
- 勝率に基づく評価関数の評価と最適化(評価関数,ゲームプログラミング)
- 駒の関係を利用した将棋の評価関数の学習(評価関数,ゲームプログラミング)
- ゲーム情報学とゲーム情報学研究会(研究会千夜一夜)
- 将棋におけるProbCutの静止探索への応用(Session 1)
- 倉庫番における部分マップの組合せに基づく手詰り判定手法
- 効率的な詰将棋探索のための評価関数(セッション(1) : ゲーム情報学(1))
- 効率的な詰将棋探索のための評価関数 (人工知能基礎論研究会(第55回)特集「エンタテイメントコンピューティングの基礎と応用」および一般) -- (セッション(1)ゲーム情報学(1))
- 述語論理で表された特徴関数のネットワーク型局面評価器への自動変換
- ゲームプログラムのためのパターン型評価関数の自動生成法(ゲームプログラミング)
- 関係代数を用いたfeature中の論理式の効率的評価方法
- 大規模クラスタシステムでの実行 : GPS将棋の試み
- 人流計測による避難誘導効果の実証的検証
- 人流計測による避難誘導効果の実証的検証
- 人流計測による避難誘導効果の実証的検証
- CBRテロに対する対処訓練を支援する避難シミュレータの実現 (「知能と社会・ネットワーク」および一般発表)
- パズルの解法(ゲームとコンピュータ)
- 清水女流王将vsあから2010--コンピュータの思考過程を追う (特集 あから2010勝利への道)
- あから2010のシステム設計と操作概要 (特集 あから2010勝利への道)
- オンラインゲーム運営補助のためのツール(ゲームAI)
- しりとりゲームの数理的解析(ゲームプログラミング)
- 無理数を近似する分数(プログラム・プロムナード)
- 最中限の終盤の分析
- 部分計算を用いた手生成の高速化
- 完全情報ゲームとAND/OR木探索(ゲームとコンピュータ)
- 怪物を閉じ込める(プログラム・プロムナード)
- 組木細工(プログラム・プロムナード)
- 3.Mac OS X編(2.教育用計算機環境の事例)(大規模分散ネットワーク環境における教育用計算機システム)
- 論理回路のシミュレーション(プログラム・プロムナード)
- パズル(ゲーム情報学研究の事例)(ゲーム情報学)
- ハフマン符号を解く(プログラム・プロムナード)
- プログラム・プロムナード : 大小の贈り物
- 倉庫番パズル(プログラム・プロムナード)
- 1, 600台のインターネット端末をつないだ : 東京大学教育用計算機システム(ECCS)
- 高度なIT人材を育成するITスクールの実施例(2004年度東京会場)
- プライバシーを保護する匿名認証技術
- あから2010勝利への道 : 4.清水女流王将 vs あから2010:コンピュータの思考過程を追う
- あから2010勝利への道 : 2.あから2010のシステム設計と操作概要
- 部品合成による漢字スケルトンフォントの作成
- 箱積みが最善引き分けの証明の別解
- 箱積みが最善引き分けの証明
- CBRテロ被害予測のためのシミュレータ
- 避難誘導効果の検証に向けた人流計測
- 4.センサデータマイニングを活用した安全安心な避難誘導への取組み(安全・安心社会実現のためのセンサデータマイニング応用)
- 避難シミュレータのための動線解析と避難誘導支援への応用
- 疎結合並列計算機上の遅延評価型関数型言語処理系の性能評価
- 複数OS環境におけるユーザ管理
- 大規模計算機センターのセキュリティ対策事例
- マルチユーザ環境における仮想マシン上のWindows環境の構築
- 攻略工房-1-MMX命令を攻略する
- マルチメディア命令セットを使った文字列処理, 記号処理の高速化
- 数当てゲ-ム(MOO,マスタ-マインド) (ゲ-ムプログラミング) -- (第3章 パズル)
- ACM Programming Languages Summer Extravaganza報告
- 関数型言語処理系におけるデータ構成子のunbox化
- FPGAによる関数型言語向きアーキテクチャを持つプロセッサの実装
- コンピュータ将棋の評価関数と棋譜を教師とした機械学習(コンピュータ将棋の技術〔第5回〕)
- 一次元歩行者モデルを用いた高速避難シミュレータの開発とその応用
- GPS将棋とテキストプロトコルによる大規模将棋ソフトウェアの組み立て
- 最善手の予測に基づくゲーム木探索の分散並列実行
- コンピュータ将棋を用いた棋譜の自動解説と評価
- 入玉指向の将棋プログラムの作成
- 特集「ゲームプログラミング」の編集にあたって
- 局面の局所的な類似性を利用したモンテカルロ木探索の効率化
- 新規節点で固定深さの探索を行うdf-pnの拡張 (特集 ゲームプログラミング)
- 定跡データベースの評価法の提案
- 避難シミュレータのための動線解析と避難誘導支援への応用
- LEADING EDGE 科学の最前線から 一流プロ棋士と対等に渡り合える将棋プログラムを開発 : ｢第2回電王戦｣で注目を集める｢GPS将棋｣の開発者に聞く
- 多数の計算機を活用したゲーム木探索技術の進歩 : 三浦弘行八段とGPS将棋との対局を振り返って (ミニ特集 現役プロ棋士に勝ち越したコンピュータ将棋 : 第2回電王戦,第23回世界コンピュータ将棋選手権速報)
- タイトル無し