Trò chơi & AI

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 1)

Trò chơi & AI

Minimax with Alpha-Beta Pruning

Thời gian (Time) O(b^m)
Không gian (Space) O(m)

Mô tả nguyên lý

Thuật toán quyết định cho trò chơi đối kháng hai người, cắt tỉa các nhánh không cần thiết.

Cài đặt mẫu (Implementation)

function alphaBeta($node, $depth, $alpha, $beta, $isMax) {
    if ($depth == 0) return evaluate($node);
    if ($isMax) {
        $value = -INF;
        foreach (getChildren($node) as $child) {
            $value = max($value, alphaBeta($child, $depth - 1, $alpha, $beta, false));
            $alpha = max($alpha, $value);
            if ($alpha >= $beta) break;
        }
        return $value;
    }
}