1概要

この記事では、MinimaxアルゴリズムとそのAIでの応用について説明します。これはゲーム理論のアルゴリズムなので、それを使って簡単なゲームを実装します。

また、このアルゴリズムを使用する利点と、それをどのように改善できるかについて説明します。


2前書き

ミニマックスは意思決定のためのアルゴリズムです。このアルゴリズムの目的は、最適な次の動きを見つけることです。

このアルゴリズムでは、一方のプレーヤーをマキシマイザーと呼び、もう一方のプレーヤーをミニマイザーと呼びます。評価スコアをゲームボードに割り当てると、一方のプレーヤーが最大スコアのゲーム状態を選択し、もう一方のプレーヤーが最小スコアの状態を選択します。

言い換えれば、


















マキシマイザーは最高得点を得るように働きますが、ミニマイザーは動きに対抗しようとすることによって最低得点を得ようとします**

それはhttps://en.wikipedia.org/wiki/Zero-sum__game[zero-sum game]の概念に基づいています。

ゼロサムゲームでは、合計効用スコアはプレイヤー間で分けられます。あるプレイヤーの得点が増加すると、他のプレイヤーの得点も減少します。

したがって、合計得点は常にゼロです。

一人のプレイヤーが勝つためには、他のプレイヤーが負けなければなりません。このようなゲームの例は、チェス、ポーカー、チェッカー、三目並べです。

興味深い事実 – 1997年に、IBMのチェスプレイコンピュータDeep Blue（Minimaxで構築）がGarry Kasparov（チェスの世界チャンピオン）を破った。


3ミニマックスアルゴリズム

私たちの目標はプレイヤーにとって最良の動きを見つけることです。そうするために、私たちはただ最良の評価スコアを持つノードを選ぶことができます。プロセスをより賢くするために、我々はまた、先を見越して潜在的な相手の動きを評価することができます。

それぞれの動きに対して、私たちは私たちの計算能力が許す限り多くの動きを先読みすることができます。アルゴリズムは相手が最適に遊んでいると仮定します。

技術的には、ルートノードから始めて、可能な限り最良のノードを選択します。評価スコアに基づいてノードを評価します。私たちの場合、評価関数は結果ノード（葉）だけにスコアを割り当てることができます。

したがって、我々はスコアを用いて葉に再帰的に到達し、スコアを逆伝播させる。

以下のゲームツリーを見てください。

リンク:/uploads/minimax-768×196.png%20768w[]

  • Maximizer


    はルートノード

    から始まり、最大スコアの移動を選択します。残念ながら、葉だけがそれらと一緒に評価スコアを持っているので、アルゴリズムは再帰的に葉の節に到達しなければなりません。与えられたゲームツリーでは、現在のところ最小化者が

    リーフノードから移動を選択** するようにしているので、最小スコアのノード（ここではノード3と4）が選択されます。それがルートノードに達するまで、それは同様に最良のノードを選び続ける。

それでは、アルゴリズムのステップを正式に定義しましょう。

  1. 完全なゲームツリーを構築する

  2. 評価関数を使って葉のスコアを評価する

  3. プレーヤーのタイプを考慮して、葉から根へのバックアップスコア.

    • 最大のプレーヤーのために、最大のスコアを持つ子供を選んでください

    • 最小プレーヤーの場合、最小スコアの子供を選択してください

  4. ルートノードで、最大値を持つノードを選択して、

対応する動き


4実装

それでは、ゲームを実装しましょう。

このゲームでは、

n

個の骨

を持つ

ヒープがあります。両方のプレイヤーは、自分の順番で

1、2または3個のボーンを拾います

骨を取れないプレイヤーはゲームに負けます。各プレイヤーは最適にプレーします。

n

の値を考えて、AIを書きましょう。

ゲームのルールを定義するために、

GameOfBones

クラスを実装します。 

class GameOfBones {
    static List<Integer> getPossibleStates(int noOfBonesInHeap) {
        return IntStream.rangeClosed(1, 3).boxed()
          .map(i -> noOfBonesInHeap - i)
          .filter(newHeapCount -> newHeapCount >= 0)
          .collect(Collectors.toList());
    }
}

さらに、

Node

クラスと

Tree

クラスの実装も必要です。 

public class Node {
    int noOfBones;
    boolean isMaxPlayer;
    int score;
    List<Node> children;
   //setters and getters
}
public class Tree {
    Node root;
   //setters and getters
}

それでは、アルゴリズムを実装しましょう。それは先を見越して最善の行動を見つけるためにゲームツリーを必要とします。それを実装しましょう: 

public class MiniMax {
    Tree tree;

    public void constructTree(int noOfBones) {
        tree = new Tree();
        Node root = new Node(noOfBones, true);
        tree.setRoot(root);
        constructTree(root);
    }

    private void constructTree(Node parentNode) {
        List<Integer> listofPossibleHeaps
          = GameOfBones.getPossibleStates(parentNode.getNoOfBones());
        boolean isChildMaxPlayer = !parentNode.isMaxPlayer();
        listofPossibleHeaps.forEach(n -> {
            Node newNode = new Node(n, isChildMaxPlayer);
            parentNode.addChild(newNode);
            if (newNode.getNoOfBones() > 0) {
                constructTree(newNode);
            }
        });
    }
}

今度は、両方のプレイヤーに最適な移動を選択することによって、プレイアウトをシミュレートする

checkWin

メソッドを実装します。スコアを次のように設定します。

  • 1、マキシマイザーが勝った場合

ミニマイザが勝った場合は** -1

最初のプレイヤー（この場合はマキシマイザー）が勝った場合、

checkWin

はtrueを返します。 

public boolean checkWin() {
    Node root = tree.getRoot();
    checkWin(root);
    return root.getScore() == 1;
}

private void checkWin(Node node) {
    List<Node> children = node.getChildren();
    boolean isMaxPlayer = node.isMaxPlayer();
    children.forEach(child -> {
        if (child.getNoOfBones() == 0) {
            child.setScore(isMaxPlayer ? 1 : -1);
        } else {
            checkWin(child);
        }
    });
    Node bestChild = findBestChild(isMaxPlayer, children);
    node.setScore(bestChild.getScore());
}

ここで、

findBestChild

メソッドは、プレーヤーがマキシマイザーの場合、最大スコアを持つノードを見つけます。それ以外の場合は、最小スコアの子を返します。 

private Node findBestChild(boolean isMaxPlayer, List<Node> children) {
    Comparator<Node> byScoreComparator = Comparator.comparing(Node::getScore);
    return children.stream()
      .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed())
      .orElseThrow(NoSuchElementException::new);
}

最後に、

n

（ヒープ内のボーンの数）の値を使用してテストケースを実装しましょう。 

@Test
public void givenMiniMax__whenCheckWin__thenComputeOptimal() {
    miniMax.constructTree(6);
    boolean result = miniMax.checkWin();

    assertTrue(result);

    miniMax.constructTree(8);
    result = miniMax.checkWin();

    assertFalse(result);
}


5改善

ほとんどの問題で、ゲームツリー全体を構築するのは現実的ではありません。

実際には、私たちは部分的な木を開発することができます（あらかじめ定義された数のレベルまで木を組み立てるだけです）

。

それから、私たちは

評価関数

を実装する必要があります。

完全なゲームツリーを構築しなくても、高い分岐係数を持つゲームの移動を計算するのは時間がかかる可能性があります。

  • 幸いなことに、ゲームツリーのすべてのノードを探索することなく、最適な動きを見つけることができます。いくつかの規則に従っていくつかの分岐をスキップすることができますが、最終的な結果には影響しません。

    このプロセスは


    剪定

    と呼ばれます。


Alpha–beta pruning

は、ミニマックスアルゴリズムの一般的な変種です。


6. 結論

ミニマックスアルゴリズムは、コンピュータボードゲームで最も人気のあるアルゴリズムの1つです。それは順番に基づいてゲームに広く適用されています。プレイヤーがゲームについての完全な情報を持っているとき、それは良い選択です。

非常に高い分岐係数を持つゲーム（例:GOのゲーム）には最適ではないかもしれません。それにもかかわらず、適切な実装を考えれば、それはかなり賢いAIになり得ます。

いつものように、このアルゴリズムの完全なコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-1[GitHubへの追加]にあります。