Bàn cờ là một tấm bảng chữ nhật N dòng mã số từ trên xuống lần lượt
là 1, 2,...,N và M cột mã số từ trái sang lần lượt là 1,2,...,M; 2 £ N £ 500,
2 £
M £
50. Một quân cờ @ được đặt tại dòng x, cột y. Hai đấu thủ A và B luân
phiên mỗi người đi một nước như sau:
buộc phải chuyển quân cờ @ từ cột hiện đứng là y sang cột k tùy chọn nhưng phải
khác cột y. Việc chuyển này phải được thực hiện nghiêm ngặt như sau: trước hết đẩy ngược quân cờ @ lên k
dòng. Nếu quân cờ vẫn còn trong bảng thì rẽ phải hoặc trái để đặt quân cờ vào cột k, ngược lại nếu quân cờ rơi ra ngoài
bảng thì coi như thua.
Như vậy, nếu quân cờ
đang đặt tại vị trí (x,y) muốn chuyển quân cờ sang cột k ¹ y thì trước hết phải đẩy quân cờ đến dòng x-k. Nếu x-k ³ 1 thì được phép đặt quân cờ vào vị trí mới là (x-k,k).
Giả thiết A luôn luôn
là đấu thủ đi nước đầu tiên và hai đấu thủ đều chơi rất giỏi. Biết các giá trị
N, M, x và y. Hãy cho biết A thắng (ghi 1) hay thua (ghi 0)?
|
s
|
u
|
v
|
w
|
x
|
|
j
|
|
A3
|
|
|
|
k
|
|
|
|
|
|
l
|
B2
|
|
|
|
|
m
|
|
|
A1
|
|
|
n
|
|
|
|
|
|
o
|
|
|
|
|
|
p
|
|
@
|
|
|
|
q
|
|
|
|
|
Với N = 8, M = 4, quân cờ @ đặt tại vị trí xuất phát (7,2) và A đi trước ta thấy A sẽ thắng sau 3
nước đi đan xen tính cho cả hai đấu thủ như sau:
1. A chuyển @ từ
vị trí @(7,2) sang vị trí A1(4,3)
2. B chuyển @ từ
vị trí A1(4,3) sang vị trí B2(3,1)
3. A chuyển @ từ
vị trí B2(3,1) sang vị trí A3(1,2)
B chịu thua vì hết cách đi!
Thuật toán
Ta thử vận dụng kĩ thuật Nhân - Quả để
điền trị 1/0 vào mỗi ô (i, j) của bảng a
với ý nghĩa như sau: nếu gặp thế cờ có quân cờ @ đặt tại vị trí (i, j) thì ai
đi trước sẽ thắng (1) hay thua (0). Ta sẽ duyệt theo từng dòng từ 1 đến N, trên mỗi dòng ta duyệt từ cột 1
đến cột M.
Ta có nhận xét
quan trọng sau đây. Nếu ô (i, j) = 0 tức là gặp thế thua thì các ô đi đến được
ô này sẽ là những thế thắng. Đó chính là các ô (i+j, k) với 1 £ k £ M và k ¹ j.
|
Nhận xét
Nếu [i, j] = 0 thì mọi ô trên dòng i+j,
trừ ô (i+j, j)
đều nhận trị 1.
[i,
j] = 0 Þ
[i+j, k] = 1, k = 1..M, k ¹ j.
|
Từ nhận xét này ta viết ngay được hàm Ket - kiểm tra xem người đi trước
với quân cờ @ tại ô (x,y) trên bàn cờ N´M sẽ thắng (1) hay thua
(0).
Trước hết ta lấp đầy trị 0 cho bảng - mảng hai chiều a[1..N,
1..M] kiểu byte, sau đó lần lượt duyệt các phần tử của bảng và điền trị 1 theo
nhận xét trên.
function Ket(x,y: integer): integer;
var i,j,k: integer;
begin
fillchar(a,sizeof(a),0);
for i := 1 to x-1 do
for j := 1 to
Min(x-i,M) do
if (a[i,j] = 0)
then
{ Điền 0 cho các
ô (i+j, k); k=1..M, k ¹ j }
for k := 1
to M do
if (k
<> j) then a[i+j,k] := 1;
Ket := a[x,y];
end;
Thuật toán trên đòi hỏi độ phức tạp cỡ N.M2.
|
|
u
|
v
|
w
|
x
|
|
|
u
|
v
|
w
|
x
|
|
j
|
0
|
0
|
0
|
0
|
|
|
0
|
0
|
0
|
0
|
|
k
|
0
|
0
|
0
|
0
|
|
|
0
|
1
|
1
|
1
|
|
l
|
0
|
0
|
0
|
0
|
|
|
1
|
1
|
1
|
1
|
|
m
|
0
|
0
|
0
|
0
|
|
|
1
|
1
|
0
|
1
|
|
n
|
0
|
0
|
0
|
0
|
|
|
1
|
1
|
1
|
0
|
|
o
|
0
|
0
|
0
|
0
|
|
|
0
|
0
|
0
|
0
|
|
p
|
0
|
0
|
0
|
0
|
|
|
1
|
1
|
1
|
1
|
|
q
|
0
|
0
|
0
|
0
|
|
|
0
|
0
|
0
|
0
|
|
Lấp đầy 0 (bảng trái) rồi điền trị
(bảng phải)
cho cờ bảng N = 8, M = 4.
Kết quả với x =
7, y = 2: a[7,2] = 1 (A thắng).
|
||||||||||
Để tham gia cuộc
chơi với các giá trị N, M và (x,y) cho trước dĩ nhiên bạn cần tính trước bảng a
theo thủ tục Ket nói trên. Sau đó, mỗi lần cần đi bạn chọn
nước đi theo hàm CachDi như mô tả dưới đây. Hàm nhận vào các giá trị N, M là kích thước
dòng và cột của bảng; dòng sx, cột sy là vị trí đang xét của quân cờ @ và cho
ra một trong ba giá trị loại trừ nhau như sau:
CachDi = 1 nếu tìm được một vị trí chắc thắng (nx,ny)
để đặt quân cờ;
CachDi = 0 nếu không thể tìm được vị trí chắc
thắng nào nhưng còn nước đi do đó buộc phải đi đến vị trí (nx,ny);
CachDi = -1 nếu hết cách đi, tức là chấp nhận
thua để kết thúc ván cờ.
Ta thấy sau khi
gọi thủ tục Ket thì dòng đầu tiên của bảng a chứa tòan 0
và phần tử a[2,1] cũng nhận trị 0. Đó là những thế buộc phải đầu hàng vì đã hết
cách đi. Vậy tình huống đầu hàng (hay hết cách đi) sẽ là
sx = 1, hoặc
sx = 2 và sy = 1.
Ngoài ra, do thủ
tục Ket đã được gọi, tức là bảng a đã được điền
thể hiện mọi cách đi của cuộc chơi nên a[sx,sy] cho ta ngay giá trị chắc thắng
hoặc chắc thua của tình huống xuất phát từ ô (sx,sy).
Nếu a[sx,sy] = 0
ta đành chọn nước đi có thể thua chậm theo Heuristic sau đây: Tìm cách đẩy quân cờ @ từ vị trí (sx,sy) lên
càng ít ô càng tốt.
Nếu a[sx,sy] = 1
ta chọn nước đi có thể thắng nhanh theo Heuristic sau đây: Tìm cách đẩy quân cờ @ từ vị trí (sx,sy) lên cao nhất có thể được,
tức là lên vị trí (nx, ny) thỏa đồng thời các điều kiện
a[nx, ny] = 0,
nx càng nhỏ càng
tốt.
Sau này ta sẽ
thấy các Heuristics trên chỉ là một cách
đi tốt chứ chưa phải là cách đi tối ưu.
function CachDi(M, sx, sy: integer; var nx,ny: integer):
integer;
begin
if (sx = 1) or ((sx = 2)
and sy = 1)) then
begin { Het cach di: Dau
hang }
CachDi := -1;
exit;
end;
CachDi := a[sx,sy];
if CachDi = 0 then { Con
nuoc di nhung se thua }
for ny := 1 to
Min(sx-1,M) do
if (ny <> sy)
then
begin
nx := sx – ny;
exit;
end;
{ Chac thang }
for ny := Min(sx-1,M)
downto 1 do
if (ny <> sy) then
if (a[sx-ny,ny] = 0)
then
begin { chac
thang }
nx := sx –
ny; exit;
end;
end;
end;
Hàm Min(a,b) cho
ra giá trị min giữa hai số a và b cần dược mô tả trước như sau:
function Min(a,b: integer): integer;
begin
if (a < b) then Min :=
a else Min := b;
end;
Chương trình C# dưới đây mô
tả một ván Cờ Bảng 50 ´ 7 giữa hai đấu thủ A (đi trước) và B. Quân cờ xuất phát
tại vị trí (49,5). Ván này A sẽ thắng.
using
System;
using
System.Collections.Generic;
using
System.Text;
namespace
ConsoleApplication1 {
class Program {
static int maxn = 501, maxm = 51;
static int[,] a = new int [maxn,maxm];
static void Main(string[]
args){
Game(50, 7, 49, 5);
Console.WriteLine("\n \n Fini");
Console.ReadLine();
}
static void Game(int n, int m, int x, int
y) {
Console.WriteLine("\n The co " +
n +
" X
"+m+" @ = ("+x+","+y+")");
Ket(m, x, y);
Show(a, x, m);
while (true) {
Console.Write("\n A: ( "
+ x + " , " + y + " ) ");
if (CachDi(m,
x, y, ref x, ref y) == -1) {
Console.Write("Dau hang !!!");
Console.ReadLine();
return;
}
else Console.Write(" ==> (
" + x + " , " + y + " ) ");
if (Console.Read() == '.') return;
Console.Write("\n
B: ( " + x + " , " + y + " ) ");
if
(CachDi(m, x, y, ref x, ref y) == -1) {
Console.Write("Dau hang !!!");
Console.ReadLine();
return;
}
else Console.Write(" ==> (
" + x + " , " + y + " ) ");
if (Console.Read() == '.') return;
}
// while
}
static int CachDi(int m, int sx, int sy,
ref int nx, ref int ny)
{
if (sx == 1 || (sx == 2 && sy
== 1)) return -1;
if (a[sx, sy] == 0) { // Di duoc, nhung
thua
for (ny = 1; ny <=
Min(sx-1,m);++ny)
if (ny != sy) { nx = sx - ny; return 0; }
}
for (ny = Min(sx-1,m); ny > 0;
--ny)
if (ny != sy)
if (a[sx - ny, ny] == 0) //
Chac thang
{ nx = sx - ny; return 1; }
return 0;
}
static int
Min(int a, int b) { return (a < b) ? a : b; }
static int
Ket(int m, int x, int y) {
Array.Clear(a,0,a.Length);
for (int i =
1; i < x; ++i) { // voi moi dong i
int minj =
Min(x - i, m);
for (int j = 1; j <= minj; ++j)
// xet cot j
if (a[i,
j] == 0)
for
(int k = 1; k <= m; ++k)
if (k
!= j) a[i + j, k] = 1;
}
return a[x,
y];
}
static void Show(int[,] s, int n, int m) {
Console.WriteLine();
for (int i = 1; i <= n; ++i) {
Console.Write("\n"+i+". ");
for (int j = 1; j <= m; ++j)
Console.Write(a[i, j] +
" ");
}
}
}// Program
}
Nếu N có kích thước
lớn, thí dụ, cỡ triệu dòng, còn số cột M vẫn đủ nhỏ, thí dụ M £ 50
và đề ra chỉ yêu cầu cho biết người đi trước thắng hay thua chứ không cần lý
giải từng nước đi thì ta vẫn có thể sử dụng
một mảng nhỏ cỡ 51´51 phần tử để giải bài toán trên. Ta khai báo kiểu mảng
như sau:
const mn = 51;
type
MB1 = array[0..mn] of
byte;
MB2 = array[0..mn]
of MB1;
var a: MB2;
N: longint;
M: integer;
....
Ta sử dụng mảng
index dưới đây để chuyển đổi các số hiệu dòng tuyệt đối thành số hiệu riêng
trong mảng nhỏ a. bạn chỉ cần lưu ý nguyên tắc sau đây khi xử lý các phép thu
gọn không gian: Không ghi vào vùng còn
phải đọc dữ liệu. Thực chất đây là một hàm băm các giá trị i trong khoảng 1..N vào miền 0..M bằng phép chia
dư: i à (i-1) mod (M+1) như mô tả trog hàm index.
function index(i,M:
integer): integer;
begin
index := i mod (M+1);
end;
function Ket(M: integer;
x: longint; y:
integer): integer;
var i: longint; j,k:
integer;
begin
fillchar(a,sizeof(a),0);
for i:= 1 to x-1 do
begin
k := index(i+M,M);
fillchar(a[k],sizeof(a[k]),0);
for j:=1 to Min(x
- i, M)do
if (a[index(i,M),j]
= 0) then
for k := 1 to
M do
if (k
<> j) then
a[index(i+j,M),k] := 1;
end;
Ket := a[index(x,M),y];
end;
//C#
static int
Index(int i, int m) { return i % (m + 1); }
static int
Ket(int m, int x, int y){
int id, Minj, i, j, k, v ;
Array.Clear(a, 0, b.Length);
for (i = 1; i < x; ++i) {
id = Index(i + m, m);
for
(v = 1; v <= m; ++v) a[id, v] = 0;
minj = Min(x - i, m);
for
(j = 1; j <= minj; ++j) // xet cot j
if
(a[Index(i, m), j] == 0)
for (k = 1; k <= m; ++k)
if (k != j) a[Index(i + j, m), k] = 1;
}
return a[Index(x,m), y];
}
Đến đây ta thử mở rộng điều kiện của bài toán như sau: Hãy
cho biết, với các giá trị cho trước là kích thước bảng N´ M, vị trí xuất phát của
quân cờ @ (x,y) và đấu thủ A đi trước thì A thắng hoặc thua sau bao nhiêu nước
đi ?
|
Nguyên
tắc của các trò chơi đối kháng
Nếu biết là thắng thì tìm cách thắng nhanh nhất,
Nếu biết là sẽ thua thì cố kéo dài cuộc chơi để
có thể thua chậm nhất. |
Ta vẫn sử dụng bảng A để điền trị với các qui
ước mới sau đây:
Nếu từ ô (i, j) người đi trước có thể thắng sau b nước đi
thì ta đặt a[i,j] = +b; ngược lại nếu từ ô này chỉ có thể dẫn đến thế thua sau
tối đa b nước đi thì ta đặt a[i,j] = -b.
Một nước đi là một lần di chuyển quân cờ của một trong 2 người chơi. Ta cũng
qui ước a[i,j] = 0 có nghĩa là đấu thủ xuất phát từ ô (i,j) sẽ hết cách đi do
đó chấp nhận thua ngay. Kí hiệu (i,j) à
(u,v) nếu có nước đi hợp lệ từ ô (i,j) sang ô (u,v). Từ nguyên tắc của các trò chơi đối kháng ta suy ra
(1) Nếu từ ô (i,j)
có những nước đi hợp lệ dẫn đến thế (làm cho đối phương) thua thì ta chọn cách
thắng nhanh nhất bằng cách đặt
a[i,j] = min { -a[u,v] | (i,j) à (u,v), a[u,v] £ 0 } + 1
(2) Nếu từ ô (i,j) mọi nước đi hợp lệ đều dẫn
đến thế (tạo cho đối phương thắng) thì ta phải chọn cách thua chậm nhất bằng
cách đặt
a[i,j] = - (max { a[u,v] | (i,j) à (u,v), a[u,v] > 0 } + 1)
|
|
1
|
2
|
3
|
4
|
|
1
|
0
|
0
|
0
|
0
|
|
2
|
0
|
1
|
1
|
1
|
|
3
|
1
|
1
|
1
|
1
|
|
4
|
1
|
1
|
-2
|
1
|
|
5
|
1
|
1
|
1
|
-2
|
|
6
|
-2
|
-2
|
-2
|
-2
|
|
7
|
3
|
3
|
3
|
3
|
|
8
|
3
|
-4
|
3
|
3
|
|
9
|
3
|
3
|
3
|
3
|
|
10
|
3
|
3
|
3
|
5
|
|
11
|
-4
|
-4
|
-4
|
-4
|
|
12
|
-4
|
5
|
5
|
5
|
|
Tab
Game với
N
= 12, M = 4.
|
||||
Sau khi lấp đầy 0
cho bảng a ta lần lượt duyệt các dòng i từ 1 đến x. Với mỗi dòng ta duyệt các
cột j từ 1 đến M. Nếu gặp trị a[i,j] = 0 ta hiểu là vị trí này sẽ dẫn đến thua.
Ta cần tính số bước thua chậm nhất rồi gán cho a[i,j]. Tiếp đến, do vị trí
(i,j) là thua nên ta phải cập nhật lại các giá trị a[u,v] ứng với các vị trí
(u,v) à (i,j).
Bạn thử điền trị
cho bảng a với N = 12, M = 4. Trong thí dụ này, a[8,2] = - 4 có nghĩa là nếu
quân cờ @ đặt ở vị trí (8,2) thì người đi trước sẽ thua sau 4 nước đi. Thật vậy, gọi A là người đi trước,
ta thấy nếu A di chuyển @ đến (7,1) thì B sẽ đi tiếp để thắng sau 3 nước đi; A
không thể đên dòng 6 (?). Nếu A đến (5,3) thì B sẽ đi tiếp để thắng sau 1 nước.
Nếu A đến (4,4) thi B sẽ đi tiếp 1 nước nữa để đến (1,3) là thắng.
Tại sao trong hàm
Ket ta phải tính thế thua trước khi tính thế thắng.
Vì khi gặp a[i,j] = 0 thì ta cần cập nhật giá trị này để biết được là sẽ thua
sau bao nhiêu nước đi. Sau đó, do cơ chế lập luận lùi, chỉ khi nào ta biết số
nước thua tại a[i,j] thì mới tính tiếp được các thế thắng dẫn đến hế thua này.
function Ket(M,x,y: integer): integer;
var i, j: integer;
begin
fillchar(a,sizeof(a), 0);
for i := 1 to x do
for j := 1 to M do
if (a[i,j] = 0) then
begin
TinhNuocThua(M,i,j);
TinhNuocThang(M,x,i,j);
end;
Ket := a[x,y];
end;
Procedure TinhNuocThua(M,i,j: integer);
var k, vmax: integer;
begin
vmax := -1;
for k := 1 to Min(i-1,M)
do
if (k <> j) then
vmax := Max(vmax,
a[i-k,k]);
a[i,j] := -(vmax + 1);
end;
Procedure TinhNuocThang(M,x,i,j: integer);
var k, d, v: integer;
begin { Xet dong i+j }
d := i+j;
if (d <= x) then {
quan co con trong vung can xu ly }
begin
v := -a[i,j] + 1;
for k := 1 to M do
if (k <> j)
then
if (a[d,k] > 0)
then a[d,k] := Min(a[d,k], v)
else a[d,k] := v;
end;
end;
// C#
static int Ket(int n, int m, int x, int y) {
Array.Clear(a, 0, a.Length);
for (int i = 1; i <= x; ++i) {
// voi moi dong i
for (int j = 1; j <= m; ++j)
// xet cot j
if (a[i, j] == 0) {
TinhNuocThua(m, i, j);
TinhNuocThang(m, x, i,
j);
}
}
return a[x,y];
}
static void TinhNuocThua(int m, int i,
int j) {
int vmax = -1, km = Min(i-1,m);
for (int k = 1; k <= km; ++k)
if (j != k) vmax = Max(vmax,
a[i - k, k]);
a[i,j] = -(vmax + 1);
}
static void TinhNuocThang(int m, int x,
int i, int j){
int d = i + j;
if (d > x) return;
int vmin = -a[i,j]+1;
for (int k = 1; k <= m; ++k)
if (k != j)
a[d,k] = (a[d, k] > 0) ? Min(a[d,
k], vmin) : vmin;
}
Với N cỡ triệu và M đủ nhỏ bạn cũng có thể vận dụng các kĩ
thuật tương tự như đã trình bày để có thể tính số nước thắng/thua, tuy nhiên
trong trường hợp này bạn phải khai báo mảng a rộng gấp đôi, tức là a phải chứa
2M+2 dòng gồm M dòng trước dòng đang xét và M dòng sau dòng đang xét. các dòng
trước và sau này dùng để cập nhật số nước đi thắng/thua.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét