Đến lượt ai, người đó có nhiệm vụ di chuyển quân cờ đang đặt tại cột i sang cột theo cách sau:

• Thoạt tiên chuyển dọc quân cờ lên k dòng, nếu quân cờ chưa ra khỏi giới hạn bàn cờ thì tiếp tục chuyển quân cờ (rẽ phải hoặc trái) sang cột k.
• Đấu thủ nào, đến lượt mình, không tìm được cách nào di chuyển quân cờ thì sẽ thua. Ván cờ kết thúc.

Thí dụ, với bàn cờ 10x4, quân cờ @ đặt tại vị trí (5,3) thì A có thể di chuyển quân cờ đến các ô (6,1), (7,2) hoặc (9,4).

Yêu cầu: Hãy cho biết A có thể thắng hay không? Trong trường hợp A thắng, hãy cho biết A có thể thắng sau tối đa bao nhiêu nước đi với giả thiết là hai đấu thủ A và B đều chơi rất giỏi và mỗi lượt A hoặc B đi được gọi là một nước đi.

Trong thí dụ trên, khi quân cờ được đặt tại vị trí xuất phát (5,3) thì A thua.

Ngược lại, nếu chọn vị trí xuất phát là (4,3) thì A có thể thắng sau 2 nước đi (xem hình 1).

Dữ liệu vào: Tệp văn bản tab.inp:

Dòng đầu tiên là số lượng test s, 1 s 10.

Tiếp đến là s dòng, mỗi dòng là một test gồm 4 số tự nhiên cách nhau ít nhất một dấu cách, N M x y, trong đó

• N - số lượng dòng của bảng,1 s 200,
• M - số lượng cột của bảng,1 s 50,
• x- tọa độ dòng xuất phát của quân cờ,
• y - tọa độ cột xuất phát của quân cờ.

Dữ liệu ra: Tệp văn bản tab.out:

Gồm s dòng, dòng thứ i chứa kết quả của test thứ i, cụ thể là chứa duy nhất một số tự nhiên d với nghĩa sau,

• d = 0: nếu A thua,
• d > 0: nếu A thắng sau d nước đi.

Thí dụ,

Bài giải

Đây là một bài toán khó thuộc lớp các bài toán trò chơi, tuy nhiên lời giải là dễ hiểu và đặc biệt là thuật giải bài toán này có thể vận dụng cho một số bài toán khác.

a. Trước hết chúng ta hãy giảm nhẹ yêu cầu của bài toán, cụ thể là chúng ta chỉ yêu cầu xác định đấu thủ đi nước đầu tiên là A sẽ thắng (ghi đáp số là 1) hay thua(ghi đáp số là 0).

Phương án này có thể giải dễ dàng bằng quy hoạch động như sau.

Lần lượt điền các giá trị 0 và 1 vào các ô trong từng dòng của bảng, theo trật tự từ dòng cao nhất, dòng thứ N đến dòng thấp nhất, dòng 1. Trên mỗi dòng ta lần lượt điền từ trái qua phải, tức là từ cột 1 đến cột M. Gọi mảng chứa dữ liệu của bàn cờ làa, ta quy định a[i,j] = 0 nếu xuất phát từ ô (i,j) đến lượt ai đi thì sẽ thua, ngược lại, a[i,j] = 1 thì người nào đến lượt đi sẽ thắng.

Để tiện trình bày, ta sẽ gọi ô chứa trị 0 là ô 0 (ô không) hay ô (dẫn đến) thua , ô chứa trị 1 là ô 1 hay ô (dẫn đến) thắng.

Ta thấy dòng N sẽ chứa toàn 0, vì đó là các thế“cùng”, tức là các thế thua. Từ dòng N-1 trở xuống ta tính trị cho các ô như sau.

Từ ô (i,j), nếu có một cách di chuyển quân cờ đến ô 0 là ô đẩy đối phương vào thế thua, thì người cầm quân sẽ thắng, ngược lại, nếu không có cách nào, hay với mọi cách đi người cầm quân chỉ có thể di chuyển quân cờ đến các ô 1 thì anh ta sẽ thua, vì sau anh ta, đến lượt đối phương sẽ được “hưởng” thế thắng tại các ô nhận trị 1.

Khung của lời giải thể hiện trong thủ tục run sẽ như sau:

1.Mở tệp input tab.inp để đọc dữ liệu vào.

2.Mở tệp output tab.out để chuẩn bị ghi kết quả.

3.Đọc số lượng test vào biến sotest.

4.Với mỗi test

4.1.Đọc các giá trị N, M, x và y từ tệp input tab.inp, trong đó N và M là kích thước bàn cở, (x,y) là tọa độ xuất phát của quân cờ.

4.1.Gọi thủ tục tab để điền trị cho mảng a là mảng biểu thị bàn cờ.

4.1.Ghi a[x,y] là kết quả chơi ván cờ của đấu thủ A ứng với test đã cho với giả thiết là A đi trước.

5.Đóng các tệp input và output.

procedure run;

var i: integer;

begin

assign(f,fn); reset(f);

assign(g,gn); rewrite(g);

readln(f,sotest);

for i:=1 to sotest do

begin

readln(f,n,m,x,y);

tab;

writeln(g,a[x,y]);

end;

close(f); close(g);

end;

Thủ tục tab được thể hiện như sau,

1Khởi trị toàn 0 cho mảng a.

2Với mỗi dòng từ N-1 đến 1

Với mỗi cột từ 1 đến M

Điền trị cho ô a[i,j] theo thủ tục value(i,j).

4.Nhận a[x,y] làm đáp số. Dừng thủ tục.

procedure tab;

var i,j: integer;

begin

fillchar(a,sizeof(a),0);

for i:=n-1 downto 1 do

for j:=1 to m do value(i,j);

end;

Thủ tục điền trị cho ô (i,j), value(i,j) hoạt động như sau,

1. Đầu tiên ta duyệt các cột trước j, cụ thể là các cột k:=1..(j-1) và xét xem có thể di chuyển quân cờ @ đến ô (i+k,k) để đảm bảo chắc thắng hay không. Quân cờ @chuyển được đến ô (i+k,k) khi và chỉ khi

(i)có thể chuyển @ đến dòng i+k vẫn nằm trong giới hạn của bàn cờ, tức là i+k N,

(ii)Nếu chuyển @ đến ô (i+k,k) thì người cầm quân chắc thắng, hay là người đi tiếp sẽ thua, tức là a[i+k,k] = 0.

2. Tiếp đến ta duyệt các cột sau j, cụ thể là các cột k từ j+1 đến M theo cùng cách thức như trên.

Nếu tìm được một ô thỏa hai điều kiện thắng (i) và (ii) thì ta gán trị cho a[i,j] = 1 với ý nghĩa là người cầm quân đi từ ô (i,j) đó sẽ chắc thắng, sau đó dừng tủ tục value.

Ngược lại, nếu đãduyệt mọi cột k:= 1..j-1, j+1..M mà không tìm được ô nào thỏa hai điều kiện thắng nói trên thì đành chọn ô tùy ý, miễn là đi được theo đúng luật chơi. Trong trường hợp này ta phải gán trị a[i,j] = 0 với ý nghĩa là người cầm quân sẽ thua, sau đó dừng thủ tục value.

{ xac dinh gia tri cho o a[i,j];

a[i,j] = 0: Ai di tu o do se thua

a[i,j] = 1: Ai di tu o do se thang }

procedrue value(i,j: integer);

var k: integer;

begin

a[i,j]:=1; { Gán trước trị thắng }

{ Duyet cac o truoc cot j }

for k:=1 to j-1 do

if i+k <= n { trong ban co } then

if a[i+k,k] = 0 then exit;

{ Duyet cac o sau cot j }

for k:=j+1 to m do

if i+k <= n { trong ban co } then

if a[i+k,k] = 0 then exit;

a[i,j]:=0;

end;

Toàn văn chương trình cho trường hợp a như sau.

(*====================================

Chi can biet thang (1) thua (0)

======================================*)

uses crt;

const

fn = 'tab.inp'; gn='tab.out';

bl = #32; nl = #13#10;

nn = 201; mm = 51; { kich thuoc ban co mm X nn }

type

mb1 = array[0..mm] of byte;

mb2 = array[0..nn] of mb1;

var f,g: text;

n,m,sotest: integer;

x,y: integer; { Toa do xuat phat cua quan co }

a: mb2;

{ xac dinh gia tri cho o a[i,j];

a[i,j] = 0: Ai di tu o do se thua

a[i,j] = 1: Ai di tu o do se thang }

procedrue value(i,j: integer);

var k: integer;

begin

a[i,j]:=1; { Gán trước trị thắng }

{ Duyet cac o truoc cot j }

for k:=1 to j-1 do

if i+k <= n { trong ban co } then

if a[i+k,k] = 0 then exit;

{ Duyet cac o sau cot j }

for k:=j+1 to m do

if i+k <= n { trong ban co } then

if a[i+k,k] = 0 then exit;

a[i,j]:=0;

end;

procedure tab;

var i,j: integer;

begin

fillchar(a,sizeof(a),0);

for i:=n-1 downto 1 do

for j:=1 to m do value(i,j);

end;

procedure run;

var i: integer;

begin

assign(f,fn); reset(f);

assign(g,gn); rewrite(g);

readln(f,sotest);

for i:=1 to sotest do

begin

readln(f,n,m,x,y);

tab;

writeln(g,a[x,y]);

end;

close(f); close(g);

end;

BEGIN

run;

readln;

END.

Bạn hãy thử chạy với dữ liệu vào N = 10, M = 4, x = 4, y = 3 và hiển thị mảng a để so sánh với bảng trong hình 1.

b. Ta xét trường hợp yêu cầu thực hiện đầy đủ, nghĩa là phải tính toán xem đấu thủ A cần đi bao nhiêu nước sẽ thắng. Khung chung cho trường hợp này hoàn toàn giống trường hợp a. Điểm khác biệt duy nhất là thủ tục điền trị value(i,j) cho mỗi ô (i,j). Để thực hiện nhiệm vụ này ta chấp nhận nguyên tắc đời thường trong các trò chơi như sau:

• Kẻ nào biết là mình sẽ thắng thì phải tìm cách thắng nhanh nhất,
• Kẻ nào biết là mình sẽ thua thì phải tìm cách thua chậm nhất.

Ta gọi nguyên tắc trên là heuristics (đọc là ơ-ris-tics) có nghĩa là kinh nghiệm chỉ đạo.

Giống như phần trên, ta sẽ gọi ô dẫn đến thắng là ô thắng, ô dẫn đến thua là ô thua. Nói cách khác, ô thắng là ô mà đấu thủ cầm quân từ ô đó sẽ tìm được cách đi để thắng, còn ô thua thì ngược lại, đấu thủ nào cầm quân ở ô đó để đi thì với mọi cách đi đều dẫn đến thua. Trị của ô thắng và thua trong trường hợp b này không đơn giản là 0/1 như trong trường hợp a. Cụ thể là ô thắng (i,j) sẽ nhận giá trị v nếu sau v nước đi người cầm quân cờ tại ô đó sẽ thắng. Còn ô thua (i,j) sẽ nhận giá trị v nếu sau v nước đi người cầm quân cờ tại ô đó sẽ thua dù cho anh ta có cố tình kéo dài ván cờ.

Nhận xét này dẫn đến kỹ thuật điền trị cho mỗi ô (i,j) như sau:

Tại ô (i,j) xét các khả năng:

Nếu có các khả năng dẫn đến thắng thì điền trị cho ô (i,j) với cách thắng nhanh nhất:

a[i,j] = min { Chiều dài của mọi đường dẫn đến thắng } + 1

Ngược lại, nếu không có đường nào dẫn đến thắng thì điền trị cho ô (i,j) với cách thua chậm nhất:

a[i,j] = max { Chiều dài của mọi đường dẫn đến thua } + 1

Dễ hiểu là tại sao lại cộng thêm 1. Đó chính là thêm một nước đi cho người đang cầm quân tại ô (i,j).

Làm thế nào để biết được đường dẫn đến thắng hoặc thua. Rất dễ. Để ý rằng ta chỉ cần quan tâm đến số nước đi dẫn đến thắng / thua chứ không quan tâm đến con đường khúc khuỷu, gập gềnh ra sao. Nghĩa là ta chỉ quan tâm đến độ dài đường đi mà thôi. Vậy thì hãy quy định gán trị cho mỗi ô (i,j) là độ dài đường đi, hay là số nước đi dẫn đến thắng hoặc thua. Ta lại biết, xét theo quan điểm của người cầm quân cờ tại ô (i,j), để thực hiện một nước đi thì mỗi ô (i,j) chỉ có thể dẫn đến một trong 2 khả năng loại trừ nhau: hoặc thắng – hoặc thua. Ta nói trịcủa mỗi ô (i,j) trên bàn cờ cho biết ai cầm quân cờ tại ô này để thực hiện một nước đi thì sau bao nhiêu nước đi sẽ dẫn đến thắng hoặc thua. Cờ này không có trạng thái hòa.

Ta hãy quy định trị của ô (i,j), nếu là số dương thì biểu thi số nước đi dẫn đến thắng, ngược lại nếu trị của ô (i,j) âm hoặc bằng 0 sẽ biểu thị số nước đi (dĩ nhiên là tính theo giá trị tuyệt đối) dẫn đến thua. Từ đây ta có công thức tính trị như sau:

1.Khởi trị:

1.1.Với dòng cao nhất, dòng thứ N, a[N,j] = 0, j := 1..M.

1.2.a[N-1,1] = 0 (bạn hãy giải thích vì sao?)

2.Với các ô (i,j) còn lại ta xét:

2.1.Nếu có cách đi dẫn đến thắng, tức là cách đi dẫn đến ô âm làm cho đối phương thua thì điền trị cho ô (i,j) với cách thắng nhanh nhất:

a[i,j] = min { -a[i+k,k] | (i+k N) and (a[i+k] 0) } + 1

2.2.Ngược lại, nếu không có đường nào dẫn đến thắng thì điền trị cho ô (i,j) với cách thua chậm nhất:

a[i,j] = max { a[i+k,k] | (i+k N) and (a[i+k] > 0) } + 1

Lưu ý rằng với các số âm và 0 ta có thể bỏ qua phép toán lấy trị tuyệt đối và đảo dấu so sánh trong biểu thức 2.1 như sau:

a[i,j] = -(max { a[i+k,k] | (i+k N) and (a[i+k] 0) } – 1)

Ta còn phải lưu ý đến dấu của các trị a[i,j]. Số là, trong trường hợp người cầm quân (i,j) sẽ thắng thì a[i,j] phải là số dương, còn trong trường hợp người đó thua thì a[i,j] phải là số không dương, tức là phải nhỏ hơn hoặc bằng 0.

Với kiểu số nguyên ngắn shortint (dạng 1 byte) chứa các trị trong khoảng
-128..127 ta dễ dàng cài đặt thuật toán value như sau:

procedure value(i,j: integer);

var k,maxthua,minthang: integer;

begin

maxthua:=0; minthang:=-127;

for k:=1 to j-1 do

if i+k <= n then

if a[i+k,k] <= 0 then

begin

{ duyet o am: Ai di chuyen quan vao day se thang

nen can chon o de thang nhanh nhat }

if minthang < a[i+k,k] then minthang:=a[i+k,k]

end

else

begin

{ duyet o duong: Ai di vao day se thua

nen can chon o de thua cham nhat }

if maxthua < a[i+k,k] then maxthua:=a[i+k,k];

end;

for k:=j+1 to m do

if i+k <= n then

if a[i+k,k] <= 0 then

begin

{ duyet o am: Ai di chuyen quan vao day se thang

nen can chon o de thang nhanh nhat }

if minthang < a[i+k,k] then minthang:=a[i+k,k]

end

else

begin

{ duyet o duong: Ai di vao day se thua

nen can chon o de thua cham nhat }

if maxthua < a[i+k,k] then maxthua:=a[i+k,k];

end;

{ uu tien cho kha nang thang }

if minthang <>-127 then a[i,j]:=-(minthang-1)

else a[i,j]:= -(maxthua+1);

end;

Thuật toán trên có tên gọi là thuật toán min-max.

Chương trình hoàn chỉnh cho phương án đầy đủ cuối cùng sẽ như sau.

(* Phuong an day du *)

program tab;

uses crt;

const

fn = 'tab.inp'; gn = 'tab.out';

bl = #32; nl = #13#10;

nn = 201; mm = 51;

type

mb1 = array[0..mm] of shortint;

mb2 = array[0..nn] of mb1;

var f,g: text; { files input, output }

n,m: integer; { kich thuoc bang }

x,y: integer; { toa do xuat phat cua quan co }

sotest: integer;

a: mb2;{ mang 2 chieu chua du lieu mo phong ban co }

{--------------------------------------------------

xac dinh tri cho o (i,j). Chon o (i+k,k)

de chuyen quan tu (i,j) den do, sao cho chac thang

---------------------------------------------------}

procedure value(i,j: integer);

var k,maxthua,minthang: integer;

begin

maxthua:=0; minthang:=-127;

for k:=1 to j-1 do

if i+k <= n then

if a[i+k,k] <= 0 then

begin

{ duyet o am: Ai di chuyen quan vao day se thang

nen can chon o de thang nhanh nhat }

if minthang < a[i+k,k] then minthang:=a[i+k,k]

end

else

begin

{ duyet o duong: Ai di vao day se thua

nen can chon o de thua cham nhat }

if maxthua < a[i+k,k] then maxthua:=a[i+k,k];

end;

for k:=j+1 to m do

if i+k <= n then

if a[i+k,k] <= 0 then

begin

{ duyet o am: Ai di chuyen quan vao day se thang

nen can chon o de thang nhanh nhat }

if minthang < a[i+k,k] then minthang:=a[i+k,k]

end

else

begin

{ duyet o duong: Ai di vao day se thua

nen can chon o de thua cham nhat }

if maxthua < a[i+k,k] then maxthua:=a[i+k,k];

end;

{ uu tien cho kha nang thang }

if minthang <>-127 then a[i,j]:= -(minthang-1)

else a[i,j]:= -(maxthua+1);

end;

procedure tab;

var i,j: integer;

begin

fillchar(a,sizeof(a),0);

{ xu ly rieng cac phan tu 2..M cua dong 2 }

for j:=2 to m do value(n-1,j);

for i:=n-2 downto 1 do

for j:=1 to m do value(i,j);

end;

procedure run;

var i: integer;

begin

assign(g,gn); rewrite(g);

assign(f,fn); reset(f);

readln(f,sotest);

for i:=1 to sotest do

begin

readln(f,n,m,x,y);

tab;

{ Ghi ket qua }

if a[x,y] < 0 then writeln(g,0)

else writeln(g,a[x,y]);

end;

close(f); close(g);

end;

BEGIN

run;

readln;

END.

Một bài toán ứng dụng: Jump Game (Cờ nhảy).

Mời các bạn vui Xuân bằng bàn cờ nhảy sau đây.

Bàn cờ nhảy là một băng N ô mã số từ 1 đến N. Một quân cờ @ được đặt tại một ô x nào đó trên bàn cờ. Cho trước hai giá trị M trong khoảng 1..N và y trong khoảng 1..M.

Hai đấu thủ là A và B lần lượt di chuyển quân cờ. Luật chơi như sau:

• Đến lượt ai, người đó có nhiệm vụ di chuyển quân cờ thêm t ô với t nằm trong khoảng 1 t M, nhưng không được phép chọn trùng với số t của người vừa đi,

• A luôn đi trước trong mọi ván cờ và trong nước đi đầu tiên của mình A phải chọn