(57)【要約】【課題】被験者の体験データを取得することなく、ＲＰＧの攻略法を算出することができ、人間が楽しいと感じるゲーム要素を工学的に把握することができ、コンピュータによって操作されるキャラクタの行動選択の仕方を容易にプログラミングすることができるＲＰＧの攻略法算出装置、算出方法、算出プログラム及びこのプログラムを記録した記録媒体を提供する。【解決手段】ＲＰＧの攻略法算出装置は、ＲＰＧのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、この制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出部と、プレイヤーの状態及び時点が与えられるとその時点のその状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定部とを備えており、プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力する。【選択図】図１
2013252247.tif 000002
【特許請求の範囲】
【請求項１】
ロールプレイングゲームのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、該制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出部と、
前記プレイヤーの状態及び時点が与えられると当該時点の当該状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定部とを備えており、
前記プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力することを特徴とするロールプレイングゲームの攻略法算出装置。
【請求項２】
前記最適政策算出部は、前記制御期間におけるマルコフ決定過程問題を動的計画法で求めるように構成されていることを特徴とする請求項１に記載の攻略法算出装置。
【請求項３】
ロールプレイングゲームのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、該制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出工程と、
前記プレイヤーの状態及び時点が与えられると当該時点の当該状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定工程とを備えており、
前記プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力することを特徴とするロールプレイングゲームの攻略法算出方法。
【請求項４】
前記最適政策算出工程は、前記制御期間におけるマルコフ決定過程問題を動的計画法で求めるように構成されていることを特徴とする請求項３に記載の攻略法算出方法。
【請求項５】
ロールプレイングゲームのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、該制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出手順と、
前記プレイヤーの状態及び時点が与えられると当該時点の当該状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定手順とをコンピュータで実行させ、
前記プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力することを特徴とするロールプレイングゲームの攻略法算出プログラム。
【請求項６】
前記最適政策算出手順は、前記制御期間におけるマルコフ決定過程問題を動的計画法で求めるように構成されていることを特徴とする請求項５に記載の攻略法算出プログラム。
【請求項７】
ロールプレイングゲームのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、該制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出手順と、
前記プレイヤーの状態及び時点が与えられると当該時点の当該状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定手順とをコンピュータで実行させる攻略法算出プログラムを記録したコンピュータ読み取り可能な記録媒体であり、
前記プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力することを特徴とするロールプレイングゲームの攻略法算出プログラムを記録した記録媒体。
【請求項８】
前記最適政策算出手順は、前記制御期間におけるマルコフ決定過程問題を動的計画法で求めるように構成されていることを特徴とする請求項７に記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ロールプレイングゲーム（ＲＰＧ）をモデル化してゲームの攻略法（行動選択の仕方）を算出するための攻略法算出装置、算出方法、算出プログラム及びこのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
近年、コンピュータの低価格化に伴い、テレビゲーム機が広く普及し、ゲームの一分野として、ＲＰＧも広く普及している。このようなＲＰＧの開発を行う場合、従来は以下のような問題点を有していた。
（１）プレイヤーが遊ぶ際にどのようにプレイするかを把握するためには、多くの被験者に遊んでもらいプレイヤーの体験データを取得することが行われる。しかしながら、これは、多くの被験者を雇う必要があるため、コストが大幅に高くなるのみならず、データを得るのに多大な時間を要する。
（２）日々販売されるＲＰＧは多数あるが、その中でヒットするＲＰＧは非常に少数である。そのようにヒットしたＲＰＧには、人間が楽しいと感じる要素が多数含まれていると考えられるが、どのような要素が楽しいと感じる要素であるのか工学的には未だ把握されていない。
（３）最近は、プレイヤーの補佐を行うキャラクタ（お仲間キャラクタ）をコンピュータが操作するＲＰＧも多いが、このようなお仲間キャラクタの賢い行動（コマンド）選択の仕方をプログラミングすることはかなり難しい。
【０００３】
一方、ゲーム情報学等の工学分野においては、ＲＰＧをマルコフ決定過程（ＭＤＰ）等の確率モデルを用いてモデル化し、ゲームを攻略する戦略について数理工学的に扱う研究がなされ、報告されている（例えば、非特許文献１及び２）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】高木幸一郎、雨宮真人、「ロールプレイングゲーム（ＲＰＧ）の戦闘におけるバランス自動調整システム開発のための基礎的考察」、情報処理学会研究報告、ＧＩ、２００１（２８）、ｐｐ．３１−３８（２００１）
【非特許文献２】高木幸一郎、雨宮真人、「ロールプレイングゲーム（ＲＰＧ）のバランスとは何か、分析およびその調整に関する提案」、情報処理学会研究報告、ＧＩ、２００１（５８）、ｐｐ．６７−７４（２００１）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１及び２に開示されているごとき、従来のモデル化は、ＲＰＧの一部のみのモデル化であった。即ち、プレイヤーがマップ上を移動するマップモードと、マップモードにおいて敵と遭遇した際に開始される戦闘モードとからなる冒険型のＲＰＧにおいて、戦闘モードのみのモデル化であり、これでは、ＲＰＧ全体の攻略法（行動選択の仕方）を算出することができず、前述した（１）〜（３）のごとき開発支援上の問題点を解決することができなかった。
【０００６】
従って本発明の目的は、被験者の体験データを取得することなく、ＲＰＧの攻略法（行動選択の仕方）を算出することができるＲＰＧの攻略法算出装置、算出方法、算出プログラム及びこのプログラムを記録した記録媒体を提供することにある。
【０００７】
本発明の他の目的は、人間が楽しいと感じるゲーム要素を工学的に把握することができるＲＰＧの攻略法算出装置、算出方法、算出プログラム及びこのプログラムを記録した記録媒体を提供することにある。
【０００８】
本発明のさらに目的は、コンピュータによって操作されるキャラクタの行動選択の仕方を容易にプログラミングすることができるＲＰＧの攻略法（行動選択の仕方）を算出することができるＲＰＧの攻略法算出装置、算出方法、算出プログラム及びこのプログラムを記録した記録媒体を提供することにある。
【課題を解決するための手段】
【０００９】
本発明によれば、ＲＰＧのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、この制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出部と、プレイヤーの状態及び時点が与えられるとその時点のその状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定部とを備えており、プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力するＲＰＧの攻略法算出装置が提供される。
【００１０】
ＲＰＧの自動開発に資する研究開発としてＭＤＰなる確率モデルを用いた定式化は従来より行われていたが、従来技術では、ＲＰＧの一部のイベントを定式化するのみの不充分なものであった。
【００１１】
本発明によれば、ＲＰＧ全体をＭＤＰで定式化している。これにより、
（Ａ）開発者のみが知っている情報を既知と仮定したもとでの攻略法の算出を行い、
（Ｂ）開発者のみが知っている情報を未知と仮定した（一般のプレイヤーと同様の立場を仮定した）もとでの攻略法の算出を行っている。
【００１２】
これは、ゲーム情報学分野における学際的な知見を与えるのみならず、ゲーム産業においても以下のごとく有用である。
【００１３】
第１に、本発明で算出される目的（お金の獲得等）のもとでの攻略法（行動選択の仕方）をコンピュータにシミュレーションさせることによって、その目的におけるプレイヤーのゲーム結果をシミュレートできる。このシミュレーションを利用することによって、マップ上に隠されたアイテムやイベントに遭遇する割合（仮にプレイヤーが１万人いた場合に何人が遭遇できるか）等を把握でき、その割合を見ながら適切な隠し場所を設定することができる。
【００１４】
第２に、本発明で算出される数理工学的に最適な攻略法と実際のプレイヤーによる攻略法との比較を行うことにより、人間が楽しいと感じるゲーム要素を工学的に把握できる可能性がある。人間が楽しいと感じるゲーム要素を確率モデル上のパラメータ設定のある種のパターンとして把握できれば、そのような要素を多く含むゲーム開発を行うことができる。
【００１５】
第３に、近年では、ゲーム中にプレイヤーに協力するコンピュータ操作のキャラクタの登場が多い。このようなコンピュータによって操作されるキャラクタの行動選択の仕方をプログラミングするのは難しかったが、本発明により種々の目的毎の攻略法を算出することによって、各目的に適した（プレイヤーに協力する）キャラクタの行動選択の仕方（攻略法）をプログラミングすることが可能となる。
【００１６】
最適政策算出部は、制御期間におけるＭＤＰ問題を動的計画法（ＤＰ）で求めるように構成されていることが好ましい。
【００１７】
本発明によれば、さらに、ＲＰＧのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、この制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出工程と、プレイヤーの状態及び時点が与えられるとその時点のその状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定工程とを備えており、プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力するＲＰＧの攻略法算出方法が提供される。
【００１８】
最適政策算出工程は、制御期間におけるＭＤＰ問題をＤＰで求めるように構成されていることが好ましい。
【００１９】
本発明によれば、さらにまた、ＲＰＧのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、この制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出手順と、プレイヤーの状態及び時点が与えられるとその時点のその状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定手順とをコンピュータで実行させ、プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力するＲＰＧの攻略法算出プログラムが提供される。
【００２０】
最適政策算出手順は、制御期間におけるＭＤＰ問題をＤＰで求めるように構成されていることが好ましい。
【００２１】
本発明によれば、さらに、ＲＰＧのプレイヤーのゲーム開始時点における初期状態と制御期間の長さとが与えられた際に、この制御期間中に得られる総報酬に相当する期待総利得を最大にする政策を出力する最適政策算出手順と、プレイヤーの状態及び時点が与えられるとその時点のその状態においてそれ以降の期待総利得を最大にする最適行動及び期待総利得の最大値を出力する行動決定手順とをコンピュータで実行させる攻略法算出プログラムを記録したコンピュータ読み取り可能な記録媒体であり、プレイヤーの初期状態及び制御期間の長さに対して制御期間における期待総利得を最大にすることが保証された最適政策を出力するＲＰＧの攻略法算出プログラムを記録した記録媒体が提供される。
【００２２】
最適政策算出手順は、制御期間におけるＭＤＰ問題をＤＰで求めるように構成されていることが好ましい。
【発明の効果】
【００２３】
本発明によれば、制御期間における期待総利得を最大にすることが保証された政策が出力されるので、プレイヤーの初期状態と制御期間長とに対して制御期間における期待総利得を最大にする政策を出力することが可能となり、そのＲＰＧに関する攻略法（行動選択の仕方）を算出することができる。
【００２４】
即ち、本発明によれば、攻略法をコンピュータにシミュレーションさせることによって、被験者の体験データを取得することができ、算出される数理工学的に最適な攻略法と実際のプレイヤーによる攻略法との比較を行うことにより、人間が楽しいと感じるゲーム要素を工学的に把握することができ、さらに、人間が楽しいと感じるゲーム要素を確率モデル上のパラメータ設定のある種のパターンとして把握できれば、そのような要素を多く含むゲーム開発を行うことができる。また、種々の目的毎の攻略法を算出することによって、各目的に適したプレイヤーに協力するキャラクタの攻略法を容易にプログラミングすることが可能となる。
【図面の簡単な説明】
【００２５】
【図１】本発明の第１の実施形態として、ＲＰＧの開発支援に用いる攻略法算出装置の全体構成を概略的に示すブロック図である。
【図２】図１の実施形態における攻略法算出装置の主要部の動作を説明するフローチャートである。
【図３】図１の実施形態における攻略法算出装置の主要部の構成を概略的に示すブロック図である。
【図４】図１の実施形態におけるＤＰグラフの一例を示す図である。
【図５】図１の実施形態における攻略法算出装置の行動決定部の動作を説明するフローチャートである。
【図６】第１の実施形態及び第２の実施形態の実施例におけるマップの構成例を示す図である。
【発明を実施するための形態】
【００２６】
図１は本発明の第１の実施形態としてＲＰＧの開発支援に用いる攻略法算出装置の全体構成を概略的に示しており、図２は本実施形態における攻略法算出装置の主要部の動作を説明しており、図３は本実施形態における攻略法算出装置の主要部の構成を概略的に示しており、図４は本実施形態におけるＤＰグラフの一例を示しており、図５は本実施形態における攻略法算出装置の行動決定部の動作を説明している。この第１の実施形態は、各種確率分布を支配する真のパラメータθ＊が既知の場合である。
【００２７】
図１に示すように、本実施形態における攻略法算出装置は、バス１０を介して互いに接続された中央処理装置（ＣＰＵ）１１と、リードオンリメモリ（ＲＯＭ）１２と、ランダムアクセスメモリ（ＲＡＭ）１３と、ハードディスク駆動装置（ＨＤＤ）１４と、サウンド処理部１５と、画像処理部１６と、ブルーレイディスク／デジタルバーサタイルディスク（ＢＲ／ＤＶＤ）駆動装置１７と、入出力インタフェース１８と、通信インタフェース１９とを備えたコンピュータ及びこれを作動させるプログラムから構成される。
【００２８】
サウンド処理部１５はスピーカ２０に接続されており、画像処理部１６は表示ディスプレイ２１に接続されている。ＢＲ／ＤＶＤ駆動装置１７はブルーレイディスク／デジタルバーサタイルディスク／コンパクトディスク（ＢＲ／ＤＶＤ／ＣＤ）２２が装着可能となっており、入出力インタフェース１８にはコントローラ２３、キーボード２４及びマウス２５が接続されている。
【００２９】
ＣＰＵ１１は、ＲＯＭ１２に記憶されているオペレーションシステム（ＯＳ）やブートプログラム等の基本プログラムに従ってＲＡＭ１３に記憶されているプログラムを実行して本実施形態の処理を行う。また、ＣＰＵ１１は、ＲＡＭ１３、ＨＤＤ１４、音声処理部１５、画像処理部１６、ＢＲ／ＤＶＤ駆動装置１７、入出力インタフェース１８、及び通信インタフェース１９の動作を制御する。
【００３０】
ＲＡＭ１３は攻略法算出装置のメインメモリとして使用され、ＨＤＤ１４やＢＲ／ＤＶＤ駆動装置１７から転送されたプログラムやデータを記憶する。また、ＲＡＭ１３は、プログラム実行時の各種データが一時的に記憶されるワークエリアとしても使用される。
【００３１】
ＨＤＤ１４は、プログラム及びデータがあらかじめ記憶されているか、又は通信インタフェース１９を介して外部のネットワーク取り込んだプログラム及びデータが記憶される。
【００３２】
サウンド処理部１５は、ＣＰＵ１１の指示に従ってゲームの背景音や効果音等のサウンドデータを再生するための処理を行い、スピーカ２０へその音声信号を出力する。
【００３３】
画像処理部１６は、ＣＰＵ１１の指示に従って２次元又は３次元グラフィック処理を行い、画像データを生成する。生成された画像データは、表示ディスプレイ２１に出力される。表示ディスプレイ２１ではなく図示しないＴＶの画面に表示する場合には、同期信号を付加したビデオ信号を出力する。
【００３４】
ＢＲ／ＤＶＤ駆動装置１７は、ＣＰＵ１１の指示に従って、セットされたＢＲ／ＤＶＤ／ＣＤ２２からゲームに関連するプログラムやデータを読出し、ＲＡＭ１３へ転送する。また、セットされたＢＲ／ＤＶＤ／ＣＤ２２へプログラムやデータの書き込みをすることも可能である。
【００３５】
入出力インタフェース１８は、コントローラ２３、キーボード２４及びマウス２５とＣＰＵ１１又はＲＡＭ１３との間のデータのやり取りを制御する。コントローラ２３には、ゲームを行う際に操作される方向キーやボタン等を備えている。
【００３６】
通信インタフェース１９は、通信回線を介して外部ネットワークに接続されており、ＣＰＵ１１の指示に従って、外部ネットワークとの間でプログラムやデータのやり取りが可能となっている。
【００３７】
このような構成の攻略法算出装置において、ＣＰＵ１１は、作動時は、まず、ＲＡＭ１３内にプログラム記憶領域、データ記憶領域及びワークエリアを確保し、ＨＤＤ１４又は外部からプログラム及びデータを取り込んで、プログラム記憶領域及びデータ記憶領域に格納する。次いで、このプログラム記憶領域に格納されたプログラムに基づいて、図２に示す処理を実行する。ＣＰＵ１１がプログラムを実行することによって、図３に概略的に示すごとき攻略法算出装置が構築される。
【００３８】
即ち、図３に示すように、本実施形態の攻略法算出装置は、最適政策算出部３０と、行動決定部３１とを備えるように構築される。ここで、最適政策算出部３０はＤＰグラフ作成器３０ａと、ＤＰ実施器３０ｂとを備え、行動決定部３１は行動決定器３１ａと、遷移確率テーブル３１ｂと、利得テーブル３１ｃとを備えるように構築される。
【００３９】
この攻略法算出装置の各部説明を行う前に、本実施形態で用いるマルコフ決定過程（ＭＤＰ）を利用したロールプレイイングゲーム（ＲＰＧ）の数理モデルと、その数理モデルで表現されるＲＰＧの仕様とについて説明する。
【００４０】
まず、本実施形態におけるＲＰＧの仕様について説明する。
【００４１】
プレイヤーはヒットポイント（ＨＰ)と呼ばれる数値を持ち、ＨＰが０となると、次の期にマップ上のスタート位置から再開する。再開時には、ＨＰは、スタート時と同じ最大値Ｍｈｐまで回復する。
【００４２】
ｓｍｉはマップ上の位置を示し、ＳＭ、ＳＭ＝｛ｓｍ１，ｓｍ２，・・・，ｓｍ｜ＳＭ｜｝は、マップ上の位置の集合である。ここで、ゲーム開始時のスタート位置をｓｍ１とする。なお、本実施形態においては、スタート位置及び現在のプレイヤーの位置は、プレイヤーによって既知であるとする。ｆｉは、マップ上の地形の種類を示し、Ｆ、Ｆ＝｛ｆ１，ｆ２，・・・，ｆ｜Ｆ｜｝はマップ上の地形の種類の集合である。マップ上の各位置がどの地形に該当するかは、関数Ｆ（ｓｍｉ）∈Ｆで分かる。
【００４３】
ｅｉは、敵の種類を示し、Ｅ、Ｅ＝｛ｅ１，ｅ２，・・・，ｅ｜Ｅ｜｝は敵の種類の集合である。Ｍ(ｅｉ）は、敵ｅｉの出現時のこの敵ｅｉのＨＰを示す。プレイヤーは、敵を攻撃することによって敵のＨＰを０以下にすると、その敵を倒し、その敵に該当する報酬Ｇ（ｅｉ）を得る。
【００４４】
プレイヤーが選択できる行動（コマンド）は、マップモードと戦闘モードとでは異なり、マップモードではａ１からａ４が選択可能であり、戦闘モードではａ５及びａ６が選択可能である。ａ１，ａ２，ａ３，ａ４は、マップ上でそれぞれ右、左、上、下に移動するための行動である。ｍｖ（ｓｍｉ，ａｊ）はプレイヤーが位置ｓｍｉで行動ａｊを選択した際の移動先位置である。プレイヤーの移動に際して、確率ｐ（ｅｋ｜Ｆ（ｍｖ（ｓｍｉ，ａｊ）），θ＊）で移動先ｍｖ（ｓｍｉ，ａｊ）に敵ｅｋが出現し、戦闘モードになる。敵は同時に複数出現することはなく、確率１−Σｅｋ∈Ｅｐ（ｅｋ｜Ｆ（ｍｖ（ｓｍｉ，ａｊ）），θ＊）で何も出現せずにマップモードが続く。
【００４５】
戦闘モードの行動ａ５はプレイヤーが戦うための行動であり、確率ｐ（Ｃ（ｅｉ）｜ａ５，ｅｉ，θ＊）で敵ｅｉへの攻撃に成功し、その場合、敵ｅｉのＨＰがＣ（ｅｉ）だけ減少する。プレイヤーは、確率１−ｐ（Ｃ（ｅｉ）｜ａ５，ｅｉ，θ＊）で敵ｅｉへの攻撃に失敗する。また、行動ａ５の選択とは直接的に関係しないが、戦闘モードでは敵もプレイヤーに対して攻撃し、確率ｐ（Ｂ（ｅｉ）｜ｅｉ，θ＊）で敵ｅｉがプレイヤーへの攻撃に成功し、その場合、プレイヤーのＨＰがＢ（ｅｉ）だけ減少する。攻撃は、プレイヤーが常に先攻すると仮定する。敵ｅｉは、確率１−ｐ（Ｂ（ｅｉ）｜ｅｉ，θ＊）でプレイヤーへの攻撃に失敗する。行動ａ６は、プレイヤーが敵から逃げるための行動であり、確率ｐ（ｍａｐ｜ａ６，θ＊）でプレイヤーは次の期にマップモードで移動し、確率１−ｐ（ｍａｐ｜ａ６，θ＊）で戦闘モードが続く。行動ａ６を選択した場合にも、敵は攻撃してくる。よって、プレイヤーが逃げることに失敗し、かつ敵が攻撃に成功すると、プレイヤーはダメージを受ける。θ＊は、上述の各確率分布を支配する真のパラメータであり、本実施形態では既知であるとする。
【００４６】
次に、確率システムの動的な最適化問題を定式化する優れた能力を有する数理モデルであるＭＤＰについてその概要を説明する。
【００４７】
ＭＤＰについては、例えば、金子哲夫、「マルコフ決定理論入門」、槙書店（１９７３）や森村英典、高橋幸雄、「マルコフ解析」、日科技連、東京（１９７９）等に記載されている。
【００４８】
ＭＤＰは、状態ｓｉ、ｓｉ∈Ｓ、Ｓ＝｛ｓ１，ｓ２，・・・，ｓ｜Ｓ｜｝（｜Ｓ｜は有限）、各状態で選択できる行動ａｉ、ａｉ∈Ａ、Ａ＝｛ａ１，ａ２，・・・，ａ｜Ａ｜｝（｜Ａ｜は有限）、状態ｓｉで行動ａｊを選択したもとで、状態ｓｋへ遷移する遷移確率ｐ（ｓｋ｜ｓｉ，ａｊ，ξ＊）（ξ＊は遷移確率分布を支配する真のパラメータ）、遷移に伴って発生する利得ｒ（ｓｉ，ａｊ，ｓｋ）で構成される。ＭＤＰの目的は、行動を選び、状態が遷移し、利得を得るという一連のプロセスを繰り返しながら総利得を最大化することである。プロセスの繰り返し回数が有限の場合には、総利得の期待値（期待総利得）を最大化する最適な決定関数を動的計画法（ＤＰ）によって求めることができる。具体的には、真のパラメータξ＊が既知の場合であれば、下記の式（１）を用いて、ｔ期の状態がｓｉという条件下におけるｔ期以降の期待総利得の最大値Ｖ（ｓｉ，ｔ）を逐次的に計算できる。決定関数は、状態と期とを受け取って、その期で選ぶべき行動を返す関数である。
【００４９】
【数１】
2013252247.tif 000003
【００５０】
次に、ＭＤＰと本実施形態におけるＲＰＧとの対応について説明する。
【００５１】
ｘｔは、ＭＤＰにおけるｔ期の状態を示す変数であり、式（２）のように構成される。
【００５２】
ｘｔ＝（ｘｔ，１，ｘｔ，２，ｘｔ，３，ｘｔ，４）      （２）
ただし、ｘｔ，１はｔ期におけるプレイヤーのＨＰ、ｘｔ，２はｔ期におけるプレイヤーのマップ上での位置、ｘｔ，３はｔ期における敵の種類、ｘｔ，４はｔ期における敵のＨＰをそれぞれ示し、マップモードの場合には敵は存在せず、ｘｔ，３-＝ｘｔ，４＝０とする。
【００５３】
Ａ（ｘｔ）は、状態ｘｔにおいて選択可能なＭＤＰの行動集合を示す。ｙｔはＭＤＰにおけるｔ期に選択した行動を示す変数である。
【００５４】
次に、マップモードのｔ期の状態ｘｔで行動ｙｔを選択したときの状態遷移について説明する。ｔ＋１期には、確率ｐ（ｅｉ｜Ｆ（ｍｖ（ｘｔ，２，ｙｔ）），θ＊）で敵ｅｉが出現し、戦闘モードの状態ｘｔ＋１、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｍｖ（ｘｔ，２，ｙｔ），ｅｉ，Ｍ(ｅｉ））      （３）
に遷移する。ただし、ゲームのスタート位置であるｓｍ１が、移動先ｍｖ（ｘｔ，２，ｙｔ）の場合には敵は出現しない（ｐ（ｅｉ｜Ｆ（ｍｖ（ｘｔ，２，ｙｔ）），θ＊）＝０）とする。また、確率１−Σｅｉ∈Ｅｐ（ｅｉ｜Ｆ（ｍｖ（ｘｔ，２，ｙｔ）），θ＊）で敵が出現せずにマップモードの状態ｘｔ＋１に遷移する。このときの状態ｘｔ＋１は、移動先ｍｖ（ｘｔ，２，ｙｔ）がｓｍ１の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（Ｍｈｐ，ｓｍ１，ｘｔ，３，ｘｔ，４）      （４）
移動先ｍｖ（ｘｔ，２，ｙｔ）がｓｍ１以外の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｍｖ（ｘｔ，２，ｙｔ），ｘｔ，３，ｘｔ，４）    （５）
である。式（４）の場合は、プレイヤーがスタート位置ｓｍ１に戻り、ＨＰを最大値Ｍｈｐまで回復した状態である。
【００５５】
次に、戦闘モードのｔ期の状態ｘｔで行動ｙｔを選択したときの状態遷移について、行動ｙｔが行動ａ５（戦う）の場合と行動ａ６（逃げる）の場合とに分けて説明する。
【００５６】
まず、行動ａ５（戦う）の場合について説明する。確率１−ｐ（Ｃ（ｘｔ，３）｜ａ５，ｘｔ，３，θ＊）（１−ｐ（Ｂ（ｘｔ，３）｜ｘｔ，３，θ＊）でプレイヤーと敵との両方が攻撃に失敗し、状態ｘｔ＋１、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｘｔ，２，ｘｔ，３，ｘｔ，４）              （６）
に遷移する。確率（１−ｐ（Ｃ（ｘｔ，３）｜ａ５，ｘｔ，３，θ＊））ｐ（Ｂ（ｘｔ，３）｜ｘｔ，３，θ＊）でプレイヤーは攻撃に失敗し、敵は攻撃に成功し、状態ｘｔ＋１へ遷移する。
このときの状態ｘｔ＋１は、ｘｔ，１＞Ｂ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１−Ｂ（ｘｔ，３），ｘｔ，２，ｘｔ，３，ｘｔ，４）  （７）
で、ｘｔ，１≦Ｂ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（Ｍｈｐ，ｓｍ１，０，０）                            （８）
である。式（８）の場合には、プレイヤーが敵に倒されて、ゲームのスタート位置ｓｍ１からの再開である。確率ｐ（Ｃ（ｘｔ，３）｜ａ５，ｘｔ，３，θ＊）（１−ｐ（Ｂ（ｘｔ，３）｜ｘｔ，３，θ＊））でプレイヤーは攻撃に成功し、敵は攻撃に失敗し、状態ｘｔ＋１へ遷移する。このときの状態ｘｔ＋１は、ｘｔ，４＞Ｃ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｘｔ，２，ｘｔ，３，ｘｔ，４−Ｃ（ｘｔ，３））  （９）
で、ｘｔ，４≦Ｃ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｘｔ，２，０，０）              （１０）
である。式（１０）の場合には、敵ｘｔ，３を倒すことに成功しているので、この状態遷移に伴い、利得ｒ（ｘｔ，ａ５，ｘｔ＋１）＝Ｇ（ｘｔ，３）を得る。確率ｐ（Ｃ（ｘｔ，３）｜ａ５，ｘｔ，３，θ＊）ｐ（Ｂ（ｘｔ，３）｜ｘｔ，３，θ＊）でプレイヤーと敵の両方が攻撃に成功し、状態ｘｔ＋１へ遷移する。このときの状態ｘｔ＋１は、ｘｔ，４≦Ｃ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｘｔ，２，０，０）                    （１１）
で、ｘｔ，４＞Ｃ（ｘｔ，３）かつｘｔ，１＞Ｂ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１−Ｂ（ｘｔ，３），ｘｔ，２，ｘｔ，３，ｘｔ，４−Ｃ（ｘｔ，３））                              （１２）
で、ｘｔ，４＞Ｃ（ｘｔ，３）かつｘｔ，１≦Ｂ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（Ｍｈｐ，ｓｍ１，０，０）          （１３）
である。式（１１）の場合には、敵ｘｔ，３を倒すことに成功しているので、この状態遷移に伴い、利得ｒ（ｘｔ，ａ５，ｘｔ＋１）＝Ｇ（ｘｔ，３）を得る。式（１３）の場合はプレイヤーが敵に倒されて、ゲームのスタート位置ｓｍ１からの再開である。
【００５７】
次に、戦闘モードのｔ期の状態ｘｔで行動ａ６（逃げる）を選択したときの状態遷移について説明する。確率ｐ（ｍａｐ｜ａ６，θ＊）でプレイヤーが逃げることに成功し、状態ｘｔ＋１、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｘｔ，２，０，０）          （１４）
に遷移する。確率１−ｐ（ｍａｐ｜ａ６，θ＊）（１−ｐ（Ｂ（ｘｔ，３）｜ｘｔ，３，θ＊））でプレイヤーが逃げることに失敗し、敵が攻撃に失敗し、状態ｘｔ＋１、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１，ｘｔ，２，ｘｔ，３，ｘｔ，４）    （１５）
に遷移する。確率（１−ｐ（ｍａｐ｜ａ６，θ＊））ｐ（Ｂ（ｘｔ，３）｜ｘｔ，３，θ＊）でプレイヤーが逃げることに失敗し、敵が攻撃に成功し、状態ｘｔ＋１へ遷移する。このときの状態ｘｔ＋１は、ｘｔ，１＞Ｂ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（ｘｔ，１−Ｂ（ｘｔ，３），ｘｔ，２，ｘｔ，３，ｘｔ，４）（１６）
で、ｘｔ，１≦Ｂ（ｘｔ，３）の場合には、
ｘｔ＋１＝（ｘｔ＋１，１，ｘｔ＋１，２，ｘｔ＋１，３，ｘｔ＋１，４）
＝（Ｍｈｐ，ｓｍ１，０，０）                          （１７）
である。式（１７）の場合には、プレイヤーが敵に倒されて、ゲームのスタート位置ｓｍ１からの再開である。
【００５８】
前述した通り、プレイヤーが敵ｘｔ，３を倒した状態遷移に伴う利得は、ｒ（ｘｔ，ａ５，ｘｔ＋１）＝Ｇ（ｘｔ，３）である。その他の状態遷移に伴う利得は、ｒ（ｘｔ，ａ５，ｘｔ＋１）＝０である。本実施形態では、初期状態ｘ１がｘ１＝（Ｍｈｐ，ｓｍ１，０，０）であり、各期の状態は観測可能である。また、プレイヤーや敵の攻撃力Ｃ（ｅｉ），Ｂ（ｅｉ）及び敵を倒したときの報酬Ｇ（ｅｉ）等は全て既知であるとする。このもとで、Ｔ期間のプレイを行って総利得
【数２】
2013252247.tif 000004
の最大化を目的とする。
【００５９】
次に、図２に示されたフローチャート、図３に示されたブロック図、図４に示された図、及び図５に示されたフローチャートを参照して、本実施形態の攻略法算出装置の動作を説明する。
【００６０】
図２及び図３に示すように、まず、構築された最適政策算出部３０におけるＤＰグラフ作成器３０ａにプレイヤーの初期状態ｘ１と制御期間長Ｔとが入力される（ステップＳ１）。この初期状態ｘ１と制御期間長ＴとはＨＤＤ１４に格納されているデフォルト値又は前回のプレイ結果値をＲＡＭ１３のデータ記憶領域に格納したものであっても良いし、キーボード２４から入力した値であっても良い。
【００６１】
プレイヤーの初期状態ｘ１と制御期間長Ｔとが入力されると、ＤＰグラフ作成器３０ａは、Ｔ期間の期待総利得を最大化するための動的計画法（ＤＰ）の問題を解くためのＤＰグラフを作成する（ステップＳ２）。例えば、想定されるプレイヤーの全状態を要素とする状態集合Ｓが、Ｓ＝｛ｓ１，ｓ２，ｓ３，ｓ４｝でｘ１＝ｓ１の場合であれば、図４のようなＤＰグラフが作成される。これは、１時点目（１期）はプレイヤーの初期状態で表現され、２時点目からＴ時点目まではプレイヤーの想定される各状態で表現されたグラフにおいて、末端のＴ時点目（Ｔ期）のノードから遡りながらＤＰでＴ期間のＭＤＰ問題を解くことによって、Ｔ期間の期待総利得を最大化する最適政策を求めるための準備である。
【００６２】
次いで、ＤＰ実施器３０ｂがＤＰによってＴ期間のＭＤＰ問題を解くことによって、Ｔ期間の期待総利得を最大化する最適政策が求められる（ステップＳ３）。ＤＰ実施器３０ｂは、ＤＰグラフの末端の各ノードから順にそのノードでの最適な行動（ＲＰＧにおけるプレイヤーのコマンド選択）とそのノード以降の期待総利得の最大値を、行動決定部３１における行動決定器３１ａと連携して求める（ステップＳ４）。
【００６３】
即ち、各ノード毎にそのノードの時点ｔ（何時点目かを示す自然数）とプレイヤーの状態ｘｔ（ｔ時点目のプレイヤーの状態）とを行動決定器３１ａへ送ると、そのノードにおける最適な行動とそのノード以降の期待総利得の最大値とが求められて行動決定器３１ａから送り返される。
【００６４】
その後、ＤＰグラフの１時点目のノードまで全て解き終わったかどうかが判断され（ステップＳ５）、解き終わっていればＤＰグラフの全ノードにおける最適な行動とそのノード以降の期待総利得の最大値が最適政策として出力される（ステップＳ６）。
【００６５】
次に、図３及び図５に示されたフローチャートを参照して行動決定部３１の動作、即ち図２におけるステップＳ４の動作を説明する。
【００６６】
まず、最適政策算出部３０のＤＰ実施器３０ｂから行動決定部３１の行動決定器３１ａへ、時点ｔ（何時点目かを示す自然数）とプレイヤーの状態ｘｔ（ｔ時点目のプレイヤーの状態）とが入力される（ステップＳ４１）。
【００６７】
次いで、入力された時点ｔとプレイヤーの状態ｘｔとに応じてそのノード以降の期待総利得の最大値とそのノードにおける最適な行動とが算出される（ステップＳ４２）。ｔ＝Ｔの場合には、式（１８）で、そのノード以降の期待総利得の最大値が求められる。
【００６８】
【数３】
2013252247.tif 000005
ただし、Ｖ（ｘＴ，Ｔ）はＴ時点目の状態ｘＴから時点Ｔ＋１への状態遷移に伴う最後の１期間の期待総利得の最大値である。ｐ（ｘＴ＋１｜ｘＴ，ｙＴ，θ＊）は遷移確率テーブル３１ｂから読み取ったものである。ｒ（ｘＴ，ｙＴ，ｘＴ＋１）は利得テーブル３１ｃから読み取ったものである。１≦ｔ≦Ｔ−１の場合には次の式（１９）でそのノード以降の期待総利得の最大値が求められる。
【００６９】
【数４】
2013252247.tif 000006
ただし、Ｖ（ｘＴ，Ｔ）はｔ時点目の状態がｘｔという条件のもとでの、ｔ時点以降の期待総利得の最大値である。本実施形態ではＤＰを利用しているので、このように部分最適解を再利用している。ｔ＝Ｔの場合には次の式（２０）でそのノードにおける最適な行動が求められる。
【００７０】
【数５】
2013252247.tif 000007
ただし、ｄ＊（ｘＴ，Ｔ）はＴ時点目の状態ｘＴにおいて選択すべき最適な行動である。１≦ｔ≦Ｔ−１の場合には次の式（２１）でそのノードにおける最適な行動が求められる。
【００７１】
【数６】
2013252247.tif 000008
ただし、ｄ＊（ｘｔ，ｔ）はｔ時点目の状態ｘｔにおいて選択すべき最適な行動である。
【００７２】
その後、そのノードにおける最適な行動とそのノード以降の期待総利得の最大値が最適政策算出部３０のＤＰ実施器３０ｂへ出力され（ステップＳ４３）、前述の最適政策が出力されるのである。
【００７３】
以上説明したように、第１の実施形態によれば、ＤＰを用いて各時点のプレイヤーの各状態において、その時点以降の期待総利得を最大化し、最終的に制御期間における期待総利得を最大にすることが保証された政策が出力されるので、プレイヤーの初期状態と制御期間長とに対して制御期間における期待総利得を最大にする政策を出力することが可能となり、そのＲＰＧに関する攻略法（行動選択の仕方）を算出することができる。
【００７４】
即ち、本実施形態によれば、攻略法をコンピュータにシミュレーションさせることによって、被験者の体験データを取得することができる。例えば、プレイヤーのゲーム結果をシミュレーションすることによって、マップ上に隠されたアイテムやイベントに遭遇する割合等を把握でき、その割合を見ながら適切な隠し場所を設定する等のゲーム開発支援を行うことができる。また、算出される数理工学的に最適な攻略法と実際のプレイヤーによる攻略法との比較を行うことにより、人間が楽しいと感じるゲーム要素を工学的に把握することができる。人間が楽しいと感じるゲーム要素を確率モデル上のパラメータ設定のある種のパターンとして把握できれば、そのような要素を多く含むゲーム開発を行うことができる。また、種々の目的毎の攻略法を算出することによって、各目的に適したプレイヤーに協力するキャラクタの攻略法を容易にプログラミングすることが可能となる。
【００７５】
次に、各種確率分布を支配する真のパラメータθ＊が未知である、本発明を拡張した第２の実施形態について説明する。
【００７６】
本実施形態における攻略法算出装置の構成は基本的には、第１の実施形態の場合と同様であり、従ってその構成の説明は省略する。
【００７７】
真のパラメータ未知の場合を説明するために、いくつかの新たな定義を行う。ｐ（θ）はパラメータθの事前分布であり、既知であるとする。Θはパラメータ空間であり、θ＊∈Θ、θ∈Θである。ｘｔｙｔ−１はｔ期目の状態ｘｔに至るまでの遷移系列であり、ｘｔｙｔ−１＝ｘ１ｙ１・・・ｘｔである。
【００７８】
真のパラメータ既知の場合には、ＤＰでＴ時点から遡りながら各時点の各状態に対して行動選択を行うが、真のパラメータ未知の場合には、ＤＰでＴ時点から遡りながら各時点の各状態と１時点からその時点に至るまでの各遷移系列の組に対して行動選択を行う。
【００７９】
Ｔ時点目の状態ｘＴ（全ての状態の候補）と遷移系列ｘＴｙＴ−１（全ての遷移系列の候補）の組に対する処理は以下の通りである。
【００８０】
【数７】
2013252247.tif 000009
ただし、ｐ（θ｜ｘＴｙＴ−１）は１時点からＴ時点に遷移系列ｘＴｙＴ−１のように遷移した場合の事後分布である。
【００８１】
ｔ時点目（１≦ｔ≦Ｔ−１）の状態ｘｔ（全ての状態の候補）と遷移系列ｘｔｙｔ−１（全ての遷移系列の候補）の組に対する処理は以下の通りである。
【００８２】
【数８】
2013252247.tif 000010
式（２２）から式（２５）を用いてｄ＊Ｂ（ｘ１，ｘ１，１）まで求めることによって、１時点目からＴ時点目までの全ての状態と遷移系列の組とに対して、ベイズ基準のもとで総利得を最大にするという点で最適な行動選択の仕方を求めることができる。
【００８３】
式（２２）から式（２５）には積分計算が含まれており、一般的に、積分計算は計算量が多いが、二項分布（敵の出現以外の確率分布）の事前分布としてベータ分布を、多項分布（敵の出現の確率分布）の事前分布としてディリクレ分布をそれぞれ仮定すると、積分計算は四則演算で実施することができる（Ｍａｔｓｕｓｈｉｍａ，Ｔ．，Ｈｉｒａｓａｗａ，Ｓ．，Ａ  Ｂａｙｅｓ  ｃｏｄｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｍａｒｋｏｖ  ｍｏｄｅｌｓ，ＴＥＣＨＮＩＣＡＬ  ＲＥＰＯＲＴ  ＯＦ  ＩＥＩＣＥ，ＩＴ９５−１，ｐｐ．１−６（１９９５））。四則演算の一例として、マップモードのｔ期の状態ｘｔにおいて行動ｙｔを選択したもとで、敵ｅｉが出現し、戦闘モードの状態ｘｔ＋１に遷移する場合の
【数９】
2013252247.tif 000011
の計算を以下に示す。
【００８４】
【数１０】
2013252247.tif 000012
ここで、Ｎ（Ｆ（ｍｖ（ｘｔ，２，ｙｔ）），ｅｉ｜ｘｔｙｔ−１）は系列ｘｔｙｔ−１中で地形の種類がＦ（ｍｖ（ｘｔ，２，ｙｔ））の位置で敵ｅｉが出現した回数、α（ｅｉ｜Ｆ（ｍｖ（ｘｔ，２，ｙｔ）））はｐ（ｅｉ｜Ｆ（ｍｖ（ｘｔ，２，ｙｔ）），θ）に対するディリクレ分布（事前分布）のパラメータ、α（ｍｖ（ｘｔ，２，ｙｔ）｜Ｆ（ｍｖ（ｘｔ，２，ｙｔ）））は
【数１１】
2013252247.tif 000013
に対するディリクレ分布（事前分布）のパラメータを示す。このように、事前分布としてディリクレ分布やベータ分布を採用することにより、積分計算を四則演算で置き換えることができる。ディリクレ分布やベータ分布のパラメータの設定が事前分布の設定に相当するが、事前に何も情報が無い場合の設定の仕方についてはベイズ統計学やその応用分野で種々の方法が研究されている。多くの分野で良好な性質が報告されているジェフリーズの事前分布が有名であり、本実施形態に適用する場合は、各パラメータを０．５に設定することに相当する。例えば、Ｂｅｒｇｅｒ，Ｊ．Ｏ．，Ｓｔａｔｉｓｔｉｃａｌ  Ｄｅｃｉｓｉｏｎ  Ｔｈｅｏｒｙ  ａｎｄ  Ｂａｙｅｓｉａｎ  Ａｎａｌｙｓｉｓ，Ｓｐｒｉｎｇ−Ｖｅｒｌａｇ，Ｎｅｗ  Ｙｏｒｋ（１９８０）、繁桝算男，ベイズ統計入門，東京大学出版会（１９８５）、Ｍａｔｓｕｓｈｉｍａ，Ｔ．，Ｈｉｒａｓａｗａ，Ｓ．，Ａ  Ｂａｙｅｓ  ｃｏｄｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｍａｒｋｏｖ  ｍｏｄｅｌｓ，ＴＥＣＨＮＩＣＡＬ  ＲＥＰＯＲＴ  ＯＦ  ＩＥＩＣＥ，ＩＴ９５−１，ｐｐ．１−６（１９９５）、鈴木譲，ベイシアネットワーク入門，培風館，東京（２００９）を参照。事前分布にディリクレ分布やベータ分布を採用してジェフリーズの事前分布に設定し、式（２２）から式（２５）で処理することにより、真のパラメータ未知の場合にベイズ基準のもとで総利得を最大化することができる。
【００８５】
以上の説明では、真のパラメータ未知の場合のベイズ最適な行動選択の仕方を求めるアルゴリズムについて述べた。事前分布としてディリクレ分布やベータ分布を採用することにより、積分計算を四則演算に置き換えた。しかしながら、ベイズ最適な行動選択の仕方を求めるためには、多大な計算量が必要となる。真のパラメータ既知の場合には、ＤＰの各時点毎に式（１９）の処理を状態数分だけ実施すればよい。一方、真のパラメータ未知のベイズ最適の場合には、ＤＰの各時点毎に式（２５）の処理を状態数と遷移系列の個数との積分だけ実施する必要があり、処理の回数は時点の数（ｔ期のｔ）に対する指数オーダとなる。
【００８６】
そこで、本実施形態の望ましい態様として、真のパラメータ未知の場合に近似を行う例を説明する。ここで、学習データＬを新たに導入する。学習データは過去のゲームのプレイデータである遷移系列の集合であったり、敵の出現確率などの個々の確率分布について真のパラメータの分布から発生させたサンプルデータであったり、種々の形態が適用可能である。
【００８７】
前述したベイズ最適な方法では、各時点毎にその時点までの遷移系列ｘｔｙｔ−１に対する事後分布によって、
【数１２】
2013252247.tif 000014
を計算したが、近似アルゴリズムでは、時点に関係なく学習データＬによる事後分布を用いて
【数１３】
2013252247.tif 000015
を計算する。具体的には、
【数１４】
2013252247.tif 000016
を真のパラメータ既知の場合の式（１８）から式（２１）に代入して行動選択の仕方を求める。
【００８８】
近似アルゴリズムにより、ＤＰの処理の回数は真のパラメータ既知の場合と同じ回数に軽減することができる。有限の学習データに対する理論的な精度保証はないが、漸近的には学習データによる事後分布を用いた推定値が真のパラメータに収束するので、求める行動選択の仕方も真のパラメータ既知の場合に収束する。
【実施例】
【００８９】
真のパラメータθ＊が既知の場合の行動選択の仕方を求めるアルゴリズムに関する第１の実施形態について実験を行った実施例を説明する。図６にこの実施例におけるマップを示す。実験結果が理解しやすいように９マスからなる小規模のマップとした。以下の表１〜表５は地形の設定、確率の設定及びその他の設定を示している。
【００９０】
【表１】
2013252247.tif 000017
【００９１】
【表２】
2013252247.tif 000018
【００９２】
【表３】
2013252247.tif 000019
【００９３】
【表４】
2013252247.tif 000020
【００９４】
【表５】
2013252247.tif 000021
【００９５】
以上の設定で、真のパラメータ既知の場合のアルゴリズムを適用して、１０期間の期待総利得を最大化するための各期における行動選択の仕方を求めた。
【００９６】
結果の一部について述べると、例えば、時点３（３期）でプレイヤーのＨＰが６であり位置ｓｍ４にいるマップモードの状態では、最適の行動選択はａ３という上のマスｓｍ７への移動であった。これは、プレイヤーのＨＰにまだ余裕があるので、弱くて報酬の小さい敵が出現する右（ａ１）やＨＰを回復する下（ａ４）ではなく、強くて報酬の大きい敵が出現する上（ａ３）への移動を選択しているのである。他方、同じ時点３（３期）のマップモードであってもＨＰが１であり位置ｓｍ４にいる状態では、行動ａ４を選択して下のＨＰを回復してくれるスタート位置ｓｍ１へ移動した。これは、プレイヤーのＨＰに余裕がないので回復するための行動選択である。また、時点９（９期）にＨＰが１であり位置ｓｍ４にいるマップモードの状態では、行動ａ１を選択して、弱くて報酬の小さい敵が出現する右のｓｍ５へ移動した。これは、プレイヤーのＨＰに余裕はないが、残りの期間にも余裕がないため、弱い敵が出現するｓｍ５への移動を選択しているのである。
【００９７】
このように、真のパラメータ既知の場合のアルゴリズムを適用することにより、開発者であれば知っている真のパラメータの情報を利用して対象期間の期待総利得を最大にする行動選択の仕方を求めることができる。
【００９８】
次に、真のパラメータが未知の場合の行動選択の仕方を求めるアルゴリズムに関する第２の実施形態について実験を行った実施例を説明する。真のパラメータ既知の場合の実施例と同じ設定のもとで、真のパラメータ未知の場合の近似アルゴリズムを適用した。学習データとして、各確率分布毎にサンプルデータを発生させた。そのもとで、近似アルゴリズムを適用し、各時点の各状態における行動選択が真のパラメータ既知の場合と比較して一致するかどうか調べた。各確率分布の学習データ数を１０、１００、１０００と変化させ、それぞれの学習データ数に対して１００パターンの学習データを発生させて適用実験を行った。真のパラメータ既知の場合の行動選択との一致率は１００パターンの平均で、学習データ数が１０の場合で約８８％、学習データ数が１００の場合で約９４％、学習データ数が１０００の場合で約９６％であった。
【００９９】
このように、学習データによる事後分布を利用する近似アルゴリズムを用いることにより、真のパラメータが未知の場合でも、ＤＰに必要な計算量を、真のパラメータ既知の場合の計算量と同程度とすることができる。また、少ない実験例ではあるが、学習データの増加に伴い真のパラメータ既知の場合との行動選択の一致率が高くなることが確認できた。
【０１００】
以上述べた実施形態は全て本発明を例示的に示すものであって限定的に示すものではなく、本発明は他の種々の変形態様及び変更態様で実施することができる。従って本発明の範囲は特許請求の範囲及びその均等範囲によってのみ規定されるものである。
【符号の説明】
【０１０１】
１０  バス
１１  ＣＰＵ
１２  ＲＯＭ
１３  ＲＡＭ
１４  ＨＤＤ
１５  サウンド処理部
１６  画像処理部
１７  ＢＲ／ＤＶＤ駆動装置
１８  入出力インタフェース
１９  通信インタフェース
２０  スピーカ
２１  表示ディスプレイ
２２  ＢＲ／ＤＶＤ／ＣＤ
２３  コントローラ
２４  キーボード
２５  マウス
３０  最適政策算出部
３０ａ  ＤＰグラフ作成器
３０ｂ  ＤＰ実施器
３１  行動決定部
３１ａ  行動決定器
３１ｂ  遷移確率テーブル
３１ｃ  利得テーブル
【図１】
2013252247.tif 000022
【図２】
2013252247.tif 000023
【図３】
2013252247.tif 000024
【図４】
2013252247.tif 000025
【図５】
2013252247.tif 000026
【図６】
2013252247.tif 000027