MinMax algorithm in practice - tictactoe. On what basis we choose the right move?

Question

I deal with that for a week now.

I have constructed a tree of gameboards and I evaluated them - > every node hasint evaluation field on what basis I choose the right move? I cannot get it from any tutorials, youtube video. The algorithm seems to be useless.

In my evaluation method: 1 cross/circle inline 10^0 points, 2 crosses/circles in line 10^1 points,... n crosses/circles in line 10^(n-1) points. Is it + or - 10^(n-1) points depends on a level of tree.

I put cross on a top left field my stupid algorithm thinks this is the best possible track for computer player(CIRCLE):

[O| | |
------
 | | |
------
 | | |

Evaluation -1
TotalEvaluation -1
Dobry  X
, O|X| |
------
 | | |
------
 | | |

Evaluation 0
TotalEvaluation -1
Dobry  X
, O|X| |
------
O| | |
------
 | | |

Evaluation -11
TotalEvaluation -12
Dobry  X
, O|X| |
------
O| | |
------
X| | |

Evaluation 10
TotalEvaluation -2
Dobry  X
, O|X| |
------
O|O| |
------
X| | |

Evaluation -31
TotalEvaluation -33
Dobry  X
, O|X| |
------
O|O| |
------
X| |X|

Evaluation 30
TotalEvaluation -3
Dobry  X
]

If you understand any of it please try to explain.

This is my Node:

package tictactoe;

import java.util.ArrayList;

import static tictactoe.Field.*;

public class Node {
    static int KEY = 0;
    int level, key, evaluation;
    int[][] board;
    ArrayList<Node> children;
    int stamp;
    int totalEval;
    Node parent;

    Node(int[][] board, int level, int stamp, Node parent) {
        this.board = board;
        this.level = level;
        this.stamp = stamp;
        this.parent = parent;
        totalEval = 0;
        children = new ArrayList<Node>();
        key = KEY++;
        setEvaluation();
        if(parent != null)
            totalEval = parent.totalEval + evaluation;
        else
            totalEval = evaluation;

    }

    public void setEvaluation() {
        int evaluation = 0;
        int howManyInLine = board.length;
        int opponentSign = CIRCLE;
        if(stamp == CIRCLE)
            opponentSign = CROSS;
        for(; howManyInLine > 0; howManyInLine--) {
            if(level % 2 == 0) {
                evaluation += countInlines(stamp, howManyInLine);
                evaluation -= countInlines(opponentSign, howManyInLine);
            } else {
                evaluation -= countInlines(stamp, howManyInLine);
                evaluation += countInlines(opponentSign, howManyInLine);
            }
        }
        this.evaluation = evaluation;
    }

    public int countInlines(int sign, int howManyInLine) {
        int points = (int) Math.pow(10, howManyInLine - 1);
        int postiveCounter = 0;
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                //czy od tego miejsca jest cos po przekatnej w prawo w dol, w lewo w dol, w dol, w prawo
                if(toRigth(i, j, sign, howManyInLine))
                    postiveCounter++;
                if(howManyInLine > 1) {
                    if(toDown(i, j, sign, howManyInLine))
                        postiveCounter++;
                    if(toRightDiagonal(i, j, sign, howManyInLine))
                        postiveCounter++;
                    if(toLeftDiagonal(i, j, sign, howManyInLine))
                        postiveCounter++;
                }
            }
        }
        return points * postiveCounter;
    }

    public boolean toRigth(int i, int j, int sign, int howManyInLine) {
        for(int start = j; j < start + howManyInLine; j++)
            if(j >= board.length || board[i][j] != sign)
                return false;
        return true;
    }

    public boolean toDown(int i, int j, int sign, int howManyInLine) {
        for(int start = i; i < start + howManyInLine; i++)
            if(i >= board.length || board[i][j] != sign)
                return false;
        return true;
    }

    public boolean toRightDiagonal(int i, int j, int sign, int howManyInLine) {
        int startJ = j;
        for(int start = i; i < start + howManyInLine; i++, j++)
            if(i >= board.length || j >= board.length || board[i][j] != sign)
                return false;
        return true;
    }

    public boolean toLeftDiagonal(int i, int j, int sign, int howManyInLine) {
        int startJ = j;
        for(int start = i; i < start + howManyInLine; i++, j--)
            if(i >= board.length || j < 0 || board[i][j] != sign)
                return false;
        return true;
    }

    public boolean gameOver() {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board.length; j++) {
                if(toRigth(i, j, CROSS, board.length))
                    return true;
                if(toDown(i, j, CROSS, board.length))
                    return true;
                if(toRightDiagonal(i, j, CROSS, board.length))
                    return true;
                if(toLeftDiagonal(i, j, CROSS, board.length))
                    return true;
                if(toRigth(i, j, CIRCLE, board.length))
                    return true;
                if(toDown(i, j, CIRCLE, board.length))
                    return true;
                if(toRightDiagonal(i, j, CIRCLE, board.length))
                    return true;
                if(toLeftDiagonal(i, j, CIRCLE, board.length))
                    return true;
            }
        }

        return false;
    }

    @Override
    public String toString() {
        String s = "";

        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                if(board[i][j] == CROSS)
                    s += "X";
                if(board[i][j] == CIRCLE)
                    s += "O";
                if(board[i][j] == EMPTY)
                    s += " ";
                s += "|";
            }
            s += "\n";
            if(i < board.length - 1) {
                for(int k = 0; k < board.length * 2; k++)
                    s += "-";
            }
            s += "\n";
        }
        s += "Evaluation " + evaluation + "\n";
        s += "TotalEvaluation " + totalEval + "\n";
        s += "Dobry ";
        if(stamp == CROSS)
            s += " X\n";
        else
            s += " O\n";

        return s;
    }

}

And I construct a tree from that nodes:

package tictactoe;

import static tictactoe.Field.*;

import java.awt.GridLayout;
import java.io.IOException;
import java.util.ArrayList;

import javax.swing.JFrame;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;

public class Tree {
    Node root;
    GameBoard gameBoard;
    Player player;

    public Tree(GameBoard gameBoard, Player player) {
        this.gameBoard = gameBoard;
        this.player = player;
        addNodes();
    }

    public void addNodes() {
        if(root == null)
            root = new Node(toIntArray(gameBoard.getFields()), 0, player.getStamp(), null);
        addChildren(root);
    }

    public void addChildren(Node parent) {
        if(parent.level < 5 && !parent.gameOver()) {
            for(int i = 0; i < parent.board.length; i++) {
                for(int j = 0; j < parent.board.length; j++) {
                    if(parent.board[i][j] == EMPTY) {
                        int[][] copy = hardCopy(parent.board);
                        int stamp = 0;
                        if(parent.level % 2 == 0)
                            stamp = CROSS;
                        else
                            stamp = CIRCLE;

                        copy[i][j] = stamp;
                        Node child = new Node(copy, parent.level + 1, player.getStamp(), parent);
                        System.out.println(stamp);
                        parent.children.add(child);
                        addChildren(child);
                    }
                }
            }
        }
    }

    public int[][] getBestMove() {
        System.out.println("----------");
        ArrayList<Node> childrenList = getBestNode(root, new ArrayList<Node>());
        ArrayList<Node> track = new ArrayList<Node>();
        System.out.println("ROZMIAR: " + childrenList.size());
        Node bestChild = null;
        int max = Integer.MIN_VALUE;
        for(Node node : childrenList)
            if(node.evaluation > max) {
                max = node.evaluation;
                bestChild = node;
            }
        System.out.println("NAJLEPSZY");
        System.out.println(bestChild);

        //znajdowanie przodka
        Node moveToDo = bestChild;
        while (moveToDo.parent.parent != null) {
            track.add(0, moveToDo);
            moveToDo = moveToDo.parent;
        }
        track.add(0, moveToDo);
        track.add(0, moveToDo.parent);
        System.out.println(moveToDo);
        ///
        JFrame jf = new JFrame();
        jf.setLayout(new GridLayout());
        JTextArea jta = new JTextArea(track.toString());
        JScrollPane jsp = new JScrollPane(jta, JScrollPane.VERTICAL_SCROLLBAR_ALWAYS, JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
        jf.add(jsp);
        jf.setVisible(true);
        jf.setLocation(600, 0);
        jf.pack();

        ////

        return moveToDo.board;
    }

    public ArrayList<Node> getBestNode(Node node, ArrayList<Node> childrenList) {
        for(Node n : node.children) {
            getBestNode(n, childrenList);
            if(n.children.size() == 0)
                childrenList.add(n);
        }
        return childrenList;
    }

    public void print(Node node) {
        System.out.println(node);
        for(Node n : node.children)
            print(n);
    }

    public static int[][] hardCopy(int[][] t) {
        int[][] copy = new int[t.length][t.length];
        for(int i = 0; i < t.length; i++) {
            for(int j = 0; j < t.length; j++) {
                copy[i][j] = t[i][j];
            }
        }
        return copy;
    }
}

Answer 1

As described here, the best move is chosen by either maximizing or minimizing the recursively calculated valued of the turn, depending on whether it is the turn of player one or player two. This means that in each evaluation, the algorithm alternatively takes the perspective of the two players and selecting an optimal move. This detail could be implemented by always maximizing the value, multiplying with a factor of 1 or -1 depending on the player, as only values of 1, 0 and -1 can occur for the moves.

Furthermore, pruning can be used; this means that evaluation can be stopped as soon as a move is found which is optimal for the current player, i.e. of value 1 or -1 is found, respectively.