TỰ VIẾT CHƯƠNG TRÌNH CỜ TƯỚNG Tác giả: Phạm Hồng Nguyên Mục lục Chương 1

________________________________________ Lời nói đầu (11/2002) Nhằm giúp các bạn yêu thích cờ Tướng máy tính có thêm tài liệu nghiên cứu, học tập, tôi xuất bản quyển sách này ở dạng miễn phí. So với phiên bản ban đầu (năm 1998) nó có một số sửa đổi và chỉnh lý, cắt bỏ phần dậy viết chương trình cờ Vua và các phụ lục (phụ lục chỉ là các chương trình mẫu). Một số phần của tài liệu đã được trích dẫn và đăng tải trên tạp chí PCWorld VN. Bạn có thể dùng (đọc, download, lưu trữ) tài liệu này cho mục đích sử dụng của cá nhân hoặc sao chép (copy) cho người khác nhưng không được phép: sửa đổi (bất cứ câu chữ, hình vẽ nào), kinh doanh (dưới bất cứ hình thức nào), đăng tải lại ở trang web khác (trích dẫn là được phép và phải tuân theo các qui định về trích dẫn), xuất bản lại ở bất cứ dạng nào. (Một số ngoại lệ có thể được xem xét riêng). Hi vọng, với các điều khoản dễ và "fair" này sẽ được các bạn tuân thủ nghiêm chỉnh. Một điều lưu ý nữa là tài liệu này được cung cấp ở dạng AS IT (có thế nào xin dùng thế ấy) và sẽ không được kèm thêm các bài giảng hay các trợ giúp. Tôi có cung cấp địa chỉ email, nhưng chủ yếu là để nhận những phản hồi có ích cho mọi người như những góp ý, phê bình - xin đừng lạm dụng nó. Những yêu cầu cá nhân như xin chương trình (bạn hãy tự download lấy hoặc xin bạn bè), xin giảng thêm về thuật toán hoặc giải thích riêng cho một chi tiết kỹ thuật nào đó nói chung sẽ không được đáp ứng. Bạn cần phải tự suy nghĩ, nhờ bạn bè, tìm kiếm câu trả lời có sẵn hoặc hỏi ở các diễn đàn, bạn bè. Mặc dù tôi cung cấp các chương trình mẫu và quyển sách này ở dạng miễn phí nhưng điều đó không có nghĩa là toàn bộ quĩ thời gian (vốn đã rất eo hẹp) và sức lực của tôi chỉ dành cho chúng - các bạn cần hiểu và thông cảm. Phạm Hồng Nguyên

TỰ VIẾT CHƯƠNG TRÌNH CỜ TƯỚNG Tác giả: Phạm Hồng Nguyên Mục lục Chương 1

________________________________________ Lời nói đầu (11/2002)

Nhằm giúp các bạn yêu thích cờ Tướng máy tính có thêm tài liệu nghiên cứu, học tập, tôi xuất bản quyển sách này ở dạng miễn phí. So với phiên bản ban đầu (năm 1998) nó có một số sửa đổi và chỉnh lý, cắt bỏ phần dậy viết chương trình cờ Vua và các phụ lục (phụ lục chỉ là các chương trình mẫu). Một số phần của tài liệu đã được trích dẫn và đăng tải trên tạp chí PCWorld VN. Bạn có thể dùng (đọc, download, lưu trữ) tài liệu này cho mục đích sử dụng của cá nhân hoặc sao chép (copy) cho người khác nhưng không được phép: sửa đổi (bất cứ câu chữ, hình vẽ nào), kinh doanh (dưới bất cứ hình thức nào), đăng tải lại ở trang web khác (trích dẫn là được phép và phải tuân theo các qui định về trích dẫn), xuất bản lại ở bất cứ dạng nào. (Một số ngoại lệ có thể được xem xét riêng). Hi vọng, với các điều khoản dễ và "fair" này sẽ được các bạn tuân thủ nghiêm chỉnh. Một điều lưu ý nữa là tài liệu này được cung cấp ở dạng AS IT (có thế nào xin dùng thế ấy) và sẽ không được kèm thêm các bài giảng hay các trợ giúp. Tôi có cung cấp địa chỉ email, nhưng chủ yếu là để nhận những phản hồi có ích cho mọi người như những góp ý, phê bình - xin đừng lạm dụng nó. Những yêu cầu cá nhân như xin chương trình (bạn hãy tự download lấy hoặc xin bạn bè), xin giảng thêm về thuật toán hoặc giải thích riêng cho một chi tiết kỹ thuật nào đó nói chung sẽ không được đáp ứng. Bạn cần phải tự suy nghĩ, nhờ bạn bè, tìm kiếm câu trả lời có sẵn hoặc hỏi ở các diễn đàn, bạn bè. Mặc dù tôi cung cấp các chương trình mẫu và quyển sách này ở dạng miễn phí nhưng điều đó không có nghĩa là toàn bộ quĩ thời gian (vốn đã rất eo hẹp) và sức lực của tôi chỉ dành cho chúng - các bạn cần hiểu và thông cảm. Phạm Hồng Nguyên

Lời nói đầu (1998)

Cờ Tướng và cờ Vua là các môn thể thao trí tuệ hấp dẫn và phổ biến trên thế giới. Tuy nhiên việc tìm hiểu và viết chương trình máy tính có thể chơi được các loại cờ này vẫn là các thách thức lớn, nhất là đối với các bạn trẻ. Đã có khá nhiều chương trình nguồn của cờ Vua cho tự do (trên Internet). Hầu hết các chương trình này chỉ được cho sau khi các tác giả đã phát triển chúng trong nhiều năm ròng. Ví dụ, bộ GNU Chess cho sau khi phát triển hơn 20 năm, bộ CRAFTY sau khoảng 10 năm. Nhiều chương trình trong số đó chơi rất hay, đạt thứ hạng cao trong làng cờ máy (ví dụ GNU có hệ số ELO 2350-2400, CRAFTY 2500-2700). Nhưng cũng vì vậy các chương trình này đã trở nên rất phức tạp, gần như "không thể hiểu được" với các bạn mới nhập môn. Đa số các chương trình đó được viết bằng C và chạy trong môi trường Windows (hoặc được viết ở dạng "khả chuyển" tức là thêm nhiều chỉ dẫn dịch, các lệnh phức hợp để dịch ra được nhiều môi trường) cũng làm đau đầu các bạn Việt Nam vốn quen thuộc hơn với Pascal và DOS. Cờ Vua là loại cờ ít phổ biến hơn ở Việt Nam so với cờ Tướng cũng là một trở ngại quan trọng với nhiều bạn. Ngược lại với cờ Vua, ta hầu như không thể tìm được chương trình mẫu ở dạng nguồn và tài liệu hướng dẫn tìm hiểu và viết chương trình cờ Tướng. Điều này cũng dễ hiểu, trung tâm cờ Tướng là Trung Quốc và châu Á mới phát triển rộng rãi tin học chưa lâu. Có lẽ nhiều chương trình cờ Tướng nổi tiếng sau này đang được phát triển đâu đó bởi các bạn còn rất trẻ - mà rất có thể là bạn. Tôi biết có nhiều bạn đã từng mong muốn và từng thử viết một số chương trình chơi cờ nhưng thường nhanh chóng bỏ cuộc vì cho rằng chúng quá khó. Thật ra, viết một chương trình chơi cờ không quá khó. Chỉ một vài thủ tục và hàm là hơi rắc rối bạn cần nghiên cứu kĩ mới làm tốt được. Cái khó đối với nhiều bạn là thiếu các kiến thức cơ bản và vài kĩ thuật để viết một chương trình chơi cờ. Nhằm giúp các bạn vượt qua các trở ngại bước đầu, tôi đã biên soạn tập sách này. Trọng tâm của sách là hướng dẫn bạn viết chương trình chơi cờ Tướng và áp dụng sang cờ Vua. Sách cố gắng trình bầy đầy đủ về các kiến thức tổng quan cũng như các chi tiết cùng chương trình mẫu để giúp bạn có được những hiểu biết cơ bản về chương trình cờ, có thể tự tiếp tục phát triển được các chương trình có đẳng cấp cao. Rất nhiều kĩ thuật, ý tưởng cải tiến chương trình được sách đưa ra dưới dạng gợi ý phát triển, nhờ thế các bạn không phải học một cách thụ động, gò bó và sẽ nhanh chóng làm chủ chương trình, làm chủ kĩ thuật rồi tiến tới tự do hoàn chỉnh theo ý mình. Các chương trình mẫu viết bằng Pascal và chạy dưới môi trường DOS. Chúng có cấu trúc khá súc tích và đơn giản. Chương trình đầu tiên chỉ khoảng 460 dòng lệnh nhưng hoàn chỉnh và chơi tốt. Nó sẽ được cải tiến dần dần trong những chương tiếp theo để trở thành một chương trình mẫu tốt. Để viết được các chương trình cờ ngày càng hay hơn, bạn cũng cần tự mình nâng cao hiểu biết về cờ. Sách cũng trích đoạn nhiều tài liệu và đưa vào các mục "Tham khảo kiến thức cờ". Các tài liệu này được trích dẫn có chọn lọc và phù hợp với các phần đang trình bầy. Để giúp các bạn thích ngôn ngữ C hơn, toàn bộ các chương trình nguồn tương đương viết bằng C cũng được cho kèm trong các phụ lục. Cũng để giúp các bạn quan tâm đến cờ Vua, một chương cuối và phụ lục sẽ hướng dẫn bạn và đưa ra một chương trình mẫu hoàn chỉnh. Để cổ vũ phong trào luyện tập môn thể thao này và viết chương trình cho nó, chúng tôi xin trân trọng mời các bạn chuẩn bị và tham gia Giải cờ Tướng máy Vi tính, dự định tổ chức vào cuối năm 1999, do trường Đại học Quốc gia Hà Nội phối hợp với tạp chí Thế giới Vi tính (PCWorld Việt Nam) tổ chức. Sách này cũng được coi là một trong những tài liệu chuẩn bị chính thức cho giải. Việc cải tiến, phát triển chương trình làm cho nó hay hơn, "cao thủ" hơn là một thách thức thật sự nhưng cũng vô cùng hấp dẫn. Đường đi còn dài và rộng mở đối với tất cả chúng ta. Với chiến thắng của Deep Blue, con người đã thôi băn khoăn đến khi nào máy tính có thể đánh bại người chơi cờ Vua giỏi nhất thế giới. Thế nhưng với nỗi băn khoăn khi nào máy tính hạ được người chơi cờ Tướng giỏi nhất thế giới (một việc dĩ nhiên sẽ xẩy ra) thì có lẽ phải chờ chương trình của bạn. Tôi rất hoan nghênh mọi phê bình, góp ý cho sách cũng như các chương trình cờ làm cho chúng ngày càng hoàn thiện hơn (các góp ý của các bạn sẽ được tập hợp biên soạn và phổ biến đến các bạn khác). Nếu các bạn cần liên hệ, góp ý xin hãy viết thư cho tôi theo các địa chỉ sau: Địa chỉ thư: Phạm Hồng Nguyên (Giảng viên) Khoa Công nghệ, trường Đại học Quốc gia Hà Nội 334 Đường Nguyễn Trãi, quận Thanh Xuân, Hà Nội Email: [email protected]

Nếu truy nhập được Internet, mời các bạn ghé thăm trang chủ của tôi với địa chỉ dưới đây. Bạn sẽ tìm được ở đó các chương trình mẫu, các tài liệu liên quan đến sách (cùng nhiều thứ khác). http://www.Geocities.com/phhnguyen (địa chỉ cũ) http://www.nchess.com (địa chỉ mới) Nhân đây, tôi xin bầy tỏ lòng biết ơn sâu sắc đối với vợ tôi đã tạo mọi điều kiện cho tôi trong mọi việc cũng như viết cuốn sách này. Tôi cũng xin cảm ơn các đồng nghiệp trong khoa Công nghệ thông tin, các em Nguyễn Lê Minh, Nguyễn Văn Vinh, Trương Xuân Nam đã giúp đỡ nhiều trong quá trình viết sách. Cảm ơn em Lê Linh Phong đã đọc và giúp tôi hiệu chỉnh lại toàn bộ bản thảo và các chương trình mẫu. Hà nội, 1998, Phạm Hồng Nguyên

(Tiếp)

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 = b2. Cứ như vậy ở độ sâu d sẽ có bd 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 16100 hay xấp xỉ 10120 - 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ỡ 1010 (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). 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à 404 = 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 405 = 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.