极大/小搜索，alpha/beta剪枝

本文主要是介绍极大/小搜索，alpha/beta剪枝，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 剪枝min层剪去beta最小得分比alpha最大得分还要小的得分，如果alpha是8，beta比8小的节点都剪掉，因为max层，只会选最大的
2. 剪枝max层剪去比alpha最大得分比beta最小得分还要大的得分，如果beta是8，alpha比8的节点都需要剪掉，因为min层只会选最小的

     let board = [
            ['', '', ''],
            ['', '', ''],
            ['', '', '']
        ];

        let w; // = width / 3;
        let h; // = height / 3;

        let ai = 'X';
        let human = 'O';
        let currentPlayer = human;

        function setup() {
            createCanvas(400, 400);
            w = width / 3;
            h = height / 3;
            bestMove();
        }

        function equals3(a, b, c) {
            return a == b && b == c && a != '';
        }

        function checkWinner() {
            let winner = null;

            // horizontal
            for (let i = 0; i < 3; i++) {
                if (equals3(board[i][0], board[i][1], board[i][2])) {
                    winner = board[i][0];
                }
            }

            // Vertical
            for (let i = 0; i < 3; i++) {
                if (equals3(board[0][i], board[1][i], board[2][i])) {
                    winner = board[0][i];
                }
            }

            // Diagonal
            if (equals3(board[0][0], board[1][1], board[2][2])) {
                winner = board[0][0];
            }
            if (equals3(board[2][0], board[1][1], board[0][2])) {
                winner = board[2][0];
            }

            let openSpots = 0;
            for (let i = 0; i < 3; i++) {
                for (let j = 0; j < 3; j++) {
                    if (board[i][j] == '') {
                        openSpots++;
                    }
                }
            }

            if (winner == null && openSpots == 0) {
                return 'tie';
            } else {
                return winner;
            }
        }

        function mousePressed() { 
            if (currentPlayer == human) {
                // Human make turn
                let i = floor(mouseX / w);
                let j = floor(mouseY / h);
                // If valid turn
                if (board[i][j] == '') {
                    board[i][j] = human;
                    currentPlayer = ai;
                    bestMove();
                }
            }
        }

        function draw() {
            background(255);
            strokeWeight(4);

            line(w, 0, w, height);
            line(w * 2, 0, w * 2, height);
            line(0, h, width, h);
            line(0, h * 2, width, h * 2);

            for (let j = 0; j < 3; j++) {
                for (let i = 0; i < 3; i++) {
                    let x = w * i + w / 2;
                    let y = h * j + h / 2;
                    let spot = board[i][j];
                    textSize(32);
                    let r = w / 4;
                    if (spot == human) {
                        noFill();
                        ellipse(x, y, r * 2);
                    } else if (spot == ai) {
                        line(x - r, y - r, x + r, y + r);
                        line(x + r, y - r, x - r, y + r);
                    }
                }
            }

            let result = checkWinner();
            if (result != null) {
                noLoop();
                let resultP = createP('');
                resultP.style('font-size', '32pt');
                if (result == 'tie') {
                    resultP.html('Tie!');
                } else {
                    resultP.html(`${result} wins!`);
                }
            }
        }

    function bestMove() {
            // bestMove AI要下棋的位置
            let bestScore = -Infinity;
            let move;
            for (let i = 0; i < 3; i++) {
                for (let j = 0; j < 3; j++) {
                    if (board[i][j] == '') {
                        // 随便找一个空位置下
                        board[i][j] = ai;
                        // 使用minmax计算一下下这个空位置的得分怎么样
                        let score = minimax(board, 0, false);
                        // 计算完得分后将位置还原
                        board[i][j] = '';
                        // 如果当前得分大于最佳得分
                        if (score > bestScore) {
                            // 记录最佳得分
                            bestScore = score;
                            // 记录最佳得分位置
                            move = { i, j };
                        }
                    }
                }
            }
            // 移动到最近得分位置
            board[move.i][move.j] = ai;
            // 切换角色
            currentPlayer = human;
        }

        let scores = {
            X: 1,
            O: -1,
            tie: 0
        };

        function minimax(board, depth, isMaximizing, alpha = -Infinity, beta = Infinity) {
            let result = checkWinner();
            if (result !== null) {
                // 如果是x赢了就返回1，如果是o赢了返回-1，如果是平局返回0
                return scores[result];
            }
            if (isMaximizing) {
                // max层假设是玩家下的时候
                for (let i = 0; i < 3; i++) {
                    for (let j = 0; j < 3; j++) {
                        if (board[i][j] == '') {
                            // 假设ai下的位置
                            board[i][j] = ai;
                            let score = minimax(board, depth + 1, false, alpha, beta);
                            board[i][j] = '';
                            // 1. 计算最低得分中最大的
                            alpha = max(score, alpha);
                            // 2. min层只选最小的，如果比最小的还大直接剪枝
                            // beta是min的上限，当前节点的最低得分里面的最大(alpha)已经大于了之前最小得分，直接剪枝
                            if (alpha >= beta) return alpha
                        }
                    }
                }
                // 返回min里面最大的那个
                return alpha
            } else {
                // min层假设是ai玩家下的时候
                for (let i = 0; i < 3; i++) {
                    for (let j = 0; j < 3; j++) {
                        if (board[i][j] == '') {
                            board[i][j] = human;
                            let score = minimax(board, depth + 1, true, alpha, beta);
                            board[i][j] = '';
                            // 1. 计算最低得分
                            beta = min(beta, score)
                            // 2. max层只选最大的，比max层小的不用比较
                            // alpha代表的是max的下限，如果现在计算的最低得分比之前节点计算的最低得分要小直接剪枝
                            if (alpha >= beta) return beta
                        }
                    }
                }
                // 返回最低得分
                return beta
            }
        }

这篇关于极大/小搜索，alpha/beta剪枝的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！