こんにちは。いつもお世話になっています。

いまパックマンのようなゲームを作ってまして敵のキャラのAIのようなものを作っています。  
その際にアイテムを取る最短経路を求めることはできるのですがそうではなくただ最短を求めないで効率の良いと自分の思いついた作りたいプログラムの書き方がわからなくて質問しました。

前提として、ルールとして

  * 勝利条件は点数制でアイテムの種類は５点のものと１０点の物があります。
  * ひとつ移動するごとに’１’コストが減ります移動は上下左右のみ。
  * 通れないとことして岩が置いてあります。
  * そしてトラップとしてそこから何処かへ移動してしまうワープがあります。(どこに飛んだかはそこからどれくらい移動したか値が渡されます。)

本題の自分で書きたいプログラムの戦略はその時の(計算回数的な理由で)5コスト以内で一番多い得点を得るプログラムを書きたいのです。ぜひご教授お願いします。

言語はC++です。  
敵キャラクターは配列上にマップを作って計算してます。
CC BY-SA 3.0
2015-08-02T13:26:35.100
12953
2015-08-03T07:32:09.250
2015-08-02T13:48:37.993
10330
10760
question
c++ アルゴリズム c++11 c++-cli
経路長を求めポイントを多く稼ぐ方法
どんなゲームであれ、AIを実装するときの考え方は基本的には同じです。あらゆる手順によるすべての可能性を探索し、それぞれの可能性について得点を計算して、最も点数の高い手順を選びます。そのパックマンみたいなゲームであれば、なんの障害物もないだだっ広い部屋として、`上下左右4通り
** 5回 =
1024通り`の動きの可能性がありますが、それらすべてについて得点を計算して、最も得点の高い動きを選びます。実際には壁があるので4通り全てには動けず、もう少し分岐は減るでしょう。

ランダムなワープなど確率的な事象がある場合は、期待値を計算するだけです。ギャンブルでもすべての期待値を計算できれば最適解が求まります(繰り返せば必ず負けることがわかるだけですが)。また、ゲームの状況はプレイヤーの操作によって変化しますが、相手プレイヤーの動きが不確定なゲームでは、戦略は[ミニマックス法](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95)などとしてよく研究されています(この「戦略」は現実のゲームにおいては必ずしも万人が最適な戦略だと意見が一致するものではないでしょうが、客観的に定義できるので研究対象としては妥当です)。

ただし、 **このような最適解を求めることがそのゲームのAIに必要かどうかは大いに疑問**
です。最適解の探索が必要なのはチェスや将棋などの一部のゲームに限られます。

というのは、例えばRPGで敵キャラクターがこのような最適の戦略を取ると、どのモンスターもそのモンスターが持つ最強の技や魔法だけを最初からMPが切れるまでひたすらぶっ放してくるという単調な動きになり、決して面白いゲームにはなりません。また、常に最適解を取るAIはプレイヤーに行動を読まれるので、必ずしも最強とも限りません。敵の動きに意外性を加えたければ動きにランダム性を加えるしかありませんが、そうすると最適解を計算した意味が薄れます。

実のところ、パックマンでも分かれ道に来たらランダムに進路を変えるというような単純なAIでもゲームデザイン次第で面白いものになりますし、意外に人間が動かしているかのように見えるものです。ゲームを難しくしたいのなら、強いAIを作るより、RPGなら敵のHPを増やしたり、パックマンなら敵の動きを早くしたり敵の数を増やすなどしたほうが難易度の調整をしやすいでしょう。

  * まとめ：最適なAIを作っても、頑張った割にゲームは面白くならないでしょう。

# 追記

そもそもゲーム木の実装ができないということなら、まずとにかく単純なルールでゲーム木の実装の仕方を学ぶのがいいでしょう

  * アイテムは1点のもののみ
  * 移動は左右のみ、2回まで
  * マップは長さ5の一次元。障害物なし
  * スタート位置は2(なのでマップの端にはぶつからない)
  * ワープなし

現在の状態を

```

    var state = {
        map: [0, 0, 0, 1, 1],  // 1のところにはアイテムが1個おいてある
        playerPosition: 2
    };
    
```

として、

```

    var moves = [
        { move: ["L", "L"], point: 0 },   // 左に2回移動するとアイテムは0
        { move: ["L", "R"], point: 0 },   // 左に行ってから右に行くとアイテムは0
        { move: ["R", "L"], point: 1 },   // 右に行ってから左に移動すればアイテムを1個
        { move: ["R", "R"], point: 2 }    // 右に2回移動すればアイテムを2個
    ];
    
```

というようなすべての可能性を探索し得点を計算します(この擬似コードはJavaScriptです)。`moves`が計算できたら、最も`point`が大きいのは最後の`{
move: ["R", "R"], point: 2 }`なので、その最初の手順である`"R"`(右に移動)を選びます。
CC BY-SA 3.0
2015-08-02T15:31:44.483
12956
2015-08-03T07:32:09.250
2015-08-03T07:32:09.250
10330
10330
12953
answer