GPx03

Snap!を開く　https://snap.berkeley.edu/snap/snap.html

アクションゲームのＡＩ：

Google Doodle のゲーム https://www.google.com/doodles/30th-anniversary-of-pac-man?hl=ja

PACMAN（1980年のアーケードゲーム）の再現版をプレイできる。

操作はキーボードから矢印キーで行う。

iPadやスマフォからはフリック操作で移動方向（上下左右）指示できる。

プレイして敵キャラクター（ゴースト）の移動方針を観察する。

パックマンの開発者 岩谷徹氏の PACMANの敵キャラ（ゴースト）のAIについての論文

https://jsai.ixsq.nii.ac.jp/ej/?action=pages_view_main&active_action=repository_view_main_item_detail&item_id=9670&item_no=1&page_id=13&block_id=23

論文のポイント：

・４色のゴーストの移動方針

・ゲームの難易度の自動調整

・ゲームの進行とストレス制御、緊張と緩和

思考型ゲームのＡＩ：

２人ゼロ和完全情報ゲーム

２人が交互にプレイ

（ゼロ和）先攻・後攻のどちらがが勝つ。誰かが勝つと誰かが負ける。誰かが負けると誰かが勝つ。

プレイに得点を付けるとしたら全プレイヤーの得点と失点の合計はプレイ中は常に ０ になる。

（完全情報）自分の選択肢を決定するために必要な情報をすべて手に入れることができる。

自分の考えた作戦を確実に実行できる。

相手が立案可能な全ての作戦を想定して対応できる。

この条件に合わなくなるゲームの要素

偶然性（サイコロ、山札からカードを引くなどのランダム性）

不完全情報（相手のカードの内容が見えないなど）

3人以上のゲーム（協力を求めることが可能など）

ゲーム木と探索

２０１６年度の講義資料 https://prezi.com/vhpy2_dmeu1s/14/ 

指遊び「割りばし」の後手必勝遷移図 https://twitter.com/kaityo256/status/1081578406980943872?s=19

解説記事：https://qiita.com/kaityo256/items/86562e9ab20ae7bced1d

この木なんの木？　モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々

〇×ゲームのプログラム

ターン制の2人対戦ボードゲーム用の基本的なアルゴリズムや盤面の処理方法について解説する。

開発環境はSNAP!を使う。

〇×ゲームのルール：

３ｘ３マスに〇と×を交互に描き、先に自分の印を　縦　横　斜め　のいずれかの列に3個並べた方が勝つ

プログラム要素と実装ステップ：

ゲーム画面の実装

・〇×の描画

・ゲーム盤面の表示

・ゲーム操作UI

マウスによる印の位置の指定

・ゲーム進行管理

人間ｖｓ人間による交互プレイ

ここまではゲームをプレイする道具としてのプログラムの内容。

コンピュータププレイヤー実装に向けての準備

・ゲーム終了判定

〇か×が3個並んだかを判定する。

画面の9マス全てに印が付いても〇か×が3個並ばないなら引分け。

コンピュータープレイヤー実装

・コンピュータープレイヤーの番を人間プレイヤーの代わりに組み入れる

思考ルーチンの実装ステップ

・ランダムプレイヤー

ルールに反しない様に自分の番で選択可能な着手からランダムで1手を選んで実行する

今回はランダムプレイヤーの実装まで。思考ルーチンの強化については今後の授業で扱うかもしれない。

・先読み無しの思考ルーチン

自分の番で勝利着手※が有ればそれを選ぶ（複数ある場合はランダムにその中から選択）。無い場合はランダムプレイヤーと同じ。

※この判定は、着手可能な手を1つづつ試しながら（※２）ゲーム終了判定のコードを用いればよい。

※２ 試した手をキャンセルしてゲーム盤面を元に戻すコードが必要になる。

・１手先読み思考ルーチン

自分の番で勝利できる着手が有ればそれを選ぶ。

無い場合は、次の相手の番で相手が勝つことが可能※な自分の着手を除いた残りの着手からランダムに選ぶ。

（言い換えると、敗着となる手は選ばないようにする ということ）

※この判定は仮に1手自分の印を置いて「先読み無しの思考ルーチン」を相手の番に切り替えて利用する。

どの手を選んでも相手の番で勝たれてしまう（自分が負ける）場合は、ランダムプレイヤーと同じ。

・ｎ手先読み思考ルーチン

再帰呼び出しのプログラム手法を利用してゲーム木探索を実装する。

勝利着手を見つけた場合はそれをプレイする。

指定した手数まで先読みした場合に勝利着手が見つからない場合、

負けない着手の中からランダムに選択する

↑が無い場合、引分けの局面が有ればそれを選択する

↑もない場合、必敗の局面ならランダムにプレイする

・思考ルーチンの高速化

・局面評価の導入

ｎ手先読みした盤面について（ゲームの勝敗が決まらない場合でも）有利不利を判定する。

課題１／２

　〇×ゲームの人間対人間のプレイ機能をSNAP!で実装する

　Webclassの講義資料に添付したファイルをダウンロードしてSNAP!に読み込み、コードを組み立てて実験する。
　　ファイル名：tick-tack-toe_kadai.xml

　作成したコードをSNAP!から保存（ダウンロード）してWebclassのGPx03課題の問1として提出する。

　応用課題：

盤面のサイズを４ｘ４や５ｘ５などに拡張

プレイヤーの人数を増やす（3色に対応）
　に取り組んだ場合は追加点を与える

ゲーム盤面の作成

ターンプレイヤーの制御

ゲームのプレイ画面の例

課題２／２

　〇×ゲームにコンピュータプレイヤーをSNAP!で実装する。

　コンピュータの思考ルーチンはランダムプレイで実装する。

　Webclassの講義資料に添付したファイルをダウンロードしてSNAP!に読み込み、コードを組み立てて実験する。

　　ファイル名：tick_tack_toe_kadai2b.xml

　作成したコードをSNAP!から保存（ダウンロード）してWebclassのGPx03課題の問2として提出する。

　応用課題：

マス目がすべて埋まった後ではコンピュータにプレイさせなくする。

取り組んだ場合は追加点を与える

ランダムプレイヤーの実装

ゲーム終了の判定処理

　〇×の印を付けた後で3個同じマークが並んだか判定する。

　Webclassに判定処理を組み込んだSNAP!のコードを置いておく（完成状態）。

　ファイル名　tic-tac-toe_kadai2e.xml

　SNAP!に読み込んで動作を確認するとよい。これに関する提出課題は無い。