Lispとは ゲーム理論 minimaxアルゴリズム αβアルゴリズム ソースコードの一部

Presentation on theme: "Lispとは ゲーム理論 minimaxアルゴリズム αβアルゴリズム ソースコードの一部"— Presentation transcript:

1 Lispとは ゲーム理論 minimaxアルゴリズム αβアルゴリズム ソースコードの一部
Lispによるothello Lispとは ゲーム理論 minimaxアルゴリズム αβアルゴリズム ソースコードの一部

2 Lispとは 記号処理を中心にしたプログラム言語。 リスト形式のデータ処理に向いている。 人工知能（AI）研究などの分野で使われている。
1962年に米MIT（マサチューセッツ工科大学）のJ.マッカーシーが考案し、その後様々な研究機関が独自の拡張を行っていたが、1984年にCommon Lispとして標準化された。 Prologと並ぶ人工知能分野の基本言語で、「リスト」と呼ばれるデータ操作命令の並びの形式を処理するのが特徴。 Lispのプログラミングは、既に定義されているいくつかの関数を組み合わせて新しい関数を作る形で記述される。また、呼び出すべき関数を実行時に決定でき、変数や関数の型宣言が不要リスト処理や記号処理用の機能が組み込まれている。つまり関数型言語である。

3 ゲーム理論とは ゲーム理論はAIの最も古いアリアのひとつです。ゲームを難しくしているのは限られた時間の中で問題をとかなければならないことです。 例えばチェス。 　　 チェスでは平均分岐数が約３５個ある。各プレーヤーは大体５０ステップずつ行うので、トータルで35100もの分岐が考えられる。 　　　これだけの分岐をすべてチェックするのは一生かかっても無理かもしれない。 このようにゲーム理論は現実的な問題を解決する上で有力なものである。

4 Minimaxアルゴリズム ミニマックス法は非常に単純な考え方で、相手がこちらの一番不利になる手を打ってくるとして、自分が打てる最良の手を探すアルゴリズムです。つまり、相手は評価をMINにする手、自分はその中で評価をMAXにする手を選ぼうというものです。

5 αβアルゴリズム この方法はミニ･マックス法と基本的に同じ考え方で、相手は常に一番有利な手を打って来ると考えますが、その上でこれ以上は考えても自分にとって不利な手しか出てこないような枝については、省略して行くという方法です。 盤面の評価を行いながら木を掘り進めることで、余計な枝について評価や探索を行うことを防ぎます。 資源（メモリ、CPU）の有効利用につながります。

6 Othelloのソースコード① (defun minimax (player board ply eval-fn)
(if (= ply 0) 　　　(funcall eval-fn player board) 　　　(let ((moves (legal-moves player board))) (if (null moves) 　　　(if (any-legal-move? (opponent player) board) 　　　　　　(- (minimax (opponent player) board (- ply 1) eval-fn)) 　　　　　　　　　(final-value player board)) (let ((best-move nil) (best-val nil)) 　　　(dolist (move moves) (let* ((board2 (make-move move player (copy-board board))) (val (- (minimax (opponent player) board2 (- ply 1) eval-fn)))) (when (or (null best-val) (> val best-val)) (setf best-val val) (setf best-move move)))) (values best-val best-move))))))

7 Othelloのソースコード② (defun alpha-beta (player board achievable cutoff ply eval-fn) (if (= ply 0) 　　　(funcall eval-fn player board) 　　　(let ((moves (legal-moves player board))) (if (any-legal-move? (opponent player) board) 　　　(- (alpha-beta (opponent player) board (- cutoff) 　　　　　　　　　　　　　　　　　　　　 (- achievable) (- ply 1) eval-fn)) (final-value player board)) (let ((best-move (first moves))) (loop for move in moves do 　(let* ((board2 (make-move move player (copy-board board))) (val (- (alpha-beta (opponent player) board2 (- cutoff) 　　　　　　　　　　　　　　　　　　　　 (- achievable) (- ply 1) eval-fn)))) 　　　　　　　　　(when (> val achievable) (setf achievable val) (setf best-move move))) until (>= achievable cutoff)) (values achievable best-move)))))

8 Othelloの始め方 とタイプして、実行するとゲームが始まります。 Minimax vs αβ 結果は？ (othello
　　　　(minimax-searcher 3 #'count-difference) 　　　　(alpha-beta-searcher 3 #'weighted-squares)) とタイプして、実行するとゲームが始まります。 Minimax　vs　αβ 結果は？

9 おまけ（さらにOthelloをJessで）
JessとはExpertSystem構築ツールであるCLIPSをJAVA環境で使用できるようにしたもの。 文法はLISPになかなか似てる。 人工知能プログラミング　＋　JAVA LISPで書いたコードを１００％JESSにtranslateすることは難しい。（多分無理。） ＝＞足りないところはJAVAで。

10 おまけ（続き・・・） イメージ データ JAVA （GUI担当） JESS （アルゴリズム担当） データ

11 JavaとJessのコード public int[][] minimax(int player, int[][] board, int ply){ int eval = 0; int[][] position = new int[1][1]; ・・・・・・ return position; 　　　} Minimaxメソッド 引数：player（現在のplayer）、board（現在のboard）、ｐｌｙ（検索木の深さ） Return：position（minimaxによって決められた手）

12 JavaとJessのコード① public int[] minimax(int player, int[][] board, int ply){ int eval = 0; int[] position = {0}; if(ply == 0){ eval = weightedSquares(player, board); } else{ minimax2(player, board, ply); return position;

13 JavaとJessのコード② private int[] minimax2(int player, int[][] board, int ply){ int[][] possibleStone; possibleStone = parent.checkAll2(parent.turn); try{ r.executeCommand("(bind ?moves (create$ ))"); for(int i = 0; i < 8; i++){ for(int j = 0; j < 8; j++){ if(possibleStone[i][j] == 1) r.executeCommand("(bind ?moves (create$ ?moves "+ (i*10 + j) +"))"); } if(r.executeCommand("(eq ?moves (create$ ))").equals("TRUE")){ r.executeCommand("" + "" + ""); else minimax3(player, board, ply); catch(JessException je){ System.err.println(je); return new int[1];