おちゃめくらぶ掲示板 - 1659321896

2050：御茶目菜子：2014/05/07(水) 23:38:27: 対戦型ゲームの思考ルーチンの作り方
昨日は私がプチコンで作った卓球ゲームの当たり判定にちょっとした問題が見つかっため
思考ルーチンをどのように作るかという部分で頓挫しているということについて書いたにょ。
思考ルーチン（言い換えればコンピュータ側のAI）は2人対戦型のゲームや多人数でプレイ
できるゲームを作る際にすべて人間同士での対戦を行うのではなければ必要不可欠なものと
なっているにょ。
つまり、対戦型のゲームを1人で遊べるようにするためにはコンピュータの思考ルーチンは
必要になってくるということにょ。
こんなことはあえて言うまでもなく当たり前のことだけどやはり思考ルーチンを作ってみたい
と思う人もいると思うので私の過去の経験などを元に簡単に書いてみることにしたにょ。

まず、思考ルーチンを作るにあたって考えなくてはならないのは下記の2つにょ。

　(1)思考型ゲーム
　(2)リアルタイム型ゲーム

(1)これは将棋、オセロ、麻雀などのテーブルゲームや一般的な戦略シミュレーション
ゲームを示すにょ。
これらのゲームでは自分と相手のターンが分かれており自分のターンの間は思考に専念が
できるにょ。
そのため60fpsで動作しているからといって1フレーム（1/60秒）で思考をを完了させる必要は
ないにょ。

(2)これは対戦型の格闘ゲーム、アクションゲーム、スポーツゲームなどのリアルタイム性が
高いゲーム全般を示すにょ。
基本的にこれらのゲームでは1フレームの間に思考を完了する必要があるにょ。
60fpsで動作するゲームの場合は思考ルーチンは1/60秒以内に止めておく必要があるという
ことにょ。

これ以外にも(1)(2)の中間に位置するリアルタイムストラテジーのようにリアルタイム性は
あるものの1フレームで思考を完了させる必要ないものがあるにょ。（要するにアクション
ゲームほどのリアルタイム性はないけどターンが分かれてないため思考時間にある程度の
制限が出てくるゲーム）
(2)も1フレームで完了するとは限らないのだけどここでは(2)は1フレームで思考が完了、
(1)はターン制で思考時間に特に大きな制限はないという条件で考えてみるにょ。

まずは、思考ルーチンの花形ともいえる思考型ゲームについて見てみるにょ。
ここで考える必要があるのは作ろうとしているゲームが「二人零和有限確定完全情報ゲーム」
か否かということにょ。
これは2人で対戦し、勝利条件が明確に決まっていて、パターン数が有限ですべての情報が
開示されているゲームのことにょ。
具体的な例を挙げれば将棋、オセロなどが相当するにょ。（盤面などですべての情報が公開
されていて運が絡む余地はない）
完全情報ゲームに対して不完全情報ゲームというものも存在するにょ。
それは山札や（相手に見えない）手札やサイコロを使いすべての情報が開示されてない
ゲームのことでポーカーなどの多くのトランプゲーム、麻雀、人生ゲームなどのボード
ゲームがこれに該当するにょ。
不完全情報ゲームについては不確定な情報も多いため完全な思考ルーチンを作ることは
できないけれど逆に言えば不確定であるからこそインチキも可能になるにょ。
例えば麻雀だとCOM側は積み込みをやってあがりまくるキャラや天和（テンホー）をしまくる
最強のキャラを作ることが可能になるにょ。（サイコロやルーレットを使うゲームならば
COM側は常に有利な目が出るようにするという感じで強キャラを演出できる）
そこまでのあからさまな操作を行うインチキ（イカサマ）ではなく本来は見えない相手の
手牌の情報などを取得して思考する（人間で言えば透視能力に近いもの）というインチキは
簡単に可能になるにょ。
したがって、そういうインチキ技がアリかナシかもあらかじめ考えておく必要があるにょ。

完全情報ゲームである将棋やオセロだとそういうインチキ技は使えないにょ。
しかし、完全情報ゲームはほとんどのものは有限回で終了するため十分な速さのCPUとメモリを
搭載したコンピュータがあれば無敗の思考ルーチンを作ることが可能になるにょ。
「チェスなんてただの○×（マルバツ）ゲーム」という白ちゃんのありがたいお言葉もある
くらいだからね。
チェスは将棋のように相手から取った駒を自軍の駒として活用できないため全局面数は
将棋がおよそ10の220乗通りに対して、チェスは10の120乗通りと少ないにょ。
しかし、それはあくまで将棋と比べて少ないというだけで10の120乗通りを素直にすべて
考えていたら現在のコンピュータではとても現実的な時間の間に思考を完了させることは
できないにょ。

実際のゲームではすべての局面を想定して思考する必要なんてないにょ。
あからさまに悪手であるものはそこから先を考慮する必要はないからね。
それはαβ法やミニマックス法を使えば思考ルーチンに実装することができるにょ。
そのためにはその手が良い手か悪い手かを示す評価関数が必要になってくるにょ。
私は将棋ゲームを作った経験がないし、将棋もあまり強くないので説明が上手くできない
けどオセロならば評価関数を作るのは比較的簡単にょ。

　9 1 8 6 6 8 1 9
　1 1 7 3 3 7 1 1
　8 7 5 5 5 5 7 8
　6 3 5 0 0 5 3 6
　6 3 5 0 0 5 3 6
　8 7 5 5 5 5 7 8
　1 1 7 3 3 7 1 1
　9 1 8 6 6 8 1 9

このように盤面に0～9点までの評価点のテーブルを用意することでどこに置くのが有利、不利
かをコンピュータに理解させることができるにょ。
ただし、これは序盤のみ有効な評価点であり、中盤以降は隅を取ることにそこまでの
価値はなくなるにょ。（あくまでこの評価点テーブルは単なる一例にすぎない）
また、オセロの場合は中割を行い「自分が置ける場所を増やし相手の置ける場所を減らす
場所に置く」というのが序盤から中盤にかけての最も有力な戦略となるにょ。
それを知っておくと「隅を取れば有利になる」とか「（序盤であっても）たくさんひっくり
返せる場所に置く方が有利」といった知識しかない初心者相手ならば余裕で勝つことが
できるにょ。（むしろ、序盤は自分の石を増やさない方が有利なくらいなので真逆であり
私が昔ポケコンPC-1350で作ったオセロゲームの思考ルーチンは速度の都合で上記のような
評価点のテーブルのみというシンプルなものだったけどそれでも友人がPC-88で作った
自分が獲得できる石の数が多い所に置くようにしたプログラム相手に完勝した）
そこで上記のような評価点とそこに打った時に相手の置ける場所がどれだけなのかを点数化
したものをミックスさせてその上で評価点を出せば初級者相手ならいい勝負ができる思考
ルーチンができるにょ。
そして、上記のαβ法を用いて数手先読みさせたり、終盤の数手は最終局面までを読み取る
ことで最善手を打つようにすれば中級者（級位者）相手でもそれなりに戦える思考ルーチンが
できるにょ。
中級者相手に勝てるレベルや上級者（段位者）にそれなりに戦えるレベルの思考ルーチンで
あれば定石を覚えさせる必要があるにょ。

オセロの全局面数は約10の60乗通りであるためαβ法を用いれば完全解析も射程に入っている
わけだし、人間対コンピュータの対戦では1997年の時点ですでにコンピュータは世界
チャンピオンを完全に凌駕しているにょ。
さすがに将棋は全局面数が多くまだまだ人間（プロ棋士）には及ばないという印象だったけど
昨年行われた第2回将棋電王戦、今年行われた第3回将棋電王戦を見るともうプロ棋士との
間にはそれほどの力の差はなくなっているように思えるにょ。
さすがにまだトッププロほどの力はないけどそれはマシンスペックの向上とアルゴリズムの
改良で恐らく近い将来にはトッププロを負かす日が来ると思われるにょ。（囲碁に関しては
全局面数は10の360乗程度であるためまだまだプロの足下にも及ばない）

プチコンで既存の完全情報ゲームを再現するならばオセロくらいが最もハードルが低くて
良いのではないかと思われるにょ。（ポピュラーであるため定石や戦略を書いた本やWeb
サイトも多いし）
オセロよりもさらにハードルが低いものと言えば○×ゲーム（三目並べ）があるにょ。
これはルールを知らない人は居ないくらい単純なものであり、思考ルーチンは至って簡単に
できるにょ。
○×ゲームはお互いが最善手を打てば引き分けになってしまうゲームなので強い思考
ルーチンを作れば人間に対して無敗になるにょ。（○×ゲームは初手に対してどのような
2手目を置くかでほぼ勝敗が決まる）
どんなゲームであってもそのルールをある程度熟知しておいて、「自分だったらこの場合は
どのような選択肢を取る」というのが論理的に説明できるようになれば思考ルーチンを
作ること自体はそれほど難しいことではないにょ。

次はリアルタイム型ゲームの思考ルーチンについて考えてみるにょ。
これは思考型ゲームと同じく自分がコンピュータの立場になって考えれば簡単にょ。
ただし、1フレームで完結するようにしなければならないとなると処理速度を考えた場合
数フレーム先の相手の出方をすべて予想してそれに対応できるような動作をするというのは
困難にょ。
プチコンはポケコン（最速クラスのPC-E500）や一般的な8ビットパソコンと比べてBASIC
同士ならば100倍くらいの速度（マシン語ゲームに近いレベルの速度）であり、よほど凝った
ものでない限りは思考ルーチンを入れても60fpsでの動作は実現が可能にょ。

どのようにするかはさきほどのオセロゲームのようにある程度ゲームの種類を限定して考える
必要があるにょ。
ここでは昨日書いた卓球ゲームなどの対戦型のスポーツゲーム（球技）について考えてみる
ことにするにょ。
斜め上方に打ち出されたボールは無風で空気抵抗などを考えない場合は放物線を描くにょ。
これはサイドビューの2DゲームであればX方向は等速運動、Y方向は等加速度運動となるにょ。
要するにX、Yに分解して考えれば簡単にボールの軌道が分かるということにょ。
水平方向を基準に考えてAラジアンの角度で斜めにボールを打ち出す場合には初速がVの時には
X、Yに分解して考えるとX方向の初速はCOS(A)*V、Y方向の初速はSIN(A)*Vとなるにょ。
X方向は等速運動であるためTフレーム後にはX方向の座標はVX*Tほど変化しているにょ。（VXは
X方向の速度を示している）
Y方向は等加速度運動であるため上記Y方向の初速をVYと置き換えた場合時にはTフレーム後
には速度はVY-G*Tとなっているにょ。（ここでのGはゲーム内での重力加速度を示す）
Tフレーム後の速度の式があればそれを積分することでTフレーム後の座標も求めることが
できるにょ。（サイドビューによる二次元ではなく三次元移動であればX方向の速度をさらに
分解してやればいい）

　Tフレーム後のX座標　VX*T
　　　〃　　　 Y座標　VY*T-G*T*T/2
　　※座標は打ち出した時の座標を原点と考えた相対座標

三角関数とか積分とか分からなくてもこの公式を覚えてしまえば初速が分かれば一定時間後の
ボールの位置は簡単に求まるにょ。
ボールが打ち出されたのが地面より上でそれを斜め上に打ち出し地面に付いた時の距離という
のもこの公式から求めることができるにょ。
Y座標の方をTの値を求める二次方程式と考えてやればいいわけだからね。
例えば上方向が正とした場合に地面のY座標を0と考えて打ち出したときの座標がY0ならば
VY*T-G*T*T/2+Y0=0をTについて解けばいいにょ。

　地面より上から斜め上方に打ち出したボールが地面に落下するのにかかる時間
　T=(VY+SQR(VY*VY+2*G*Y0))/G

Tの値が求まればX方向の座標も上記の公式で求まるにょ。
計算から求まるTの値は整数とは限らないけど実際は1フレーム単位でしか描画はできない
ため理論値とは最大1フレームの誤差が出るにょ。（VXの値が10で内部の座標が1当たり
画面上で1ドットに相当するならば最大で10ドットの誤差となる）
落下する座標が分かればその座標に移動すればそのボールを落下する前に打ち返すことが
できるにょ。
そのため思考ルーチンを作る場合には打ち返すためあらかじめその座標に移動するという
必要があるにょ。
卓球ではワンバウンドでの返球となるためバウンドして打ちやすい高さに達するまでの時間を
求めそこから移動すべき座標を求めることができるにょ。

移動すべき座標が分かればそこに一気に移動して打ち返すということを考えるかもしれない
けどそれはあまり良い思考ルーチンとは言えないにょ。
というのもコンピュータ側は正確に計算することでボールを返す場所を1ドットも狂わずに
完璧に狙えるような思考ルーチンを作ることは可能だけどそんな正確無比なコンピュータでは
対戦しても面白くないためにょ。
無敗を誇る最強の思考ルーチンを作ることさえ可能だし、そんなコンピュータに負けても
全然悔しくはないにょ。
正確無比をベースとして乱数でわざとミスするように設定した場合にはたとえ勝っても
「運が良かった」としか思えなくなってしまうにょ。
これは私がポケコン用に作ったピーチバレーでも考えたことであり、詳しくはこちらの開発
日記に書いているにょ。

　◎ピーチバレー　開発日記
　http://ochameclub.web.fc2.com/E500/SOFT/peach_volley_diary.htm

ポケコンでは「面白くない」というだけではなく速度面の問題もあるため上記の公式から
求めた概算のTの値による落下予測座標（この座標はプレイヤー側にも分かるように画面に
落下予測位置を表示しているため不公平さを無くすことができるだけではなく狭いポケコン
でも十分にプレイできる難易度になっている）を元に思考しているにょ。

座標を求めてそれを移動するという場合にもやはり問題が出てくるにょ。
それはボールを打って瞬時に移動し始めるということは人間にはできないためにょ。
普通の人間の反射神経は0.1～0.2秒程度となっているにょ。
つまり、思考ルーチンに人間らしさを求めるならば最初の数フレームは何もできないと
いうことにょ。
次に移動する量を考えてみるにょ。
キャラを等加速度運動するタイプのゲーム（常に等速ではなく初速ゼロから徐々に加速
していって最高速に達するまで少し時間を要するゲーム）の場合にはいきなりコンピュータ
側が最高速度で動き始めたら先ほどの正確無比な打ち返しよりも見た目ですぐに分かるため
「いかにもインチキしています」と言わんばかりになってしまうにょ。
ちなみに上記のピーチバレーではコンピュータのレベルによって打ったあとに反応できる
までの時間が異なり、プレイヤー側と全く同じように等加速度運動で動いており、さらに
速度がつきすぎて目的の場所を通りすぎたら一旦停止してそこから戻るという人間と全く
同じことを再現しているにょ。（あらかじめ座標を計算して減速しながら通り過ぎること
なくジャストの位置に停止することもできるもできるけどそれはあえてやってない）

卓球ゲームの場合はタッチパネルで操作するため一度に移動できるドット数に制約はないにょ。
そうなればコンピュータ側はプレイヤーが打った瞬間にボールを打ち返すべき座標に
ラケットを移動させることも可能になってくるにょ。
そうなればどんな速いスマッシュを打っても無意味になるし、左右のコーナーの打ち分けも
無意味になるにょ。
このように書けば面白くないゲームになってしまうというのが分かるのではないかと思うにょ。
卓球ゲームの思考ルーチンでは人間の限界速度を超えない程度の速度を最高として等加速度
運動でラケットを移動させるのがベターといえるにょ。

任意の場所に打ち分けが可能になったり、打球の種類が選択できるゲームだとそれらを
どのように活用するかで強さや面白さが変わってくるにょ。
左右の打ち分けが可能になゲームであっても正確無比に左右のライン上をジャストで狙って
くるのは面白くないのである程度の誤差がある方が楽しめるにょ。
左右どちらかを完全に乱数で決めるのではなくプレイヤー側が打ちにくいところに打つ
方がやっていて楽しめるにょ。
ただし、プレイヤーが画面の右にいるからといって常に左側にしか打ってこないと完全に
パターンとして見切られてしまうため楽しめないのである程度は乱数で幅を持たせた方が
良いと思うにょ。（ボールの落下座標を正確に求めずさきほどの公式の概算予想位置を
そのまま活用すればこのある程度の幅を意識せずにちょうど良い感じでボールが散って
くれることもある）

私が昨日動画で公開した制作中のプチコン用の卓球ゲームでは実際にラケットを振っている
イメージでラケットを左下から右上に少し移動させればコートの右側に打ち返すことが
でき右下から左上に移動させればコートの左側に打ち返すことができるにょ。（移動量が
多ければ強い打球となり、ラケットに当たる場所によって打球の方向も変わるため
ラケットを右側に動かせば必ずボールが右に行くというわけでもない）
これをコンピュータの思考ルーチンで実現するならば本来移動すべき場所から少し離れた
位置に移動してそこからボールが来る瞬間を狙って再び移動する必要があるにょ。
1つ目の移動でスイングの体勢を整えて2つ目の移動で打ち返すという感じにょ。
動作が2段階に分かれることで戦略も生まれてくるにょ。
コンピュータが落下予測位置よりも右にラケットを構えている場合は左に打ち返すのを
意味しているためその場合はあらかじめ左に移動を始めておけばいいにょ。
先ほどは打ち返してから0.1～0.2秒は何もできないと書いたけど実は相手が打ち返す前に
思考できる要素ができたということにょ。
これをコンピュータ側の思考ルーチンに組み込めばかなり強いものになるにょ。（逆に
それを利用してフェイントを仕掛けるという選択肢も生まれる）

スマッシュを打つならば高いボールが上がったかどうかを判断する必要があるにょ。
そのためスマッシュを打つときのためにボールの最高到達点の概算座標も求める必要が
出てくるにょ。
それが一定以上になった場合にはそれをめがけて高速なスイングを行えば相手のコートに
叩きつける強力なスマッシュが打てるにょ。
カットやドライブの打ち分けはそうかというと私は卓球経験が学校の授業以外ないので
よく分からないにょ（笑）
とりあえず、機能だけは実装してみたけどどういう時にカットを打てばいいのか分からない
ため思考ルーチンに組み込む場合にはランダムになってしまいそうにょ。
思考ルーチンを組み込む場合にはゲーム制作の基本であるリスクとリターンを入れておく
のが良いと思うにょ。
これを使えば絶対的に有利になるというものばかりだと展開がワンパターンになって
しまうため強い技は出すのが難しかったり、一定の条件が揃わないと出せなかったり、
出したあとの隙が大きくなったりというリスクが必要になるということにょ。（先ほどの
スマッシュでいえば高い打点となるボールに対してラケットを高速移動させてボールに
当てるということが必要になる）

移動や打ち分けはこれで大体説明したけどゲームを面白くするためにはラケットとの当たり
判定も重要になるにょ。
どんなゲームにでも当てはまるけどミスした際は「ミスの理由に納得ができる」というのが
重要にょ。（なぜミスしたのか分からないようではダメということ）
この辺については第4回プチコン講座のコラムにも書いているので参考にして欲しいにょ。

　◎コラム　当たり判定は正確に行う必要はない！？
　http://ochameclub.web.fc2.com/petitcom/p004.htm#column

私が作っている卓球ゲームはボールの動きは3次元で計算しているけどラケットの動きは
2次元であるためそもそも当たり判定を正確に行うことは不可能にょ。
しかし、自然な判定を行うことは可能であり、それは昨日も書いたように見た目通りの当たり
判定をすることで解決したにょ。
これによって、ラケットで捉えたつもりで空振りしたりとか、ラケットに当たる前にボールが
打ち返されたりという問題は解消できるにょ。
ただし、ボールの動きが3次元でラケットの動きが2次元という不一致によってプレイヤー
側とコンピュータ側では（見た目ではなく）内部座標における当たり判定の大きさが異なる
という問題が発生してしまうにょ。（プレイヤー側は前方に広く後方に狭い、コンピュータ
側は後方に広く前方に狭い）
上記のように対戦ゲームにおいてはプレイヤー側とコンピュータ側はフェアにしたいという
私のポリシーによって思考ルーチン作りは頓挫してしまったというわけにょ。
まぁそこまで拘らなければ全く問題ないことだけどね。

《　5月8日追記　》

私がプチコンで制作途中だった卓球ゲームは上記のようにボールの動きは3次元で計算して
ラケットの動きは2次元で計算していてラケットとボールは見た目通りの当たり判定を行って
いたためコンピュータとプレイヤーで当たり判定の大きさが変わってしまうという問題が
発生してしまっていたにょ。
これはラケットの動きをXY方向にしてしまったのが問題だったのでこれをXZ方向にして
しまえば問題ないにょ。（高さの概念ががあるからXYと決めていたのがまずかった）
つまり、表示上のY座標が小さくなるほどプレイヤーのラケットの大きさを小さくするという
ことにょ。（これは内部におけるラケットのZ座標を元に決めていくことになる）
これによってコンピュータとプレイヤーの当たり判定はフェアになるにょ。
移動量の問題があるけどコンピュータの方をプレイヤーの速度に合わせる（手前に近い
ほどZ方向の速度は減速させる）ことで完全にフェアにできるにょ。（そこまでする必要が
あるかどうかは微妙なレベルだけど）