.:: CODE SNIPPET ::.

"Your time is limited, so don't waste it living someone else's life"

Giải quyết bài 8 quân hậu bằng giải thuật Min-Max


1. Giải thuật
Ứng dụng giải thuật Min-Max
Thuật toán Minmax hay còn gọi là Minimax là một thuật toán dùng trong tìm kiếm có đối thủ. Cải tiến của thuật toán này là thuật toán cắt tỉa Alpha-Beta (Alpha – Beta Pruning) rất hay được sử dụng làm chiến lược cho tìm kiếm nước đi trong không gian tìm kiếm của trò chơi có tính chất đối kháng (vd cờ Tướng, cờ Vua, cờ caro… ). Nói một cách dễ hiểu, thì ý nghĩa của thuật toán này bạn có thể hiểu một cách đơn giản như sau: Giả sử bạn đang đánh cờ với máy, thì cả bàn cờ sẽ được biểu diễn trong một cái gọi là không gian trạng thái (KGTT) – bạn có thể hình dung KGTT chính là cách mà máy tính biểu diễn bàn cờ thực lên bộ nhớ máy tính. Với mỗi nước đi (mỗi thay đổi) sẽ làm cho KGTT của bàn cờ thay đổi thành một KGTT mới. Như vậy, đến nước đi của máy. Chiến lược tìm kiếm nước đi Minimax sẽ được sử dụng để làm sao tìm ra nước đi tốt nhất cho máy. Để có được nước đi tốt thì cần có một sự lượng giá tốt – là kết quả từ một hàm lượng giá (tức là cách đánh giá, như lúc mình tính ở trong đầu í == độ uyên thâm). Độ sâu (depth) là số nước mà máy sẽ tính trước. Như vậy giả sử với độ sâu là 4 thì sẽ tìm với tầm nhìn là 4 nước đi. Nút có kết quả lượng giá cao nhất ở mức gốc (mức 0) sẽ được chọn để đi (trong hình ở mức 0 chỉ có 1nút thôi, nên bạn hình dung là như vậy).


Mức 0, 2, 4 là lượt đi của máy – mức MAX (kết quả lượng giá càng lớn càng tốt).
Mức 1, 3 là lượt đi của người – mức MIN (kết quả lượng giá càng nhỏ càng tốt).
2. Áp dụng giải thuật Minmax vào bài toán 8 quân hậu

Giải quyết bài toán bằng thuật toán 8 quân hậu cho là khá dễ dàng. Trước tiên, chú ý rằng trên mỗi hàng bàn cờ, chúng ta chỉ có thể đặt duy nhất một quân hậu. Như vậy thì chứng tỏ 8 quân hậu sẽ được đặt ở 8 hàng của bàn cờ. Như vậy ta xem như sau, mỗi quân hậu sẽ chỉ được duyệt trên tất cả các cột của bàn cờ tại dòng mà quân hậu đó đang được đứng, sau đó, chọn ra một cột nào đấy sẽ là kết quả di chuyển của nó. Cột mà ta chọn sẽ thõa mãn một điều kiện nào đấy mà giải thuật MinMax cung cấp.
Giải thuật cung cấp cho chúng ta điều gì?
Giải thuật cho chúng ta hai hàm để giúp chúng ta lựa chọn cột:
 Tổng số các ô còn có thể đặt quân hậu còn lại (sau khi đặt quân hậu vào một vị trí nào đó).
 Trên những dòng còn lại (sau khi đặt quân hậu) thì số vị trí còn có thể đặt quân hậu ít nhất là bao nhiêu?
Giả sử ta đang xét tại hàng số 4. Trong bàn cờ chúng ta đã đặt vào 3 con hậu rồi, giờ ta xét đến dòng số 4.
Tại dòng này có tổng cộng 3 cột có thể được chọn để đặt quân hậu vào. Đó là A, B, C như hình dưới.
Giả sử ta chọn vị trí đặt hậu là A, thì sau đấy, ta xét trên các dòng số 5, 6, 7, 8. Theo như hai công thức của Minmax ta sẽ tính:

Tổng số ô còn lại để đặt quân hậu: 8
Số ô đặt quân hậu nhỏ nhất còn lại: 1
Tương tự đối với các vị trí B, C. Từ đấy ta có:
F1(O): F1(A)=8, F1(B)= 9, F1(C)=10 =>Max F1(O) là C
F2(O): F2(A)=1, F2(B)=1, F2(C)=2 =>Max F2(O) là C
Như vậy ta sẽ chọn ô C làm ô đặt quân hậu.
Tuy nhiên không phải lúc nào cũng có thể tính ra được các số thuận lợi như vậy. Nhiều khi Max(F1) không tương ứng với Max(F2), và đôi khi còn có trường hợp các giá trị của một hàm tính ra còn giống nhau nữa.Trong hai trường hợp đó ta sẽ làm như sau:
Trường hợp Max F1 không đúng như Max F2: trường hợp này ta sẽ tính theo công thức
Max ((f1+f2)/2)
nghĩa là sẽ tính lần lượt các giá trị của các vị trí A, B, C theo công thức trên, sau đó so sánh các giá trị này để tìm ra kết quả(Chú ý: nếu lấy càng nhiều chữ số sau phần thập phân thì phép so sánh sẽ dễ chính xác hơn)
Trường hợp các giá trị của cùng một hàm tính ra giống nhau thì chúng ta sẽ lấy giá trị ở giữa nếu số lần trùng là lẻ, còn nếu là chẵn thì lấy vị trí lớn hơn.
Sau đây là cách giải quyết bài toán bằng ngôn ngữ java, ide eclipse
Đầu tiên là hàm tính tổng các ô có thể đặt con hậu trên bàn cờ

//hàm F1: tổng số ô có thể đặt quân hậu còn lại của bàn cờ
private int F1(int[][] arr,int chkRow){
	int mark=0;
	for(int i=chkRow+1;i<8;i++){
		for(int j=0;j<8;j++){
			if(arr[i][j]==0){
				mark++;
			}
		}
	}
	return mark;
}

Tiếp theo là hàm tính số vị trí có thể đặt quân hậu trên một dòng ít nhất.

private int F2(int[][] arr,int chkRow){
	if(chkRow==7)
		return 0;
	int min=8;
	for(int i=chkRow+1;i<8;i++){
		int dem=0;
		for(int j=0;j<8;j++){
			if(arr[i][j]==0){
				dem++;
			}
		}
		if(dem<min){
			min=dem;
		}
	}
	return min;
}

Hàm quan trọng nhất là hàm xử lý thuật toán MinMax

                /*
		 *  _ _ _ _ _ _ _ _ 
		 * |_|_|x|_|_|_|_|_|  -->(số cột)
		 * |x|_|_|_|_|_|_|_| |
		 * |_|_|_|_|_|_|x|_| V(số dòng)
		 * |_|_|_|_|x|_|_|_|
		 * |_|_|_|_|_|_|_|x|
		 * |_|x|_|_|_|_|_|_|
		 * |_|_|_|x|_|_|_|_|
		 * |_|_|_|_|_|x|_|_|
		 */*/
public void Generate(){
	for(int rowIndex=0;rowIndex<8;rowIndex++){
		//Kiểm tra xem đối với mỗi dòng thì có lời giải là một cột nào được chọn ra hay chưa?
		//nếu chưa có thì lo mà đi tìm lời giải(tìm cột nào được chọn)
		//còn có rồi chuyển qua dòng tiếp theo
		boolean flag=true;
		for(int test=0;test<8;test++){
			if(boardChess[rowIndex][test]==1){
				flag=false;
				break;
			}
		}
		if(flag==false){
			continue;
		}
		//tạo một mảng chứa các cột có thể đi được của dòng đang xét
		int[] availCols=new int[]{-1,-1,-1,-1,-1,-1,-1,-1};
		float[] colValues=new float[]{-1,-1,-1,-1,-1,-1,-1,-1};
		for(int kt=0;kt<8;kt++){
			if(boardChess[rowIndex][kt]==0){//có thể đặt quân hậu
				availCols[kt]=0;
			}
		}
		
		//đối với từng vị trí có thể đặt quân hậu trên bàn cờ
		//sẽ tính hai hàm ước lượng của nó
		//hàm F1: tổng số ô có thể đặt quân hậu còn lại của bàn cờ
		//hàm F2: số vị trí có thể đặt quân hậu trên một dòng ít nhất
		int[] valsF1=new int[]{-1,-1,-1,-1,-1,-1,-1,-1};
		int[] valsF2=new int[]{-1,-1,-1,-1,-1,-1,-1,-1};
		double[] valsF=new double[]{-1,-1,-1,-1,-1,-1,-1,-1};
		for(int cl=0;cl<8;cl++){
			if(availCols[cl]==0){
				int[][] arrTemp=arrCopy();
				arrTemp[rowIndex][cl]=1;//đặt quân hậu vào mảng giả
				PutAQueenOnBoard(arrTemp, rowIndex, cl);//cập nhật lại mảng giả arrTemp
				//tiếp tục tính các hàm ước lượng ở đây
				int f1=F1(arrTemp,rowIndex);
				int f2=F2(arrTemp,rowIndex);
				//availCols[cl]=(int)(f1+f2)/2;
				valsF1[cl]=f1;
				valsF2[cl]=f2;
				//valsF[cl]=Math.round(((f1+f2)/2)*100)/100f;
				double value = (double)(f1+f2)/2;
				valsF[cl]=(double)Math.round(value * 1000) / 1000;
			}
		}
		int choosenPos=0;
		choosenPos=GetMaxPos(valsF);
	
		//đặt quân hậu vào vị trí đã tìm được
		boardChess[rowIndex][choosenPos]=1;
		PutAQueenOnBoard(boardChess, rowIndex, choosenPos);
	}
}

Trong đó, chúng ta dùng đến hàm lấy giá trị lớn nhất của mảng một chiều, hàm này được viết thêm phần xử lý trường hợp ngoại lệ đã mô tả ở trên.

//Trả về vị trí có giá trị lớn nhất trong mảng một chiều
private int GetMaxPos(double[] arr){
	int max=0;
	int dem=0;
	for(int i=1;i<8;i++){
		if(arr[i]>=arr[max]){
			max=i;
		}
	}
	for(int j=0;j<8;j++){
		if(arr[j]==arr[max]){
			dem++;
		}
	}
	if(dem%2==1){
		dem=dem/2;
		int dem1=0;
		for(int r=0;r<8;r++){
			if(arr[r]==arr[max]){
				dem1++;
				if(dem1==dem+1){
					max=r;
					break;
				}
			}
		}
		return max;
	}
	
	return max;
}

(prmhuitedu)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: