TIN TỨC CẬP NHẬT

Tổng quan về các bài toán trò chơi đối kháng

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Tổng quan về các bài toán trò chơi đối kháng

Bài gửi by pkt_zz on 13/6/2010, 3:39 am

Nguồn: [You must be registered and logged in to see this link.]
Các trò chơi đối kháng giữa hai người đã được hình thành từ lâu. Và những người chơi luôn cố gắng tìm mọi cách để mình giành được phần thắng. Và bạn có biết rằng các trò chơi đã được đoán trước là thắng, thua hay hoà không? Ý tôi muốn nói rằng, nếu một trò chơi cho trước vị trí ban đầu thì kết quả tốt nhất mà người chơi đầu tiên đạt được đã được biết từ trước(ở đây tôi giả thiết cả hai người chơi đều chơi tối ưu). Vấn đề là các trò chơi thường quá phức tạp lên không có một ai có thể đảm bảo rằng mọi nước đi của mình là tối ưu. Do vậy cho đến nay, chỉ một số lượng nhỏ bài toán đó đã được giải quyết. Và trong bài viết này tôi xin giới thiệu một cách khá đầy đủ về trò chới đối kháng hai người. Bài toán đó được phát biểu tổng quát dưới dạng đồ thị như sau:
Cho đồ thị có hướng G=(V,E) (Đồ thị G có tập đỉnh V, tập cạnh là E). Với mỗi đỉnh v Î V, ta định nghĩa E(v) = { u | (v,u) Î E }

Một trò chơi hai người được định nghĩa là một đồ thị có hướng G = (V, E) trong đó mỗi trạng thái chơi tương ứng với một đỉnh của đồ thị, hàm E(v) là qui tẵc chơi tức là E(v) chứa các đỉnh hay trạng thái chơi mà từ v có thể đi đến. Hai người luân phiên nhau đi , ở thế chơi u người chơi chỉ có thể đi sao cho nước v nhận được thoả mãn v Î E(u). Trò chơi kết thúc khi đến lượt đấu mà không thể đi tiếp được nữa. (Thông thường thì người không thể đi tiếp là người thua cuộc).
Tôi xin chia bài toán này thành hai loại bài toán: loại thứ nhất là, mỗi trạng thái chơi chỉ có một đối tượng mỗi đối tượng là một đỉnh của đồ thị. Loại thứ hai là mỗi trạng thái chơi có nhiều đối tượng. (Sự khác nhau căn bản các bạn sẽ được rõ ở phần sau).

I. Loại thứ nhất:
P1. Xét bài toán cụ thể - GAME
Một trò chơi đối kháng giữa hai người A và B diễn ra như sau: Hai người luôn phiên nhau điều khiển một con tốt theo một số con cho trước. Một người có thể di chuyển con tốt từ vị trí u đến v nếu có một đường nối trực tiếp có hướng từ u đến v. Trò chơi kết thúc không thể tiếp tục di chuyển. Người không thể tiếp tục đi là người thua cuộc. Hỏi nếu cho trước vị trí ban đầu và danh sách các đường nối hỏi người đi trước thắng hay ngươì đi sau thắng hay hoà? Giả hai người này rất thông minh các bước đi của họ là tối ưu (tức học không bao giờ đi các nước không có loại cho mình).
Input: Game.In
- Dòng đầu ghi số N là số vị trí con tốt có thể đừng, và số M là số đường đi (có hướng) mà con tốt có thể đi (1≤ N ≤ 200, 1 ≤ M ≤ N*(N-1)).
- Dòng thứ hai ghi u là trạng thái bắt đầu.
- M dòng tiếp theo mỗi dòng ghi hai số u, v mô tả một đường đi từ u đến v.
Output: Game.Out
- Ghi một số duy nhất 1, 2, hoặc 0. 1 nghĩa là người 1 thắng, 2 là người hai thắng, 0 là hoà.
Nhận xét:
- Những vị trí không có đường ra thì chắc chắn sẽ thua.
- Những vị trí nào có một đường ra nối với vị trí chắc chắn thua thì chắc chắn thắng.
- Những vị trí nào tất đường ra nối với các vị trí chắc chắn thắng thì chắc chắn thua.
- Những vị trí nào mà trạng thái thắng thua không thể xác định thì là vị trí hoà.- Bài toán có trạng thái hoà: VD: có các đường nối 1 → 2, 2 → 3, 3 → 1, 1 → 4, 4 → 5.Các vị trí 1,2,3 sẽ hòa, 5 thua, 4 thắng.
Thuật toán:
- Lúc đầu coi tất cả các vị trí v đều hoà gán giá trị đỉnh F[v] = 0. Tìm các vị trí không có đường ra thì gán lại F[v] = 2 (tức là nếu người chơi ở vị trí này sẽ thua). - Khi thay trạng thái một vị trí từ hoà sang thắng hoặc thua thì kiểm tra các vị trí có đường đi đến nó: Những vị trí u nào có một đường ra nối với vị trí v chắc chắn thua (F[v] = 2) sẽ thì chắc chắn thắng (thay F[u] = 1); Những vị trí u nào tất đường ra nối với các vị trí v (F[v] = 1) chắc chắn thắng thì chắc chắn thua (thay F[u] = 2).
- Quá trình này ngừng khi không có sự chuyển trạng nào nữa.
Chương trình mô tả thuật toán:


Code:


Procedure gan_nhan (u: byte);
Var td, v : byte;
Begin
td := 0;
If Noi_dinh_thuău) then td := 1 Else
If Noi_toan_dinh_thang_hoac_khong_co_dinh_ra (u) Then td := 2;
F[u] := td;
If td <> 0 Then
For v := 1 to N do
If F[v] = 0 Then
If C[v, u] Then gan_nhan (td);
End;

Procedure Main;
Var u : Integer;
Begin
Fillchar (F, sizeof (F), 0);
For u := 1 to N do
If Khong_Co_Canh_Ra (u) Then Gan_nhan(u);
End;
P2. (Bài tập tự giải) LGAME (BOI 2002) Cho một bảng kích thước 4*4 ô vuông, trên đó đặt hai thanh thước thợ hình L kích thước 4 ô vuông và hai hình tròn như hình vẽ, các hình này nằm trên bảng và không được đè lên nhau. Hình kẻ ca rô là của người chơi A, hình kẻ sọc của người chơi B. Hai người sẽ chơi luôn phiên, tại mỗi nước đi, một người sẽ phải nhấc thanh hình L của mình lên, xoay, lật tuỳ ít và di chuyển đến vị trí mới (khác ít nhất một ô so với vị trí ban đầu), như vậy hình đầu tiên có hai cách di chuyển. Và người chơi có thể thực hiện thêm một bước đi không bắt buộc là di chuyên một ô tròn đến một ô mới.
Trò chơi kết thúc khi không thể di chuyển được nữa, người không thể di chuyển được sẽ thua cuộc. Tuy nhiên, trò chơi vẫn có thể hoà vì trong trạng đó cả hai người đều không muốn thua.

Yêu cầu: Cho một trạng thái trò chơi, hỏi trò chơi đó sẽ kết thúc như thế, (hoà, A thắng hay B thắng, ở đây A là người đi trước)
Input: Lgame.In
- Gồm 4 dòng mỗi dòng ghi 4 kí tự, ‘.’ thể hiện ô trống(có 6 ô), ‘x’ là ô chứa miếng hình tròn (2 ô), ‘#’ biều thị ô bị miếng hình L của người chơi A đặt lên (có 4 ô), còn lại bốn ô biểu thị ô bị miếng hình L của người chơi B đặt lên.
Output:Lgame.out
- Có ba trường hợp:
+ A thắng: ghi trạng thái sau khi A đi nước đI đầu tiên dẫn đến trạng tháI thắng đó.
+ A thua: ghi ra xâu “No winning move Losing”.
+ Hoà: ghi ra xâu “No winning Draw”.

Gợi ý: Có không quá 18 000 trạng thái, giải bằng Freepascal.
Bổ xung:Đôi khi không phải lúc nào cũng có thể lưu được tất cả các trạng thái vì có một số bài toán có số trạng thái rất lớn. Vì vậy, thay vì tính trạng thái thắng thua hiện thời ta thay bằng trạng thái tương đương có cùng tính chất thắng thua.
Khái niệm: trạng thái A được gọi là tương đương với B khí và chỉ khi A và B có cùng thắng, cùng thua hoặc cùng hoà.
Để hiểu sâu hơn ta xét một bài toán cụ thể:

Stones (ACM)
Một trò chơi bốc sỏi diễn ra trên một bảng ngang kích thước 1*N ô vuông. Trên một số ô có đặt một số viên sỏi. Tại một bước đi người cầm một viên sỏi ở một ô và di chuyển viên sỏi sang bên trái một hoặc hai ô với điều kiện là ô di chuyển tới phải không có sỏi và đường di chuyển không được qua ô có sỏi. Người nào không di chuyển được sẽ là người thua cuộc. Cho trước trạng thái ban đầu hỏi người di trước có bao nhiêu nước đi đầu tiên mà người thứ luôn thua với giả thiết cả hai người đều chơi tối ưu.
Input: Stones.in
- Dòng đầu ghi số N(1 ≤ N ≤ 50).
- Dòng thứ hai ghi một xâu gồm N kí tự thể hiện trạng thái lúc bắt đầu trò chơi, ‘.’ thể hiện ô trống, ‘X’ thể hiện có sỏi (số viên sỏi không vượt quá 10).
Output: Stones.out
- Ghi một số là số đi mà có thể thắng.

Nhận xét:- Nếu coi mỗi trạng thái là một đỉnh đồ thị rõ ràng bài toán theo lý thuyết có thể tính được kết quả cần tính. Nhưng trên thực tế số trạng thái rất lớn(có thể lên đến Tổ hợp chập 10 của 50 phần tư). Như vậy bài toán không thể lập trình được vì thiếu bộ nhớ và tốc độ tính toán rất chập. - Vì vậy người ta đã nghĩ ra một cách giảm số lượng trạng thái đang xét xuống. Đầu tiên ta thấy trạng thái của người chơi được đặc trưng bởi tập có thứ tự ở đằng trước các ô tự do của mỗi viên sỏi Ví dụ: xâu “...XX.X” ↔ {3, 0, 1}. Nếu cứ để như vậy thì không giải quyết được và thay vì xét sự thắng thua của dãy đó ta xét sự thắng thua của dãy khi lấy đồng dư 3 của tất cả các phần tử trong dãy: {3,0,1} ↔ {0,0,1}, vì ta có thể chứng minh được hai dãy này là tương. Chứng minh:
Gọi dãy ban đầu là A, dãy sau khi giảm ước là B=f(A) (f là hàm rút gọn).
Vì B là dãy giảm ước của A nên với mọi B đi một nước đến B’ thì Acũng đi một nước đến A’ (cùng vị trí và số ô) sao cho f(A’) = f(B’). (I)
Ví dụ: B{0,0,1} sau một nước đi vị trí 3 với số ô đi bằng 1 đến B’{0,0,0} thì A cũng đi tại 3 với số ô bằng 1 đến A’{3,0,0}. Lúc đó ta có: f(A’) = f(B’) = {0,0,0}.
Vì mọi bước chơi của đối thủ hòng có lợi cho mình. Nếu người chơi thứ nhất thực hiện một nước đi từ A đến A’ hòng thay đổi sự thua ->thắng (vốn theo lý thuyết là xác định), tức f(A) thua, f(A’) thua mà B = f(A), suy ra B không đi được đến B’ (vì B=f(A) suy ra B thua, B’ cũng thua) suy ra người chơi đã thực hiện trên một ô có số ô tự do ở đằng trước lớn hơn bằng 3, suy tiếp ra người thức hai có thể đi tiếp một nước trên cùng ô đấy với số ô bằng (3 - số ô người một đã đi). Suy ra người 1 vẫn ổ vị trí f(A’’) thua. (II)
(I)(II) => người chơi trạng thái cuối.
Thuật giải:
- Mỗi trạng thái chơi hay mỗi đỉnh của đồ thị là một số viết trong hệ cơ số 3, sau mỗi một bước đi thì chơi đến một trạng tháI chơi khác, ta làm động tác rút gọn lấy modun 3 thì lại được một trạng thái khác được biểu diễn dưới dạng cơ số ba khác. Ta tính sự thắng thua trên đồ thị này. Ví dụ: {0, 0, 1} chỉ đi đến {0,0,0}; {1,2,1} nếu ta đi viên sỏi thứ hai sang trái hai ô ta đến trạng thái {1,0,3} ↔ {1,0,0}.(lưu ý: nếu biểu diển theo này ta chỉ đi đến trạng thái có giá trị cơ số 3 nhỏ hơn, trong đó vị trí có giá trị lớn nhất nằm bên phải}.
- Nếu một trạng thái chơi mà thắng khi chỉ khi trạng tương đương là thắng.
Chương trình mô tả

Code:


Var ketqua : array [0..59060] of byte;
Procedure Thang_thua (x : longint); {0<= x <=59049 = 3^10}
Var thang, i : byte;
a, b : array [0..10] of byte;
y : longint;
Begin
Doi_x_sang_co_so_3 (x, a);
//* x=16 => a[0]=3(số chữ số trong hệ cơ số 3 của x);
//*a[1] = 1, a[2]=2, a[3]=1;
For i := 1 to a[0] do
For ci:= 1 to 2 do
If (a[i] >= ci) then
Begin
Thuc_hien_buoc_di_o_vi_tri_i(i, ci, a, b);
//* có thể có tới hai cách, ci =1 hoặc 2
//* ví dụ: i=2, ci=2, a={3, 1, 2, 1}
//* b={3,1,0,3}
Rut_gon_b(b);
//*b={3,1,0,0}
Doi_b_sang_y(b);
//* đổi sang cơ số 10
//* y=9
If (ketqua[y] = 0) then
Begin
Ketqua[x] := 1;
Exit;
End;
End;
Ketqua[x] := 0;
End;

Procedure Chuong_trinh;
Var a, b : array [0..10] of byte;
Xau : string[50];
x : longint;
dem : byte;
Begin
Dem := 0;
Nhap_N_va_xau( N, Xau);
Doi_xau_sang_co_so_3(Xau, a);
Vong lap: Di_cac_buoc_di_thu_(a, b)
Doi_b_sang_x (b, x);
If ketqua[x] = 0 then inc (dem);
Ket_thuc_vong_lap;
Print (dem);
End;


(Bài tập tự giải) đề thi thử ioicamp.com lần 2:

Trò chơi chuyển đá
Nguồn: Topcoder – Sưu tầm: Nguyễn Văn Hiếu
Vào một ngày đẹp trời, A nghĩ ra một trò chơi và rủ B cùng tham gia. Có n ô, mỗi ô chứa một số viên đá. Các ô được đánh số từ 0 đến n-1. Để thực hiện một nước đi, A/B chọn 3 ô với chỉ số i, j, k thoả mãn i < j, j ≤ k và ô i chứa ít nhất 1 viên đá, sau đó bỏ đi 1 viên đá ở ô i đồng thời thêm hai viên đá vào ô j và ô k (mỗi ô một viên). Chú ý là j có thể bằng k, và sau mỗi bước tổng số viên đá luôn tăng lên 1. Ai không thể thực hiện nước đi coi như bị thua. A đi trước. Nhiệm vụ của bạn là xác định xem A có thể chiến thắng hay không? (giả sử B chơi tối ưu). Nếu có thể hãy in ra 3 số i, j, k mô tả nước đi đầu tiên của A. Nếu có nhiều kết quả hãy in ra kết quả có i nhỏ nhất, nếu vẫn có hơn một kết quả chọn kết quả có j nhỏ nhất, nếu vẫn có hơn một kết quả chọn kết quả có k nhỏ nhất.
Input: STONES.INP
- Dòng đầu gồm số nguyên n là số ô.
- Dòng thứ hai gồm n số, số thứ i thể hiện số viên đá ở ô i.
Output: STONES.OUT
- Nếu A thắng thì in ra 3 số i, j, k trên một dòng duy nhất.
- Nếu A thua thì in ra một số –1 duy nhất.
Giới hạn:
- Kích thước:
+ 1 ≤ n ≤ 15
+ Số viên đá ở một ô không vượt quá 1000.
- Thời gian: 1 s/test
- Bộ nhớ: 1 MB

Gợi ý: Trạng tương đương là trạng thái rút lấy modun cho 2, như vậy có nhiều nhất là 2^15 trạng thái.
Tóm lại: Tư tưởng của lại trò chơi này rất đơn giản, bước đi tốt nhất của mình là bước đi dồn đối thủ đến tình trạng xấu nhất hay có lợi cho mình nhất: F(v) = max{G(v) - F(u); u | (v,u) Î E}. Trong đó: F(v) là giá trị tốt nhất tại đỉnh v của người đi từ đỉnh đấy, G(v) là giả trị của đỉnh v.

pkt_zz
THƯỢNG TƯỚNG V
THƯỢNG TƯỚNG V

Tổng số bài gửi : 1029
Join date : 15/12/2009
Age : 25
Đến từ : MẠC XÁ-QUANG PHỤC

Xem lý lịch thành viên http://lop12a5thpttk-0609.forumotion.net

Về Đầu Trang Go down

Re: Tổng quan về các bài toán trò chơi đối kháng

Bài gửi by Trang_Pham on 2/10/2010, 8:49 am

Vãi

_________________

Trang_Pham
THƯỢNG TƯỚNG V
THƯỢNG TƯỚNG V

Tổng số bài gửi : 616
Join date : 18/09/2010
Age : 25
Đến từ : Vietnam

Xem lý lịch thành viên

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết