Trò chơi & AI
Minimax with Alpha-Beta Pruning
ID: #58
Xem trên trang chủ
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;
}
}