しりとりゲームの数理的解析(<特集>ゲームプログラミング)
スポンサーリンク
概要
- 論文の詳細を見る
"しりとり"を完全情報ゲームとして数学的に定義した"しりとりゲーム"を考えると,グラフ上のゲームとしてモデル化することができる.これは完全情報ゲームであるため理論上は解けることになるが,問題のサイズが大きくなるにつれ全探索は困難となる.本論文では,しりとりゲームに関する解析を行い,ゲームを効率的に探索する手法を提案する.この手法は数理的解析,探索の効率化の2つの部分から成っており,数理的解析としてグラフのより簡単な形への変形を行っている.加えて,しりとりゲームにおける先手の勝率に関して実験,考察を行う.
- 一般社団法人情報処理学会の論文
- 2002-10-15
著者
-
田中 哲朗
東京大学情報基盤センター
-
胡 振江
東京大学大学院情報理工学系研究科
-
武市 正人
東京大学大学院情報理工学系研究科
-
胡 振江
国立情報学研究所アーキテクチャ科学研究系
-
武市 正人
電気通信大学電気通信学部計算機科学科
-
武市 正人
東京大学
-
武市 正人
東京大学工学部
-
田中 哲朗
東京大学工学部
-
伊藤 隆
東京大学大学院情報理工学系研究科数理情報学専攻
-
伊藤 隆
東京大学大学院情報理工学系研究科数理情報学専攻:(現)三菱電機株式会社情報技術総合研究所
関連論文
- 4 大規模クラスタシステムでの実行 : GPS将棋の試み(コンピュータ将棋の不遜な挑戦)
- ボードゲーム「シンペイ」の完全解析(解析,ゲームプログラミング)
- ボードゲーム「シンペイ」の完全解析
- 少数キーを用いた日本語入力
- 3M-5 Bidirectional XML Transformation with Bi-X
- 3M-4 依存関係記述スキーマによる双方向XMLアプリケーションの開発(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- 3M-3 双方向変換に基づくウェブパブリッシング支援システムVu-X(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- 神経系の双方向マルチスケールシミュレーションと100時間ワークショップ : 東京大学21世紀COEプログラム「情報科学技術戦略コア」
- 2. 情報科学技術戦略コア(21世紀卓越した情報研究拠点プログラムの目指す研究(前編))
- 情報科学技術戦略コア
- 5-2-1 東京大学「情報科学技術戦略コア」(5-2 情報・電気・電子分野の21世紀COE,3プロジェクトの拠点リーダーより)(5.大学での研究プロジェクト : 21世紀COEプログラム)(グローバル化時代の教育と研究)
- 部分ゲームの解析結果を用いたカルキュレーションの戦略(ゲームプログラミング)
- 1.マルチコア計算機と基本的な並列化技法(マルチコアを活かすお手軽並列プログラミング)
- インターネットを用いた複数経路データ伝送方式の性能評価
- 「計算機科学」は死語?
- モデル検査技術を利用したプログラム解析器の生成ツール
- 新規節点で固定深さの探索を行うdf-pnの拡張
- I.Q Intelligent QubeのNP完全性の証明
- 特集「ゲームプログラミング」の編集にあたって
- 並列プログラムの候補生成と適合性検査による並列化
- 多地点テレビ会議における通信品質のばらつきが主観品質に及ぼす影響
- 複数経路を用いてIPパケット転送するマルチルートゲートウェイの実装と評価
- 5U-2 複数経路を用いてIPパケット転送するマルチルートゲートウェイの実装と評価
- 5U-1 TCP/IPパケットを複数経路に分配して通信する方式の性能評価
- B-11-2 複数のTCP通信にDRRを適用する場合の通信品質の評価
- B-11-1 最低保証帯域を設定したTCP通信品質の評価
- B-7-51 複数経路を用いたTCP通信に関する一検討
- B-11-14 電子商取引に帯域制御を適用する場合の通信品質の検討
- B-7-78 インターネットを用いた複数経路データ転送方式に関する一検討
- IPパケット損失がMPEG1音声・画像品質に及ぼす影響の評価
- IPパケット損失がMPEG1音声・画像品質に及ぼす影響の評価
- MPEG1総合品質に対する音声パケット損失及び画像フレムレートの影響の評価
- IPパケット損失がMPEG1画像品質に及ぼす影響の評価
- TCP通信を帯域保証する場合の問題点の分析
- TCP通信を帯域保証する場合の問題点の分析
- TCP通信を帯域保証する場合の問題点の分析
- 複数のTCP通信にWFQを適用する場合の通信品質の検討
- TCP通信を帯域保証する場合の問題点の分析
- 将棋プログラムの大規模並列実行
- パズルにまつわる最近の話題(思考ゲーム)
- AP1000へ移植したUtiLisp
- 補関数の生成による複製機能付きプログラムの自動双方向化
- 6.双方向変換による高信頼構造化文書処理(第1部:高い生産性を持つ高信頼ソフトウェア作成技術の開発,学と産の連携による基盤ソフトウェアの先進的開発)
- Generator-of-generators に基づく Fortress ライブラリ
- リスト上の最大マーク付け問題を解く並列プログラムの導出
- 木スケルトンによるXPathクエリの並列化とその評価
- 木上の双方向変換を利用したファイルマネージャの実現
- 木上の双方向変換を利用したファイルマネージャの実現
- データマイニングのアルゴリズム記述を容易にする拡張行列演算の提案
- 決定論的2階パターンとプログラム変換への応用
- 「どうぶつしょうぎ」 の完全解析
- NetBootによる端末を用いた教育用計算機システムの開発と評価(分散システム構築運用技術,ユーザ指向の分散システム/インターネットの運用・管理)
- 利得の最適連想規則を求める線形時間アルゴリズムの導出
- 最大重み和問題の線形時間アルゴリズムの導出
- ACM PLI 2000会議報告
- ナップサック問題およびその発展問題の統一的解法
- 証明数と反証数を用いたλ探索(探索,ゲームプログラミング)
- 駒の関係を利用した将棋の評価関数の学習(評価関数,ゲームプログラミング)
- 効率的な詰将棋探索のための評価関数(セッション(1) : ゲーム情報学(1))
- 大規模クラスタシステムでの実行 : GPS将棋の試み
- プログラム融合変換の実用的有効性の検証
- HYLOシステムによるプログラム融合変換の実現
- パズルの解法(ゲームとコンピュータ)
- 木変換言語の双方向化に関する事例研究(サイバー増大ページ論文概要,新しいソフトウェアの実現,サイバー増大号)
- 「不惑」の中国若手研究リーダーたち
- スケルトン並列プログラミング
- 最適化機構を持つC++並列スケルトンライブラリ(サイバー増大ページ論文概要,サイバー増大号)
- Joseph E. Stoy : Denotational Semantic: The Scott-Strachey Approach to Programming Language Theory, MIT Press, 1977(20世紀の名著名論)
- しりとりゲームの数理的解析(ゲームプログラミング)
- 変換戦略の記述に基づくプログラムの自動生成システムの実装
- 最小属性値を持つ多次元探索木の提案.
- 無理数を近似する分数(プログラム・プロムナード)
- 蓄積引数を持つ関数プログラムの融合変換
- 関数プログラムのプロモーション変換のための二手法の関係
- 最中限の終盤の分析
- 部分計算を用いた手生成の高速化
- 怪物を閉じ込める(プログラム・プロムナード)
- 組木細工(プログラム・プロムナード)
- 3.Mac OS X編(2.教育用計算機環境の事例)(大規模分散ネットワーク環境における教育用計算機システム)
- 論理回路のシミュレーション(プログラム・プロムナード)
- パズル(ゲーム情報学研究の事例)(ゲーム情報学)
- ハフマン符号を解く(プログラム・プロムナード)
- プログラム・プロムナード : 大小の贈り物
- 倉庫番パズル(プログラム・プロムナード)
- 1, 600台のインターネット端末をつないだ : 東京大学教育用計算機システム(ECCS)
- 箱積みが最善引き分けの証明の別解
- 箱積みが最善引き分けの証明
- 平面上の矩形和の最大値問題の並列プログラムの導出
- グラフの探索関数の再帰的定義と変換(特集●プログラミング及びプログラミング言語)
- 疎結合並列計算機上の遅延評価型関数型言語処理系の性能評価
- 複数OS環境におけるユーザ管理
- 大規模計算機センターのセキュリティ対策事例
- マルチユーザ環境における仮想マシン上のWindows環境の構築
- 関数型言語処理系におけるデータ構成子のunbox化
- FPGAによる関数型言語向きアーキテクチャを持つプロセッサの実装
- 最善手の予測に基づくゲーム木探索の分散並列実行
- 入玉指向の将棋プログラムの作成
- 特集「ゲームプログラミング」の編集にあたって
- プログラム運算による並列プログラミング(特集・新世紀フォーラム)
- 定跡データベースの評価法の提案