AlphaBeta(node, depth, ?, ß, maximizingPlayer): ha depth == 0 vagy node terminális állapot: térj vissza node értéke ha maximizingPlayer: maxEval = -? minden child in node gyerekei: eval = AlphaBeta(child, depth-1, ?, ß, False) maxEval = max(maxEval, eval) ? = max(?, eval) ha ß ? ?: törés // Vágás térj vissza maxEval különben: minEval = +? minden child in node gyerekei: eval = AlphaBeta(child, depth-1, ?, ß, True) minEval = min(minEval, eval) ß = min(ß, eval) ha ß ? ?: törés // Vágás térj vissza minEval
def alpha_beta(node, depth, alpha, beta, maximizing_player, evaluate, get_children):
if depth == 0 or node.is_terminal():
return evaluate(node)
if maximizing_player:
max_eval = float('-inf')
for child in get_children(node):
eval = alpha_beta(child, depth - 1, alpha, beta, False, evaluate, get_children)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Vágás
return max_eval
else:
min_eval = float('inf')
for child in get_children(node):
eval = alpha_beta(child, depth - 1, alpha, beta, True, evaluate, get_children)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Vágás
return min_eval
# Példa dummy osztályokkal
class Node:
def __init__(self, value=None, children=None):
self.value = value
self.children = children if children else
def is_terminal(self):
return self.value is not None
def evaluate(node):
return node.value
def get_children(node):
return node.children
# Példa játékfa
tree = Node(children=[
Node(value=3),
Node(children=[
Node(value=5),
Node(value=6),
]),
Node(children=[
Node(value=7),
Node(value=4),
])
])
result = alpha_beta(tree, depth=3, alpha=float('-inf'), beta=float('inf'), maximizing_player=True, evaluate=evaluate, get_children=get_children)
print("Legjobb érték:", result)
Kimenet:
Legjobb érték: 7
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct Node {
int value;
vector<Node*> children;
Node(int val = 0) : value(val) {}
bool is_terminal() const {
return children.empty();
}
};
int alpha_beta(Node* node, int depth, int alpha, int beta, bool maximizing_player) {
if (depth == 0 || node->is_terminal()) {
return node->value;
}
if (maximizing_player) {
int max_eval = numeric_limits<int>::min();
for (Node* child : node->children) {
int eval = alpha_beta(child, depth - 1, alpha, beta, false);
max_eval = max(max_eval, eval);
alpha = max(alpha, eval);
if (beta <= alpha) {
break; // Vágás
}
}
return max_eval;
} else {
int min_eval = numeric_limits<int>::max();
for (Node* child : node->children) {
int eval = alpha_beta(child, depth - 1, alpha, beta, true);
min_eval = min(min_eval, eval);
beta = min(beta, eval);
if (beta <= alpha) {
break; // Vágás
}
}
return min_eval;
}
}
int main() {
// Példa játékfa
Node* root = new Node();
root->children.push_back(new Node(3));
Node* branch1 = new Node();
branch1->children.push_back(new Node(5));
branch1->children.push_back(new Node(6));
root->children.push_back(branch1);
Node* branch2 = new Node();
branch2->children.push_back(new Node(7));
branch2->children.push_back(new Node(4));
root->children.push_back(branch2);
int result = alpha_beta(root, 3, numeric_limits<int>::min(), numeric_limits<int>::max(), true);
cout << "Legjobb érték: " << result << endl;
return 0;
}
Kimenet:
Legjobb érték: 7
Az alfa-béta vágás kulcsfontosságú a mesterséges intelligenciában, különösen kétjátékos stratégiai játékok fejlesztésekor (pl. sakk, dáma, amőba).