01/10/2018, 16:05
Nhờ giải thích thuật minimax hay alpha-beta
Giải thích thuật toán game caro. Mọi người có thể giải thích giúp em là thuật toán bên dưới sử dụng minimax hay alphaBeta được không ạ. Em cảm ơn mọi người
public Point search(BanCo bb) {
BanCo b = new BanCo(BanCo.getSize());
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b.getBanCo()[i][j] = bb.getBanCo()[i][j];
}
}
danhGiaTungBanCo(b, 2);
ArrayList<VanCo> list = new ArrayList<VanCo>();
for (int i = 0; i < maxBanCo; i++) {
list.add(getMaxBanCo());
}
int maxp = Integer.MIN_VALUE;
ArrayList<VanCo> ListChoose = new ArrayList<VanCo>();
for (int i = 0; i < list.size(); i++) {
b.getBanCo()[list.get(i).getDiem().x][list.get(i).getDiem().y] = 2;
int t = MinValue(b, Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
if (maxp < t) {
maxp = t;
ListChoose.clear();
ListChoose.add(list.get(i));
} else if (maxp == t) {
ListChoose.add(list.get(i));
}
b.getBanCo()[list.get(i).getDiem().x][list.get(i).getDiem().y] = 0;
}
int x = rand.nextInt(ListChoose.size());
return ListChoose.get(x).getDiem();
}
// Danh gia cho max AI
private int MaxValue(BanCo b, int alpha, int beta, int depth) {
int val = evaluationBoard(b);
if (depth >= doSau || Math.abs(val) > 3000) {
return val;
}
danhGiaTungBanCo(b, 2);
ArrayList<VanCo> list = new ArrayList<VanCo>();
for (int i = 0; i < maxBanCo; i++) {
list.add(getMaxBanCo());
}
for (int i = 0; i < list.size(); i++) {
b.getBanCo()[list.get(i).getDiem().x][list.get(i).getDiem().y] = 2;
alpha = Math.max(alpha, MinValue(b, alpha, beta, depth + 1));
b.getBanCo()[list.get(i).getDiem().x][list.get(i).getDiem().y] = 0;
if (alpha >= beta) {
break;
}
}
return alpha;
}
// Danh gia cho max (Nguoi choi)
private int MinValue(BanCo b, int alpha, int beta, int depth) {
int val = evaluationBoard(b);
if (depth >= doSau || Math.abs(val) > 3000) {
return val;
}
danhGiaTungBanCo(b, 1);
ArrayList<VanCo> list = new ArrayList<VanCo>();
for (int i = 0; i < maxBanCo; i++) {
list.add(getMaxBanCo());
}
for (int i = 0; i < list.size(); i++) {
b.getBanCo()[list.get(i).getDiem().x][list.get(i).getDiem().y] = 1;
beta = Math.min(beta, MaxValue(b, alpha, beta, depth + 1));
b.getBanCo()[list.get(i).getDiem().x][list.get(i).getDiem().y] = 0;
if (alpha >= beta) {
break;
}
}
return beta;
}
Bài liên quan
alpha-beta la phien ban nang cap cua minmax thoi, dùng để tỉa bớt 1 số nhánh k cần thiết
Bạn có thể giải thích cụ thể xíu cho mình được không bạn.
hic, cho bạn cái link này https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/
Cảm ơn bạn nhiều nha