Java実装によるミニマックスアルゴリズムの概要

投稿日: 2019-10-18 2022-11-06
タグ: Algorithms, Programming

1. 概要

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

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

2. 序章

ミニマックスは意思決定アルゴリズムであり、通常はターン制の2人ゲームで使用されます。アルゴリズムの目標は、最適な次の動きを見つけることです。

アルゴリズムでは、一方のプレーヤーは最大化子と呼ばれ、もう一方のプレーヤーは最小化子と呼ばれます。ゲームボードに評価スコアを割り当てると、一方のプレーヤーが最大スコアのゲーム状態を選択し、もう一方のプレーヤーが最小スコアの状態を選択しようとします。

言い換えれば、 the マキシマイザーは最高のスコアを取得するように機能し、最小化者は動きに対抗しようとして最低のスコアを取得しようとします。

ゼロサムゲームのコンセプトに基づいています。ゼロサムゲームでは、合計ユーティリティスコアがプレーヤー間で分割されます。あるプレイヤーのスコアが上がると、別のプレイヤーのスコアが下がります。したがって、合計スコアは常にゼロです。 1人のプレーヤーが勝つためには、もう1人が負ける必要があります。このようなゲームの例としては、チェス、ポーカー、チェッカー、三目並べがあります。

興味深い事実-1997年、IBMのチェスをプレイするコンピューターDeep Blue（Minimaxで構築）は、Garry Kasparov（チェスの世界チャンピオン）を打ち負かしました。

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

私たちの目標は、プレイヤーにとって最良の動きを見つけることです。そのためには、評価スコアが最も高いノードを選択するだけです。プロセスをよりスマートにするために、潜在的な対戦相手の動きを先読みして評価することもできます。

移動ごとに、計算能力が許す限り多くの移動を先読みすることができます。アルゴリズムは、対戦相手が最適にプレイしていることを前提としています。

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

以下のゲームツリーを考えてみましょう。

マキシマイザーはルートノードから開始し、最大スコアの移動を選択します。残念ながら、葉だけが評価スコアを持っているため、アルゴリズムは葉のノードに再帰的に到達する必要があります。与えられたゲームツリーでは、現在、最小化者がリーフノードからの移動を選択する番です。これにより、スコアが最小のノード（ここではノード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());
    }
}

さらに、ノードおよびツリークラスの実装も必要です。

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. 改善

ほとんどの問題について、ゲームツリー全体を構築することは現実的ではありません。 実際には、部分的なツリーを開発できます（事前定義されたレベル数までのみツリーを構築します）。

次に、評価関数を実装する必要があります。この関数は、プレーヤーにとって現在の状態がどれだけ良好かを判断できるはずです。

完全なゲームツリーを構築しなくても、分岐係数の高いゲームの動きを計算するのに時間がかかる場合があります。

幸いなことに、ゲームツリーのすべてのノードを探索せずに、最適な動きを見つけるオプションがあります。いくつかのルールに従うことでいくつかのブランチをスキップでき、最終結果には影響しません。 このプロセスはプルーニングと呼ばれます。アルファベータ法は、ミニマックスアルゴリズムの一般的な変形です。

6. 結論

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

分岐係数が非常に高いゲームには最適ではない場合があります（例：囲碁のゲーム）。それでも、適切な実装があれば、かなりスマートなAIになる可能性があります。

いつものように、アルゴリズムの完全なコードはGitHubのにあります。

getdocs

13036