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;
	}
Alone viết 18:22 ngày 01/10/2018

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

Chiện Nguyễn viết 18:11 ngày 01/10/2018

Bạn có thể giải thích cụ thể xíu cho mình được không bạn.

Alone viết 18:14 ngày 01/10/2018

hic, cho bạn cái link này https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/

Chiện Nguyễn viết 18:18 ngày 01/10/2018

Cảm ơn bạn nhiều nha

Bài liên quan
0