Tự viết chương trình cờ tướng

[CXQ]

Bài viết của tác giả Phạm Hồng Nguyên

Chương 1
TRÒ CHƠI ĐỐI KHÁNG VÀ CÁC PHƯƠNG PHÁP TÌM KIẾM

I. Dạng trò chơi

Trong phần này, ta sẽ xem cách một chương trình máy tính có thể chơi được các trò chơi đấu trí như các trò chơi cờ Vua, cờ Tướng, cờ vây, cờ caro (go-moku), go, checker... như thế nào. Các trò này còn gọi là các trò chơi đối kháng, diễn ra giữa hai đấu thủ. Nói chung, các trò chơi đó đều có thể chuyển về một dạng bài toán tìm kiếm đặc biệt: tìm đường đi đến các điểm cao nhất giữa hai đấu thủ. Đặc điểm của các trò chơi trên như sau:

* Có hai đấu thủ, mỗi người chỉ đi một nước khi tới lượt.
* Các đấu thủ đều biết mọi thông tin về tình trạng trận đấu.
* Trận đấu không kéo dài vô tận, phải diễn ra hòa, hoặc một bên thắng và bên kia thua.

Thông thường ta hay gọi các trò chơi này là các loại cờ. Đôi khi ta gọi đây là các trò chơi Minimax (dựa trên tên của thuật toán tìm kiếm cơ bản áp dụng cho chúng). Hình 1.1 là ví dụ về một số trò chơi nói trên. Các trò chơi như chơi bài, dò mìn, xúc sắc... không thuộc lớp trò chơi này.




II. Cây trò chơi
Các trạng thái bàn cờ khác nhau (hay còn gọi là một thế cờ, tình huống cờ) trong quá trình chơi có thể biểu diễn thành một cây tìm kiếm (được gọi là cây trò chơi - hình 1.2) và ta sẽ tiến hành tìm kiếm trên cây để tìm được nước đi tốt nhất. Cây trò chơi có các nút của cây là các tình huống khác nhau của bàn cờ, các nhánh nối giữa các nút sẽ cho biết từ một tình huống bàn cờ chuyển sang tình huống khác thông qua chỉ một nước đi đơn nào đó. Dĩ nhiên, các nước đi này diễn ra theo cặp do hai đấu thủ lần lượt tiến hành. Độ sâu của cây trò chơi ply là số tầng của cây (chính là độ sâu d của cây). Thuật ngữ “nước đi” trong sách được thống nhất chỉ bao gồm một lần đi của một đấu thủ hoặc một lần đi phản ứng lại của đối thủ bên kia. Chú ý nó khác với thói quen dùng trong thực tế một nước đi bao gồm lần đi của ta và một lần đi của đối thủ. Nói cách khác, nước đi ở đây thực chất chỉ là "nửa nước" theo cách hiểu của làng cờ.




III. Vét cạn
Dùng một thuật toán vét cạn để tìm kiếm trên cây trò chơi dường như là một ý tưởng đơn giản. Ta chỉ cần chọn nhánh cây sẽ dẫn tới nước thắng để đi quân là đảm bảo thắng lợi. Nếu đúng vậy, các loại cờ sẽ trở thành các trò chơi buồn tẻ, sẽ chẳng còn đâu những bí quyết huyền ảo thần kì và bàn cờ sẽ chẳng khác gì bàn... tính. Rất tiếc (hoặc rất may) rằng, cách làm này lại không thể thực hiện nổi do cái gọi là bùng nổ tổ hợp. Ví dụ, nếu từ một thế cờ, trung bình có khả năng đi được 16 nước đi khác nhau (ta gọi đó là hệ số nhánh con tại mỗi nút là b = 16). Như vậy, sau một tầng ta sẽ có 16 nút con, mỗi nút này lại có thể có 16 con nữa. Tổng số nút con ở độ sâu thứ hai là 16x16 = b^2. Cứ như vậy ở độ sâu d sẽ có b^d nút.

Nếu giả sử độ sâu của cây là 100 (hệ số nhánh 16 và độ sâu 100 đều là những con số còn nhỏ hơn con số thường gặp trong trò chơi cờ), thì số nhánh phải duyệt lên đến 16^100 hay xấp xỉ 10^120 - một con số lớn khủng khiếp. Để hình dung số đó lớn thế nào, ta giả sử tất cả các nguyên tử trong vũ trụ đều trở thành máy tính để tính nước đi với tốc độ một giây tính được cỡ 10^10 (10 tỷ) nước đi, và nếu chúng hoạt động cật lực từ thời vụ nổ lớn đến nay (theo một số lý thuyết, thì thế giới này hình thành sau một vụ nổ gọi là vụ nổ lớn bigbang, trước đây cỡ 15 tỷ năm) thì đến bây giờ mới có thể đi được nước đi đầu tiên.

Vì số các khả năng tăng quá nhanh, chỉ có một số ít những vấn đề đơn giản là thích hợp với kiểu tìm kiếm vét hết mọi khả năng này (kiểu tìm kiếm vét cạn đòi hỏi phải kiểm tra tất cả các đỉnh). Do đó, các phương pháp tìm kiếm khác đã ra đời và phát triển. Ngược lại, nếu có một phương pháp luôn luôn chính xác nhằm đánh giá một thế cờ này là tốt hay kém so với thế kia, thì trò chơi trở thành đơn giản bằng cách chọn nước đi dẫn tới thế cờ tốt nhất. Do đó sẽ không cần phải tìm kiếm gì nữa. Rất tiếc, các thủ tục như vậy không hề có. Ta cần có chiến lược tìm kiếm trong trò chơi.




IV. Chiến lược tìm kiếm trong trò chơi
Một chiến lược thường được cả người lẫn máy dùng là phân tích thế cờ chỉ sau một số nước đi nào đó của cả hai bên. Sau khi "nhìn xa" xem bàn cờ có những khả năng biến đổi như thế nào sau một số nước, ta sẽ đánh giá độ xấu tốt của các thế cờ nhận được. Tiếp theo, ta sẽ chọn nước đi sẽ dẫn tới một thế cờ tốt nhất trong số đó có cân nhắc đến cách đi của cả hai bên. Với máy, thế cờ này được đánh giá là tốt hơn thế cờ kia nhờ so sánh điểm của thế đó do bộ lượng giá trả lại. Chúng ta chỉ có khả năng xét trước một số hữu hạn các nước (ví dụ đại kiện tướng chơi cờ vua có thể xét trước 8-10 nước đi, người thường chỉ 2-4 nước đi). Rõ ràng là nếu xét càng sâu thì chơi càng giỏi. Nhưng không thể thực hiện điều này với độ sâu quá lớn được do số nút ở độ sâu đó có thể trở nên lớn khủng khiếp và không đủ thời gian để phân tích. Nếu dừng ở một độ sâu hợp lý thì bộ phân tích có thể hoàn thành việc tính toán trong một thời gian hạn định.


V. Thủ tục Minimax[1]
Giả sử chúng ta có một bộ phân tích thế cờ có thể áp dụng tất cả các luật, các phương pháp đánh cờ khác nhau vào từng thế cờ và chuyển đổi chúng thành một con số đại diện (cho điểm thế cờ). Mặt khác, ta giả sử con số đó là dương khi áp dụng cho thế cờ của một đấu thủ (được gọi là người chơi cực đại - maximizer), và là âm khi áp dụng cho đấu thủ bên kia (được gọi là người chơi cực tiểu - minimizer). Quá trình tính toán cho điểm thế cờ được gọi là lượng giá tĩnh (static evaluation). Hàm thực hiện việc tính toán được gọi là một bộ lượng giá tĩnh, và giá trị nhận được gọi là điểm lượng giá tĩnh. Cả hai đấu thủ đều cố gắng đi như thế nào đó để đạt được điểm tuyệt đối lớn nhất. Người chơi cực đại sẽ tìm những nước đi dẫn đến điểm của mình trở nên lớn hơn (hay cao nhất có thể được) hay điểm của đối thủ bớt âm hơn (nhỏ hơn về giá trị tuyệt đối). Còn đấu thủ của anh ta, người chơi cực tiểu, lại ra sức phản kháng lại, để dẫn tới điểm âm của anh ta âm hơn hay điểm dương của đối thủ nhỏ đi (hình 1.4).



Ví dụ một phần cây trò chơi trong hình 1.5.



Người chơi cực đại hi vọng chọn nước đi bên phải để đạt được điểm 8. Thế nhưng nếu đi như vậy thì khi đến lượt đi của người chơi cực tiểu, anh ta sẽ cố gắng không cho người chơi cực đại đạt được điểm này bằng cách chọn nước đi nhánh bên trái và như vậy, người chơi cực đại chỉ được có 1 điểm thay vì 8. Ngược lại, nếu người chơi cực đại chọn nước đi bên trái, thì trong tình huống xấu nhất anh ta vẫn còn được 2 điểm, lớn hơn là chọn nước đi bên phải. Nói chung, người chơi cực đại sẽ phải tìm cách nhận ra các nước đi của đối phương tiếp theo làm cho điểm giảm xuống. Và tương tự như vậy, người chơi cực tiểu phải nhận biết được nước đi của người chơi cực đại cố gắng làm tăng điểm lên. Thủ tục tìm nước đi tốt nhất trên cây trò chơi như trên được gọi là thủ tục Minimax do điểm ở mỗi nút có thể là điểm cực đại hoặc có thể là điểm cực tiểu và có thuật toán như sau:

-------------------------------------------------------------------------------------------
Thuật toán Minimax
- Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm), tính giá trị tĩnh của thế cờ hiện tại ứng với người chơi ở đó. Ghi nhớ kết quả
- Nếu như mức đang xét là của người chơi cực tiểu, áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả nhỏ nhất
- Nếu như mức đang xét là của người chơi cực đại, áp dụng thủ tục Minimax này cho các con của nó. - Ghi nhớ kết quả lớn nhất.
-------------------------------------------------------------------------------------------


Viết chương trình cho thuật toán Minimax
Bây giờ, ta thử dựa vào phát biểu trên để viết chương trình cho thuật toán này bằng ngôn ngữ tựa Pascal. Đây là một hàm có tên là Minimax và sẽ là loại đệ qui. Trước hết, để hàm này biết đã đạt đến giới hạn tìm kiếm chưa, ta cần cung cấp cho nó một tham số về độ sâu tìm kiếm depth (để biết phải tìm đến đâu), đồng thời ta cũng phải cho biết thế cờ hiện tại pos để nó từ đó nó biết cách tính tiếp. Giá trị trả về của hàm chính là điểm của thế cờ (bàn cờ) pos. Vậy hàm sẽ có khai báo dạng:

function Minimax (pos, depth): integer;


Mỗi khi Minimax được gọi, nó sẽ càng gần đến giới hạn tìm kiếm, do đó ta sẽ gọi hàm này với độ sâu bằng độ sâu cũ trừ đi một. Đạt đến độ sâu giới hạn chính là khi depth = 0. Khi đạt độ sâu này ta sẽ gọi hàm lượng giá Eval để đánh giá chất lượng của thế cờ pos hiện tại (thực hiện điều một của thuật toán). Như vậy bước đầu hàm này có dạng sau:

function Minimax (pos, depth): integer; 
begin 
   if depth = 0 then { Đã đạt đến giới hạn }
      Minimax := Eval (pos)  { Tính giá trị thế cờ pos }
   else begin 
      ... 
      Minimax (pos, depth - 1); { Gọi đệ qui với độ sâu giản dần}
       ... 
   end; 
end;

Ở trên, Minimax được gọi với độ sâu giảm đi một. Đó là độ sâu của các thế cờ là con. Các thế cờ con pos' đó là các thế cờ được tạo ra từ pos bằng cách đi một nước đi hợp lệ m nào đó. Do đó ta phải có các lệnh thực hiện đi quân để đến các thế cờ mới. Để biết từ thế cờ pos có thể đi được những nước nào, ta dùng một thủ tục Gen có tham số là thế cờ cha pos. Thủ tục này sẽ cất các thế cờ con pos' đó vào bộ nhớ (dạng danh sách). Việc tiếp theo là ta lấy từng thế cờ đó ra và áp dụng tiếp thủ tục Minimax cho nó để tính điểm value của nó.

Vậy hàm Minimax bây giờ có dạng:

function Minimax (pos, depth): integer; 
begin 
   if depth = 0 then 
      Minimax := Eval (pos) { Tính giá trị thế cờ pos }
   else begin 
      Gen (pos); { Sinh ra mọi nước đi từ thế cờ pos }
      while còn lấy được một nước đi m do
      begin
         pos := Tính thế cờ mới nhờ đi m;
         value := Minimax (pos, depth-1); { Tính điểm của pos }
          ...
      end; 
      ... 
   end; 
end;

Theo phát biểu của thuật toán, ta thấy các điều 2 và 3 chỉ khác nhau ở cách chọn kết quả tốt nhất best phụ thuộc vào người chơi đang là người chơi cực đại hay cực tiểu. Cuối cùng thuật toán sẽ trả về điểm tốt nhất đạt được. Vậy hàm này được phát triển tiếp thành:

function Minimax (pos, depth): integer; 
begin 
   if depth = 0 then 
      Minimax := Eval (pos) { Tính giá trị thế cờ pos }
   else begin 
      Gen (pos); { Sinh ra mọi nước đi từ thế cờ pos }
      while còn lấy được một nước đi m do
      begin
          pos := Tính thế cờ mới nhờ đi m;
          value := Minimax (pos, depth-1); { Tính điểm của pos }
         { Chọn điểm tốt nhất tuỳ thuộc theo người chơi }
         if người chơi là người cực đại then
         begin
             if best < value then best := value; 
        end 
        else begin 
            if best > value then best := value; 
        end 
   end; 
   Minimax := best; { Trả về giá trị tốt nhất }
   end; 
end;

Thông thường để cho tiện (và cũng rất gần sự thực) ta coi cả hai người chơi (hai bên) có cùng cách đánh giá về một thế cờ. Có điều thế cờ này là tốt với một người thì phải được đánh giá là tồi với người kia và ngược lại. Trong máy tính cách thể hiện tốt nhất là ta cho điểm một thế cờ có thêm dấu âm dương: dấu âm dành cho người chơi cực đại và dấu âm cho người chơi cực tiểu. Với người chơi cực đại sẽ mong muốn điểm này càng dương càng tốt, còn người chơi cực tiểu lại mong muốn điểm này càng âm càng tốt. Do đó để dễ xử lí ta sẽ tuỳ theo mức người chơi mà đổi dấu giá trị đánh giá thế cờ pos. Chú ý rằng, thay đổi độ sâu là chuyển sang đối phương nên phải đổi dấu. Chương trình thực hiện đổi dấu như sau:

value := -Minimax (pos, depth-1); { Tính điểm của pos }

Cũng do dùng cùng hàm lượng giá nên khi đến lượt người chơi cực đại và cực tiểu có cùng cái nhìn như nhau về một thế cờ. Điều này dẫn đến có thể dùng cùng cách chọn nước đi tốt nhất cho họ (gộp được điều 2 và 3 lại với nhau được). Giá trị best cần được khởi đầu rất nhỏ để đảm bảo không vượt mọi giá trị value, tốt nhất là giá trị -vô cùng:

function Minimax (pos, depth): integer; 
begin 
   if depth = 0 then 
   Minimax := Eval (pos) { Tính giá trị thế cờ pos }
   else begin 
      best := -INFINITY; 
      Gen (pos); { Sinh ra mọi nước đi từ thế cờ pos }
      while còn lấy được một nước đi m do
      begin
         pos := Tính thế cờ mới nhờ đi m;
         value := -Minimax (pos, depth - 1);
         if value > best then best := value; 
      end; 
      Minimax := best; 
   end; 
end;

Thông thường, bàn cờ được biểu diễn bằng các biến toàn cục. Do đó thay cho truyền tham số là một bàn cờ mới pos vào thủ thục Minimax thì người ta biến đổi luôn biến toàn cục này nhờ thực hiện nước đi "thử" (nước đi dẫn đến bàn cờ mới pos). Sau khi Minimax thực hiện việc tính toán dựa vào bàn cờ lưu ở biến toàn cục thì thuật toán sẽ dùng một số thủ tục để loại bỏ nước đi này. Như vậy Minimax bỏ các tham số pos như sau:

function Minimax (depth): integer; 
begin 
   if depth = 0 then Minimax := Eval { Tính thế cờ pos trong biến toàn cục }
   else begin 
      best := -INFINITY; 
      Gen; { Sinh ra mọi nước đi từ thế cờ pos }
      while còn lấy được một nước đi m do
      begin
         thực hiện nước đi m;
         value := -Minimax (depth - 1);
         bỏ thực hiện nước đi m;
         if value > best then best := value;
      end; 
      Minimax := best; 
   end; 
end;

Thuật toán Minimax với việc đảo dấu mỗi khi thay đổi độ sâu như trên đôi khi được gọi là thuật toán Negamax.


Đánh giá thuật toán Minimax
Nếu hệ số nhánh trung bình của cây là b và ta thực hiện tìm kiếm đến độ sâu d thì số nút phải lượng giá ở đáy cây như ta đã biết là bd. Đây chính là số đo độ phức tạp của thuật toán. Nếu b = 40, d = 4 (các con số thường gặp trong trò chơi cờ) thì số nút phải lượng giá là 40^4 = 2560000 (trên 2 triệu rưỡi nút). Còn với b = 40, d = 5 thì số nút phải lượng giá sẽ tăng 40 lần nữa thành 40^5 = 102400000 (trên 102 triệu nút).

Lưu ý: toàn bộ ý tưởng của thuật toán này là dựa trên việc chuyển đổi mỗi thế cờ thành một con số để đánh giá. Rất tiếc là các con số này thường không tốt và không đủ để đánh giá hết mọi điều. Mặt khác, thuật toán này có thể rất tốn kém (chạy chậm) do việc sinh các nước đi và lượng giá rất tốn thời gian tính toán, do vậy độ sâu của cây trò chơi cũng bị hạn chế nhiều. Ta cần có thêm những cải tiến để cải thiện tình hình.


VI. Thủ tục AlphaBeta
Thủ tục AlphaBeta là một cải tiến thuật toán Minimax nhằm tỉa bớt nhánh của cây trò chơi, làm giảm số lượng nút phải sinh và lượng giá, do đó có thể tăng độ sâu của cây tìm kiếm. Giả sử hình 1.6 là một thế cờ mà hai nút đầu tiên đã được lượng giá. Nếu thực hiện thủ tục Minimax đối với các nút đó sẽ cho thấy người chơi cực đại đã được đảm bảo nếu đi nước bên trái sẽ được ít nhất là 2 điểm dù là các lượng giá của các nút khác cho kết quả như thế nào đi nữa.



Bây giờ, ta lại giả sử nút tiếp theo được lượng giá và cho kết quả là 1. Nếu đi vào nhánh này thì đối phương sẽ đảm bảo làm điểm của người chơi cực đại không thể vượt quá được giá trị 1 dù là các lượng giá của các nút khác cho kết quả như thế nào đi nữa. Do đó đến đây, nước đi tốt nhất là chọn nước đi bên trái với đảm bảo là ít nhất đạt được 2 điểm. Và do đó, hoàn toàn không cần thiết phải lượng giá nút còn lại.

[CXQ]

Nguyên tắc Alpha-Beta

Nếu biết điều đó thật sự tồi thì đừng mất thời gian tìm hiểu nó sẽ tồi tệ đến đâu
--------------------------------------------------------------------------------------------

Ý tưởng này được gọi là nguyên tắc Alpha-Beta do nó dùng trong thủ tục AlphaBeta (ta sẽ xét dưới đây). Hai tham số của thủ tục này (theo các đặt tên truyền thống) được gọi là alpha và beta và dùng để theo dõi các triển vọng - chúng cho biết các giá trị nằm ngoài khoảng [alpha, beta] là các điểm "thật sự tồi" và không cần phải xem xét nữa. Khoảng [alpha, beta] còn được gọi là cửa sổ alpha, beta. Trong ngữ cảnh của các trò chơi, nguyên tắc Alpha-Beta nói rằng, mỗi khi xem xét một nút bất kì, nên kiểm tra các thông tin đã biết về các nút cha, ông của nó. Rất có thể do có đủ thông tin từ cha, ông nên không cần phải làm bất cứ việc gì nữa cho nút này. Cũng vậy, nguyên tắc này cũng giúp chỉnh sửa hoặc xác định chính xác giá trị tại nút cha, ông nó. Như trên nói, một cách để tiện theo dõi quá trình tính toán là dùng các tham số alpha và beta để ghi lại các thông tin theo dõi cần thiết. Thủ tục AlphaBeta được bắt đầu tại nút gốc với giá trị của alpha là -vôcùng và beta là +vôcùng. Thủ tục sẽ tự gọi đệ quy chính nó với khoảng cách giữa các giá trị alpha và beta ngày càng hẹp hơn.


Viết chương trình cho thuật toán AlphaBeta

Từ phát biểu trên ta sẽ xây dựng hàm AlphaBeta bằng ngôn ngữ tựa Pascal. Hàm này sẽ có dạng khai báo như dưới, trong đó depth là độ sâu tìm kiếm, INFINITY là giá trị vô cùng, thuật toán tính toán dựa trên thế cờ hiện tại pos là các biến toàn cục:

function AlphaBeta(alpha, beta, depth): integer; 
begin 
   if depth = 0 then 
   AlphaBeta := Eval  { Tính giá trị thế cờ pos }
   else begin 
      best := -INFINITY; 
      Gen;  { Sinh ra mọi nước đi từ vị trí pos }
      while (còn lấy được một nước đi m) and (best < beta) do
      begin
         if best > alpha then alpha := best; 
         thực hiện nước đi m;
         value := -AlphaBeta(-beta, -alpha, depth-1);
         bỏ thực hiện nước đi m;
         if value > best then best := value;
      end; 
      AlphaBeta := best; 
   end; 
end;

Lời gọi thủ tục AlphaBeta đầu tiên với độ sâu tìm kiếm 4 và thế cờ hiện tại pos có dạng như sau:

AlphaBeta(-INFINITY, +INFINITY, 4);

Cũng tương tự như thuật toán Minimax ta đã gộp hai mục 2 và 3 làm một nhờ việc đổi dấu thích hợp. So với thuật toán Minimax thì trong thuật toán AlphaBeta đã đưa thêm hai biến alpha, beta làm hai mức ngưỡng. Ta thấy cứ mỗi khi best >= beta thì thuật toán không thực hiện tiếp vòng lặp, có nghĩa là nó không chịu mở rộng tiếp những nhánh còn lại nữa. Các nhánh đó đã bị cắt bỏ - và do đó ta sẽ tiết kiệm được thời gian. Việc cắt bỏ này hoàn toàn an toàn với những lí do ta đã xét ở trên. Ta thấy rằng mỗi lần hàm này được gọi thì chỉ có tham số beta được dùng để so sánh cắt bỏ, còn tham số alpha không được dùng. Tuy nhiên khi áp dụng cùng thuật toán cho cây con thì ta đã hoán vị hai giá trị alpha, beta cho nhau (và đảo cả dấu), do đó alpha sẽ có tác dụng trong độ sâu sau, rồi độ sâu sau nữa lại đến lượt beta... Nói cách khác, một giá trị chỉ luôn ảnh hưởng đến người chơi cực đại, còn giá trị kia lại luôn ảnh hưởng đến người chơi cực tiểu. Chúng là các ngưỡng của họ (ngưỡng giữa các nước đi được chấp nhận và không chấp nhận). Những nước đi cần quan tâm phải nằm lọt giữa hai giá trị này. Dần dần khoảng cách giữa hai giá trị alpha - beta càng ngày càng thu hẹp và dẫn đến các nhánh cây có giá trị nằm ngoài khoảng này nhanh chóng bị cắt bỏ (hình 1.7).



Đánh giá thuật toán AlphaBeta
Trong điều kiện lí tưởng, thuật toán AlphaBeta chỉ phải xét số nút theo công thức:


= với d chẵn

= với d lẻ


Với b = 40 và d = 4 ta có số nút phải xét là 2x40^2 - 1 = 3199. Như vậy trong điều kiện lí tưởng thì số nút phải xét nhờ AlphaBeta (chỉ khoảng 3 nghìn nút) ít hơn thuật toán Minimax (hơn 2,5 triệu nút) là 2560000 / 3199 khoảng 800 lần. Còn với b = 40 và d = 5 ta có số nút phải xét là 40^3 + 40^(5/2) - 1 = 64000+10119-1 = 74118. Số nút phải xét nhờ AlphaBeta ít hơn thuật toán Minimax (hơn 102 triệu nút) là 102400000/74118 = 1382 lần.

Dưới đây là bảng so sánh số nút phải xét giữa hai thuật toán Minimax và AlphaBeta.




Ta có thể nhận xét như sau:

- Số lần tăng số nút khi tăng độ sâu của Minimax luôn là hệ số phân nhánh b, trong trường hợp này là 40. Số lần tăng của AlphaBeta ít hơn nhiều: chỉ cỡ 1.7 lần khi tăng từ d lẻ sang d chẵn và 23.2 lần khi từ d chẵn sang lẻ - trung bình chỉ tăng khoảng hơn 6 lần khi tăng d
- Số nút của AlphaBeta tăng chậm hơn rất nhiều lần so với Minimax. Tỉ số nút phải xét giữa hai thuật toán này càng cao khi d càng lớn.
Công thức tính số nút cho thấy số nút phải xét khi dùng AlphaBeta ít hơn nhiều so với Minimax nhưng vẫn là hàm số mũ và vẫn dẫn tới bùng nổ tổ hợp. Thuật toán AlphaBeta hoàn toàn không chống được bùng nổ tổ hợp mà chỉ làm giảm tốc độ bùng nổ. Tuy trong thực tế số nút phải xét (lượng giá) thường nhiều hơn trong điều kiện lí tưởng nhưng nó vẫn đủ để tiết kiệm khá nhiều thời gian. Trong cùng một khoảng thời gian, thuật toán AlphaBeta có thể tìm đến độ sâu gấp hai lần độ sâu tìm kiếm bằng Minimax. Hình 1.8 là đồ thị so sánh giữa hai thuật toán này.




Ví dụ: Ta sẽ xem xét thuật toán AlphaBeta hoạt động như thế nào đối với cây trò chơi như trong hình 1.9.





Cây này có độ sâu bằng 3 và hệ số phân nhánh bằng 3. Các thứ tự kết luận (các con số bên trái) được đưa ra như sau:

[1-2] Tìm kiếm đi xuống dưới theo nhánh trái cho đến lá. Ở đây giá trị tĩnh thu được là 8. Giá trị đầu tiên này do người chơi cực đại được phép chọn trong ba giá trị ở nhánh này đã đảm bảo rằng là kết quả thu được sẽ ít nhất là bằng 8. Điều lưu ý này được bước 2 ghi lại.

[3-5] Để chắc chắn không còn có điểm nào cao hơn 8, người chơi cực đại phải xét cả hai thế cờ còn lại và thu được các giá trị 7 và 2. Do đó đến đây đã kết luận chính xác điểm cao nhất có thể đạt được ở cây con là đúng bằng 8.

[6]. Leo lên một tầng cây. Đây là các nước đi của người chơi cực tiểu. Ta không hi vọng anh ta cho người chơi cực đại được nhiều điểm nên có thể tạm kết luận ở mức này là sẽ đạt được nhiều nhất là 8 điểm.

[7-8]. Để xem người chơi cực tiểu còn lựa chọn nào tốt hơn (và tồi tệ hơn cho người chơi cực đại) ta phải xem xét cả hai nước đi còn lại. Nước đi còn lại đầu tiên dẫn đến giá trị lượng giá tĩnh là 9 - một giá trị lớn hơn 8. Như vậy nhánh giữa là tồi tệ hơn cho người chơi cực tiểu. Đến đây việc cắt bỏ được thực hiện - đừng hòng người chơi cực đại với tới được điểm đó khi đã có sẵn lựa chọn thấp hơn cho anh ta (là 8). Điều này cũng dẫn đến không cần thiết phải xét hai nút còn lại - đằng nào nhánh giữa cũng đủ tồi tệ rồi và người chơi cực tiểu sẽ không chọn nó để đi.

[9-14]. Người chơi cực tiểu cần phải khảo sát tiếp lựa chọn cuối cùng. Cách làm tương tự như phần trên. Ở đây phải lượng giá cả ba nút cây và kết luận cuối cùng được đưa ra là người chơi cực đại đi giỏi lắm thì chỉ đạt được 4 điểm.

[15]. Như vậy nhờ việc khảo sát nhánh cây bên phải người chơi cực tiểu thấy rằng nếu chọn đi theo nhánh này thì người chơi cực đại chỉ được có 4 điểm thay cho 8.

[16]. Bây giờ ta có thể kết luận ở mức trên cùng. Mức này là của người chơi cực đại. Anh ta thấy rằng nếu chọn đi theo nhánh trái thì được 4 điểm. Như vậy anh ta đã chắc chắn điểm của mình sẽ ít nhất là 4 rồi. Để xem liệu có thể đạt được điểm cao hơn nữa hay không cần phải xem xét hai nhánh còn lại.

[17-30]. Tương tự như phần trên, ta kết luận nhánh giữa sẽ mang lại cho người chơi cực đại 5 điểm. 31. Cũng tương tự như kết luận 16, ở đây ta kết luận khả quan hơn là người chơi cực đại đã cầm chắc 5 điểm và có thể còn cao hơn.

[32-38] Ta kết luận được rất nhanh là cây con bên phải chỉ cho "thu hoạch" nhiều nhất là 3 điểm - một điểm số quá kém do đó thuật toán không buồn xem xét các trường hợp còn lại nữa. Do đó đã tiết kiệm được 6 nút không cần phải lượng giá và cũng không phải sinh nước đi cho hai trường hợp.

[39]. Kết luận cuối cùng là điểm cao nhất mà người chơi cực đại có thể thu được là 5 điểm nhờ chọn đi theo nhánh giữa.



VII. Hướng cải thiện việc tỉa nhánh của thuật toán AlphaBeta
Thuật toán AlphaBeta nói chung giúp chúng ta tiết kiệm nhiều thời gian so với Minimax mà vẫn đảm bảo kết quả tìm kiếm chính xác. Tuy nhiên lượng tiết kiệm này không ổn định - phụ thuộc vào số nút mà nó cắt bỏ. Trong trường hợp xấu nhất thuật toán không cắt được một nhánh nào và phải xét số nút đúng bằng Minimax. Ta cần đẩy mạnh việc cắt bỏ nhờ đẩy nhanh sự thu hẹp của cửa sổ tìm kiếm alpha - beta. Cửa sổ này được thu hẹp một bước khi gặp một giá trị mới tốt hơn giá trị cũ. Khi gặp giá trị tốt nhất thì cửa sổ này thu hẹp nhất. Do đó nếu càng sớm gặp giá trị tốt nhất thì cửa sổ càng chóng thu hẹp. Như vậy phải làm sao cho các nút ở lá được sắp xếp theo trật tự từ cao xuống thấp. Trật tự này càng tốt bao nhiêu thì thuật toán chạy càng nhanh bấy nhiêu (các công thức về số nút phải lượng giá trong điều kiện lí tưởng ở trên tính được với trật tự là tốt nhất). Ta sẽ trở lại phần này trong một chương riêng.


Tổng kết chương 1
Chương này trình bầy những kiến thức chung về trò chơi cờ, các định nghĩa và thế nào là cây trò chơi. Do bùng nổ tổ hợp quá lớn của cây trò chơi mà cả người và máy không thể (và không bao giờ) có thể tìm kiếm vét cạn (hết mọi khả năng). Do đó phương pháp tìm kiếm duy nhất là chỉ tìm kiếm đến một độ sâu giới hạn nào đó và chọn nước đi dẫn đến một thế cờ có lợi nhất cho mình. Do phải tính cả khả năng chống trả của đối phương nên ta không dùng được các thuật toán tìm kiếm thông thường. Phải dùng một thuật toán tìm kiếm riêng cho cây trò chơi. Đó là thuật toán Minimax và cải tiến của nó là AlphaBeta. Tuy cả hai thuật toán đều không tránh được bùng nổ tổ hợp nhưng AlphaBeta làm chậm bùng nổ tổ hợp hơn nên được dùng nhiều trong các trò chơi cờ.

[CXQ]

Chương 2: CỜ TƯỚNG - PHIÊN BẢN ĐẦU TIÊN (VERY SIMPLE CHINESE CHESS PROGRAM - VSCCP 1.0). Link dowload: http://www.mediafire.com/?uu6tpxaqoiw9j3l
Rất tiếc phần 3 tôi tìm không có

[xuan2009]

Ông này là một người tài giỏi. Ông khẳng định tài năng bằng những sản phẩm trí tuệ chứ không cần miệng lưỡi hay sự nhõng nhẻo của đàn bà. Tôi xin cúi đầu khâm phục ông. Chúc ông luôn mạnh giỏi. KÍNH CHÀO.

[giaitricotuong]

Bạn ơi viết về book đi nhé.Cái đó hot hơn.Thanks!!!

[romantic1]

I. Giới thiệu

Trò chơi Cờ Tướng (tên phiên âm Trung Quốc XiangQi, tên tiếng Anh Chinese Chess) là một minh hoạ rất tốt cho bài toán tìm kiếm trên cây trò chơi và áp dụng thuật toán AlphaBeta trên cây này như thế nào. Đây là một trò chơi thú vị và tương đối phổ biến ở Việt nam, châu Á cũng như trên toàn thế giới. Nó tạo cảm giác dường như máy tính có thể suy nghĩ và đọ sức với con người (thực tế cho đến nay nó vẫn chỉ tính toán mà thôi). Cờ Tướng là loại cờ có độ phức tạp và rất nhiều mặt tương đương với cờ Vua.
Trong phần này, chúng tôi sẽ giới thiệu với bạn những kiến thức cơ bản nhất về một chương trình chơi cờ phải như thế nào. Các chương trình mẫu VSCCP (Very Simple Chinese Chess Program - Chương trình Cờ Tướng rất đơn giản) cũng hết sức đơn giản và có đầy đủ trong các phụ lục.
II. Viết chương trình chơi cờ VSCCP 1.0
1. Biểu diễn bàn cờ và quân cờ

Bàn cờ trong trò chơi cờ Tướng là một bảng chữ nhật bao gồm 9 đường dọc và 10 đường ngang. Các quân cờ chia làm hai bên đứng tại các giao điểm của các đường. Bàn cờ và vị trí khởi đầu các quân cờ như hình 2.1. Cách đơn giản nhất để biểu diễn một bàn cờ trong máy tính là ta dùng một mảng hai chiều, kích thước 9 x 10:
int piece[1..10, 1..9] ;
Mảng trên hoạt động tốt nhưng có cái bất tiện là ta phải dùng tới hai chỉ số để truy cập vào mảng (ví dụ vị trí quân Pháo góc trên bên trái (cột 2, dòng 3) là piece[3, 2]). Một cải tiến nhỏ là ta dùng mảng một chiều như sau:
int piece[1..90];
Truy nhập đến vị trí quân Pháo góc trên bên trái lúc này là piece[20].


Các ô của mảng sẽ chứa những giá trị khác nhau cho biết đó là quân cờ gì. Mỗi quân cờ sẽ được gán một mã số khác nhau như bảng dưới đây. Các chỗ trống (không có quân cờ) sẽ được điền kí hiệu trống (EMPTY):



Quân cờ ------Kí hiệu ------- Giá trị
Tốt (Chốt)----PAWN----------0
Sĩ -----------BISHOP---------1
Tượng ------ELEPHANT -------2
Mã ----------KNIGHT --------3
Pháo --------CANNON --------4
Xe -----------ROOK----------5
Tướng --------KING----------6
Trống--------EMPTY---------7


Ngoài mục đích gán mỗi quân cờ một mã số để phân biệt, mã này còn giúp ta ước lượng sơ bộ tầm quan trọng của quân cờ đó.
Như vậy, lúc khởi đầu, các ô trong mảng sẽ được gán các giá trị quân cờ nhờ khai báo const (trong Java) như dưới, trong đó BOARD_SIZE (kích thước bàn cờ = 90) là một hằng số đã được định nghĩa trước đó:

char piece[BOARD_SIZE]= {
5,3,2,1,6,1,2,3,5,
7,7,7,7,7,7,7,7,7,
7,4,7,7,7,7,7,4,7,
0,7,0,7,0,7,0,7,0,
7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,
0,7,0,7,0,7,0,7,0,
7,4,7,7,7,7,7,4,7,
7,7,7,7,7,7,7,7,7,
5,3,2,1,6,1,2,3,5};

Đến đây, bàn cờ còn chưa có thông tin để phân biệt một quân cờ là của bên nào. Ta có thể cải tiến thay cho kiểu byte của mảng piece là một bản ghi nhằm lưu thêm các thông tin này. Chúng tôi xin giới thiệu một phương pháp đơn giản là dùng thêm một mảng nữa - mảng color, để lưu các thông tin về bên. Hai bên được gán kí hiệu và mã như bảng dưới. Những chỗ trống sẽ dùng cùng kí hiệu trống EMPTY.

Bên-------------Đen----------Trắng---------Trống---
Kí hiệu---------DARK---------LIGHT----------EMPTY---
Giá trị-----------0-------------1--------------7-----

Ta lại có thông tin về bên được khai báo khởi đầu tương tự:

char color[BOARD_SIZE]= {
0, 0, 0, 0, 0, 0, 0, 0, 0,
7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 0, 7, 7, 7, 7, 7, 0, 7,
0, 7, 0, 7, 0, 7, 0, 7, 0,
7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7,
1, 7, 1, 7, 1, 7, 1, 7, 1,
7, 1, 7, 7, 7, 7, 7, 1, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7,
1, 1, 1, 1, 1, 1, 1, 1, 1};
Để biết bên nào tới lượt đi, ta dùng một biến toàn cục side chứa một trong hai giá trị LIGHT và DARK. Một biến toàn cục khác xside sẽ có sẵn giá trị ngược với side để tiện tính toán (ví dụ nếu side = LIGHT thì xside = DARK). Khi tới phiên đối phương đi, ta cần đảo ngược giá trị trong cả side và xside bằng các lệnh như sau (chú ý là LIGHT+DARK = 1):
side := xside; xside := 1 - xside;
Ngoài ra, ta còn khai báo biến computerside cũng chỉ có một trong hai giá trị LIGHT và DARK nhằm cho biết bên nào là máy. Để hiện bàn cờ, phương pháp đơn giản nhất là hiện ở chế độ text (văn bản). Tuy cách này trông xấu và thường không dùng trong các chương trình có trên thị trường nhưng nó có các ưu điểm nổi trội sau:

* Vẫn hiện được bàn cờ rất đầy đủ, trực quan, dễ hiểu, cho phép theo dõi và thi đấu bình thường.
* Rất đơn giản và tin cậy. Bạn sẽ đỡ nhiều thời gian tìm hiểu và phát triển giao diện, dồn sức cho việc quan trọng hơn - làm chương trình chơi hay hơn. Giao diện đồ hoạ chỉ cần thiết lúc hoàn chỉnh - lúc bạn "đóng gói" chương trình.
* Việc hiện thêm các thông tin để kiểm tra, tìm lỗi rất dễ dàng. Rõ ràng việc dùng hai thủ tục có sẵn của Pascal là gotoxy và write thì dễ, nhanh và đảm bảo hơn các hàm đồ hoạ.
* Dễ chuyển đổi hệ máy và hệ điều hành. Có thể bạn sẽ muốn thử chạy trên những máy tính có nền tảng khác như máy mini, macintosh, hệ điều hành Windows 3.1, Win95, Win98, WinNT, System7, UNIX...
* Bạn có thể tự phát triển giao diện đồ hoạ và cài chuột theo ý mình.

Quân cờ được biểu diễn bằng một chữ cái viết hoa đứng đầu tên của nó. Quân hai bên sẽ có mầu khác nhau. Do quân Tướng và Tượng có cùng chữ cái đầu T nên để tránh nhầm lẫn ta dùng chữ V (Voi) biểu diễn quân Tượng. Tuy quân Tốt và Tướng cũng có cùng chữ cái đầu nhưng ta không sợ nhầm do Tốt không thể nhập cung bên mình được. Nó chỉ có thể "tiếp chuyện" Tướng đối phương, nhưng lúc này hai bên lại phân biệt được nhờ mầu (các phương pháp khác là dùng chữ cái đầu tên tiếng Anh: P-Tốt, E-Tượng, N-Mã, B-Sĩ, R-Xe, C-Pháo, K-Tướng; hoặc theo qui định của Liên đoàn cờ Việt Nam: Tg-Tướng, S-Sĩ, T-Tượng, X-Xe, P-Pháo, M-Mã, C-Chốt).
Ta sẽ hiện bàn cờ ở dạng như hình 2.3. Chú ý cách đánh kí hiệu các vị trí trong bàn cờ bằng chữ và số giống như bàn cờ Vua.
Để hiện một quân cờ, ta viết một thủ tục DrawCell với tham số là vị trí bàn cờ. Ngoài ra, nó còn một tham số nữa cho biết sẽ hiện mầu nền của quân cờ với mầu bình thường NORMAL (sẽ có nền đen) hay mầu khác SELECT (sẽ có nền xanh sẫm) để thể hiện quân cờ đó được chọn (phục vụ cho chọn và đi quân của người chơi).
Class void DrawCell(int pos,int mode);
Như vậy, để hiện toàn bộ bàn cờ ta chỉ cần gọi một vòng lặp for là xong:
for (int i = 1 ;i<BOARD_SIZE ; i++) DrawCell(i, NORMAL);



2. Sinh nước đi

Một trong những việc quan trọng nhất để máy tính có thể chơi được cờ là phải chỉ cho nó biết mọi nước đi có thể đi được từ một thế cờ. Máy sẽ tính toán để chọn nước đi có lợi nhất cho nó. Các yêu cầu chính đối với một thủ tục sinh nước đi là:

* Chính xác (rất quan trọng). Một nước đi sai sẽ làm hỏng mọi tính toán. Đồng thời chương trình có thể bị trọng tài xử thua luôn. Do số lượng nước đi sinh ra lớn, luật đi quân nhiều và phức tạp nên việc kiểm tra tính đúng đắn tương đối khó.
* Đầy đủ (rất quan trọng). Sinh được mọi nước đi có thể có từ một thế cờ.
* Nhanh. Do chức năng này phải sinh được hàng triệu nước đi mỗi khi máy đến lượt nên giảm thời gian sinh nước đi có ý nghĩa rất lớn.

Sinh nước đi là một thuật toán vét cạn. Máy sẽ tìm mọi nước đi hợp lệ có thể có. Máy phải sinh được từ những nước đi rất hay cho đến những nước đi rất ngớ ngẩn (như đẩy Tướng vào vị trí khống chế của đối phương). Ta hình dung ngay thủ tục sinh nước đi Gen sẽ có đầy những vòng lặp for, các câu lệnh kiểm tra if và rẽ nhánh case, trong đó các phép tính kiểm tra giới hạn chiếm một phần đáng kể. Thủ tục này luôn sinh nước cho bên đang tới lượt chơi căn cứ vào nội dung của biến side. Đây là một trong những thủ tục phức tạp và dễ sai nhất.
Một nước đi có hai giá trị cần quan tâm. Đó là điểm xuất phát (from) và điểm đến (dest). Ta sẽ khai báo một cấu trúc move như sau để dùng những nơi cần đến dữ liệu nước đi.

type
move = record { Định nghĩa cấu trúc nước đi }
from, dest: byte;
end;


Kiểm tra giới hạn bàn cờ
Ví dụ có một quân Xe nằm ở ô số 84 (trong mảng piece). Bây giờ ta sẽ sinh thử một nước đi sang trái một ô cho nó. Nước đi sang trái một ô được chuyển thành ô số 83 là một vị trí cùng hàng với ô xuất phát nên được chấp nhận. Một nước đi khác cần phải xem xét là sang trái ba ô - ô 81. Ô 81 tuy có trong bàn cờ nhưng khác hàng nên không được chấp nhận. Như vậy, muốn biết ô của nước đi sang trái có được phép không ta phải kiểm tra xem nó có cùng hàng với ô xuất phát không. Việc kiểm tra thực hiện bằng cách chia cho 9 (kích thước của một dòng) và lấy phần nguyên (trước đó lại phải chuyển thứ tự ô về gốc là 0 bằng cách trừ đi 1). Ta thấy ((83-1) div 9) = ((84-1) div 9) nên ô 83 được chấp nhận; trong khi đó do ((81-1) div 9) <> ((84-1) div 9) nên kết luận là nước đi đến ô 81 không hợp lệ (hình 2.5).

Các nước đi vừa sinh ra sẽ được đưa vào danh sách nước đi nhờ gọi thủ tục Gen_push. Thủ tục này có hai tham số là vị trí xuất phát của quân cờ sẽ đi và nơi đến dest của quân cờ đó.
Dưới đây là đoạn chương trình dùng để sinh những nước đi sang trái của một quân Xe, trong đó x là vị trí của quân Xe này .



i = x - 1; //Nước sang trái đầu tiên
while ((i-1) / 9) = ((x-1) / 9) {
if (ô thứ i là trống) or (ô thứ i có quân đối phương)
gen_push(vị trí của Xe, vị trí ô đang xét);
if ô thứ i không trống
break; // Kết thúc quá trình sinh nước đi sang trái
i = i - 1; // Xét tiếp vị trí bên trái

}

Việc sinh những nước đi theo chiều khác cũng tương tự (ví dụ để sinh nước đi theo chiều đứng ta chỉ cần cộng hoặc trừ một bội số của 9) nhưng điều kiện kiểm tra sẽ khác nhau. Như vậy, chương trình sinh nước đi Gen có dạng như sau:
for ( Xét lần lượt từng quân cờ bên hiện tại )
case quâncờ of
Xe: while ( Xét lần lượt tất cả các ô từ bên phải Xe cho đến lề trái bàn cờ ) {
if (ô đang xét là ô trống) or (ô đang xét chứa quân đối phương) gen_push(vị trí của Xe, vị trí ô đang xét)
if (ô đang xét không trống) break;
}
while (Xét lần lượt tất cả các ô từ bên trái Xe cho đến lề phải bàn cờ ) {
...}
while (Xét lần lượt tất cả các ô từ bên trên Xe cho đến lề trên bàn cờ) {
... }
while Xét lần lượt tất cả các ô từ bên dưới Xe cho đến lề dưới bàn cờ {
...}
Break;


Pháo:
...

Phương pháp này có nhược điểm là chương trình phải viết phức tạp, cồng kềnh, khó tìm lỗi nhưng khá nhanh.
Trong chương trình mẫu VSCCP, chúng tôi giới thiệu một kĩ thuật khác có tên gọi là "hộp thư" (mail box - do các bảng của nó có dạng các hộp phân thư). Mục đích chính của kĩ thuật này là nhằm giảm bớt các phép kiểm tra vượt giới hạn bàn cờ và làm đơn giản chương trình. Mấu chốt là thay cho bàn cờ có kích thước bình thường 9x10 = 90, ta dùng một bàn cờ mở rộng, mỗi chiều có thêm 2 đường nữa (bàn cờ mới có kích thước 13x14 = 182). Các ô ứng với các đường bao mở rộng đều có giá trị -1, tức là các giá trị báo vượt biên. Các nước đi trên bàn cờ 9x10 được chuyển tương ứng sang bàn cờ này. Nếu một nước đi được sinh ra lại rơi vào một trong hai đường bao thì có nghĩa nó đã rơi ra ngoài bàn cờ rồi, phải bỏ đi và ngừng sinh nước về phía đó. Sở dĩ có đến hai đường biên (chứ không phải một) do quân Mã và Tượng có thể nhẩy xa đến hai ô (hình 2.6).

Việc chuyển đổi toạ độ thực hiện nhờ hai mảng. Mảng mailbox90 dùng để chuyển từ toạ độ bàn cờ thường sang toạ độ bàn cờ mới. Mảng ứng với bàn cờ mới - mailbox182 dùng để kiểm tra các nước đi vượt quá đường biên và dữ liệu để chuyển trở lại toạ độ bình thường.
Ví dụ, nếu vị trí quân Xe nằm ở ô số 84 (trong mảng piece) như hình 2.5, thì khi đổi sang bàn cờ mở rộng sẽ thành vị trí mailbox90[84] = 148. Có nghĩa là nó ứng với ô thứ 148 của mảng mailbox182. Bây giờ ta sẽ sinh thử một nước đi sang trái một ô cho quân Xe này. Việc sinh và kiểm tra sẽ được thực hiện trong bàn cờ mở rộng, nước đi mới là ô số 148 - 1 = 147. Do mailbox182[147] = 83 ¹ -1 nên nước đi này được chấp nhận. Số 83 cho biết kết quả sang trái một ô là vị trí 83 trong bàn cờ bình thường. Tuy nhiên, nước đi sang trái ba ô, có số 148 - 3 = 145 và mailbox182[145] = -1 cho biết đó là một nước đi không hợp lệ.
Chương trình cũng cần kiểm tra số nước đi tối đa theo một hướng của quân cờ đang xét. Chỉ có quân Pháo và Xe có thể đi đến 9 nước đi, còn các quân khác có nhiều nhất là 1.
Việc đi một quân sang vị trí mới thực chất là ta đã thay đổi toạ độ của nó bằng cách cộng với một hằng số (dương hoặc âm). Ở trên ta đã thấy để quân Xe sang trái một nước ta đã phải cộng vị trí hiện tại với -1. Để sinh một ô mới theo hàng dọc, ta phải cộng với +13 hoặc -13 (chú ý, việc sinh nước và kiểm tra hợp lệ đều dựa vào mảng mailbox182 nên giá trị 13 là kích thước một dòng của mảng này). Để sinh các nước đi chéo ta phải cộng trừ với một hằng số khác. Ta nên lưu các hằng số này vào mảng offset có 2 chiều. Một chiều dựa vào loại quân cờ nên chỉ số được đánh từ 1 đến 7. Chiều còn lại là số hướng đi tối đa của một quân cờ. Quân cờ có nhiều hướng nhất là quân Mã có tới 8 hướng nên chiều này được khai báo chỉ số từ 1 đến 8. Các quân cờ có số hướng ít hơn sẽ được điền 0 vào phần thừa. Chú ý là nước đi quân Tốt của hai bên khác nhau hướng tiến. Để tiết kiệm ta chỉ lưu nước tiến của Tốt đen, còn nước tiến của Tốt trắng chỉ đơn giản lấy ngược dấu.

Kiểm tra vị trí được phép đến
Việc chuyển toạ độ từ bàn cờ thường sang bàn cờ mở rộng chỉ giúp ta loại bỏ được các nước vượt quá biên. Ta còn phải kiểm tra một số giới hạn khác. Ví dụ như Tướng và Sĩ không thể đi ra ngoài cung, Tượng chỉ được phép ở 7 điểm cố định phía bên mình, Tốt chỉ được phép tung hoành trên đất đối phương, còn phía bên mình cũng bị giới hạn ngặt nghèo một số ô... Để thực hiện những phép kiểm tra này, ta dùng một mảng là legalmove ứng với từng ô trên bàn cờ sẽ cung cấp các thông tin này. Để kiểm tra một quân cờ có được phép ở đó không, ta dùng một mặt nạ bít Maskpiece mà tuỳ theo từng quân sẽ có giá trị khác nhau. Nếu ở ô cần kiểm tra có bit trùng với mặt nạ này được đặt là 1 thì quân cờ đó được phép đến ô đấy.

Ví dụ, ô số 3 có giá trị legalmove[3] = 5 (chuyển thành số nhị phân là 00000101) cho biết các quân cờ được phép đi đến đó là Tượng, Xe, Pháo, Mã.
Ngoài ra, ta còn phải kiểm tra nước bị cản (đối với Tượng và Mã) và xử lí cách ăn quân của quân Pháo như một trường hợp đặc biệt. Như vậy, tổng thể sinh các nước đi cho một quân cờ có dạng như sau:
p = piece[i]; // Sinh nước đi cho quân cờ p ở vị trí i
for (int j = 1 ;j< 8 ; j++) { //Số hướng đi tối đa
if (offset[p,j] = 0) break;
x=mailbox90[i]; // Chuyển sang bàn cờ mở rộng
if ((p == ROOK)||(p== CANNON])) n = 9 ;
else n = 1;
for (t=1 ; t<n ; t++ ) { // Số nước có thể đi theo một hướng
if ((p==PAWN)&& (side==LIGHT)) x = x - offset[p, j];
else x = x + offset[p, j]; // Nước đi mới
y = mailbox182[x]; // Chuyển về toạ độ bình thường
if (side == DARK) t = y;
else t = 91-y;
if ((y==-1) || /*Ra ngoài lề ? */ ((legalmove[t] || maskpiece[p])==0)) // Được phép ở vị trí này không ?
break; // Thoát nếu nước đi không hợp lệ
}
// Kiểm tra nước cản với Tượng, Mã và xử lí Pháo ở đây
...

Một vấn đề nữa là luật hai Tướng không được đối mặt trực tiếp với nhau. Việc kiểm tra được thực hiện nhờ hàm kingface. Hàm sẽ trả lại giá trị true nếu nước vừa đi gây hở mặt Tướng. Hàm này có thể được đặt trong thủ tục sinh nước Gen. Tuy nhiên đơn giản hơn, ta đặt nó trong thủ tục gen_push, nếu hở mặt Tướng thủ tục này sẽ không đưa nước đi đó vào danh sách các nước đi.

3. Đánh giá một thế cờ

Đánh giá một thế cờ là một trong những nhiệm vụ quyết định chương trình chơi cờ của bạn có là "cao thủ" hay không. Căn cứ vào một thế cờ máy sẽ gán cho nó một điểm số (lượng giá tĩnh) để đánh giá độ tốt - xấu. Nhờ điểm này máy mới có thể so sánh các thế cờ với nhau và biết chọn nước đi tốt nhất. Đây là một nhiệm vụ rất khó khăn và phức tạp do không tồn tại một thuật toán tổng quát và thống nhất nào để tính điểm cả. Điểm của một thế cờ dựa trên rất nhiều yếu tố mà khó có thể số hoá hết được như phụ thuộc vào số lượng và giá trị các quân cờ hiện tại, phụ thuộc vào tính hãm, tính biến, thế công, thế thủ của từng quân cờ cũng như cả cục diện trận đấu. Ví dụ, một cặp Mã giao chân, có thể sát cánh tiến quân và tựa lưng phòng thủ thường có giá hơn hai Mã đứng rời. Nhưng cũng có lúc hai Mã đứng rời lại tốt hơn hai Mã giao chân khi Mã này lại cản Mã kia trong một thế trận nào đó. Ta cũng biết rằng, "lạc nước hai Xe đành bỏ phí, gặp thời một Tốt cũng thành công", thế nhưng số hoá điều này qua hàm lượng giá quả là một điều khó quá sức.
Chúng ta bắt đầu với việc công nhận các giả thuyết sau:

1. Ta có thể biểu diễn chất lượng một thế cờ bằng một con số. Ví dụ, con số đó có thể là đánh giá của ta về xác suất chiến thắng, nhưng đối với đa số chương trình thì con số đó không có gì đặc biệt, nó chỉ là con số mà mục đích chính là so sánh được với nhau.
2. Chúng ta nên đo chất lượng của một thế cờ tương tự như phép đo của đối phương (do đó, nếu ta coi là đạt được một thế tốt thì đối phương của ta phải thấy đó là thế xấu đối với họ và ngược lại). Điều này tuy không thật đúng lắm, nhưng nó giúp cho thuật toán tìm kiếm của ta làm việc tốt và trong thực tế cũng khá gần với sự thật.

Trong chương này chúng ta chỉ cài đặt phương pháp đơn giản nhưng cơ bản nhất: lượng giá dựa trên cơ sở giá trị của từng quân cờ. Cách tính này sẽ lấy tổng giá trị các quân cờ hiện có của bên mình trừ đi tổng giá trị các quân cờ hiện có của đối phương. Do đó, một thế cờ này hơn thế cờ kia ở chỗ nó còn nhiều quân bên mình hơn, nhiều quân giá trị cao hơn cũng như có bắt được nhiều quân và quân giá trị cao của đối phương hơn không.
Cách làm này đã bỏ qua mất những nghệ thuật, chiến lược chơi cờ (mà đó là những điểm để đánh giá một người là giỏi cờ hay không). Các quân cờ được triển khai không theo một chiến lược chung nào hết (vô định). Nó còn tạo cảm giác như cờ "vồ", nghĩa là chỉ nhằm nhằm sơ hở của đối phương là "ăn" ngay mà không cần biết đến hậu quả (điều này không hẳn đúng, lí do sẽ trình bầy dưới). Tuy nhiên phương pháp tính điểm này có những ưu điểm sau:

* Là cách tính điểm cơ bản nhất, đóng vai trò chủ đạo trong điểm của một thế cờ. Nó là cơ sở của đa số hàm đánh giá. Ta cũng có thể nhận thấy trong phần lớn thời gian diễn ra trận đấu, hai bên đều tìm cách tiêu diệt quân của nhau. Các phương án, chiến lược thường chỉ được tính như những điểm cộng thêm vào và đóng góp một tỷ lệ nhỏ trong tổng số điểm của một thế cờ. Việc chỉ nhằm "vồ" quân của đối phương nhưng sau khi suy nghĩ sâu nhiều nước cũng đã trở thành "cao cờ" rồi đấy. Nói cho cùng, mục đích chính của chúng ta cũng là "vồ" bằng được quân có giá trị cao nhất - Tướng đối phương.
* Là cách tính đơn giản nhất và nhanh nhất. Do tính nhanh, ta có thể tăng thêm độ sâu tìm kiếm. Việc tăng thêm độ sâu lại giúp máy có cái nhìn xa hơn, "cao cờ" hơn và nhiều khi khắc phục được nhược điểm của cách tính đơn giản.

Điểm các quân cờ được đánh giá theo kinh nghiệm và cho biết sự tương quan giữa các quân cờ. Sau đây là điểm từng quân mà mọi người thường chấp nhận:


Quân cờ Kí hiệu Điểm
Tốt-------PAWN-----1 (2 nếu đã qua sông)
Sĩ--------BISHOP----2
Tượng---ELEPHANT--2
Mã-------KNIGHT----4
Pháo-----CANNON---4.5
Xe--------ROOK-----9

Bạn cũng có thể theo bất kì thang điểm nào khác tuỳ theo hiểu biết và sở thích của mình. Ví dụ như trong làng cờ Việt nam thường cho điểm các quân hơi khác (xem bài đọc dưới): Tốt - 1 (2 nếu đã qua sông), Sĩ - 2, Tượng - 2.5, Mã - 4.5, Pháo - 5, Xe - 10.
Trong chương trình cờ của chúng ta, điểm cụ thể của từng quân cờ là các số nguyên 10, 20, 20, 40, 45 và 90. Ta dùng một mảng piecevalue để lưu điểm từng quân cờ. Cho điểm như vậy không những vẫn giữ nguyên được tương quan và tránh dùng số thực (tính chậm) mà ta còn có một khoảng cách hợp lí giữa các điểm để sau này dễ dàng thêm những điểm bổ xung "thưởng" hoặc "phạt", tức là những điểm căn cứ vào những yếu tố khác (ví dụ cùng là Pháo nhưng lúc chỉ được 40 điểm do ở vị trí "bí", lúc khác lại có thể đến 85 do ở vị trí Pháo trống và đang đe doạ Pháo lồng).
Trong bàn cờ, quân Tướng là quân quan trọng nhất, dù mất mọi quân hoặc đạt được thế cờ nào đi nữa đều không được mất Tướng vì nó dẫn đến thua cờ. Do đó, Tướng thường được cho một điểm rất cao, cách biệt nhiều lần so với các quân khác, đảm bảo điểm tổng của các quân còn lại cùng đủ mọi loại "thưởng", "thêm" đều không bằng được Tướng. Trong chương trình, ta cho nó 1000 điểm.
Hàm lượng giá thật đơn giản như sau (chú ý là ta chưa tăng điểm cho Tốt đã qua sông):
public class int Eval() {
int piecevalue[7]={10,20,20,40,45,90,1000};
int s = 0;
for (int i=1;i< BOARD_SIZE ; i++ ){
if (color[i] == side) s = s + piecevalue[piece[i]]
else if (color[i] == xside) s = s - piecevalue[piece[i]];
}
return s;
}

Vấn đề cải tiến hàm lượng giá sẽ được bàn riêng trong một chương phần sau.

// Đây là bài lược hoá của thầy Phạm Hồng Nguyên ! Tui xin đính chính một vài chỗ và mạo muội chuyển sang Java ! Làm được chừng nào sẽ Up lên chừng đó !
Đây là bài tui lấy từ nguồn: Lập trình Cờ Tướng - Những vấn đề cơ bản - K49C.NET
copy nội dung qua luôn để các bạn đọc cho tiện

[haithan]

Xin lỗi cho mình chen ngang dòng Topic Special này : cái này rất rất hay ...thể hiện tâm huyết những con người có chất xám đưa vào phục vụ trò chơi logic nó là trí tuệ nhân tạo đó các bạn ạ . Mình ưa nó nhất .... đúng là thanglongkydao