Trí tuệ nhân tạo trong đánh cờ (P.1)

Trí tuệ nhân tạo trong các trò chơi đánh cờ ko phải là cái gì quá cao siêu và hàn lâm, chỉ cần có kiến thức về cây, bạn hoàn toàn có thể lĩnh hội cách thức đưa ra chiến lược đánh cờ cho máy tính. Trong bài viết này tôi sẽ cố gắng trình bày một cách dễ hiểu nhất về vấn đề trên.

Đánh cờ, ví dụ, cờ vua, cờ tướng đều thuộc lý thuyết trò chơi 2 người. Có 2 khái niệm cơ bản song hành cùng nhau:

  • Trạng thái Thắng
  • Trạng thái Thua

Trước hết, thế nào là Trạng thái? Nói nôm na thì đó là thế cờ, mô tả vị trí các quân cờ trên bàn cờ. Chúng ta vẫn thường nghe những câu đại loại như: “thế cờ này có thể hóa giải được, thế cờ kia là thế cờ chết, …”. Những cách nói như thế có thể được thống nhất bằng Trạng thái Thắng và Trạng thái Thua. Một cách chung chung thì:

  • Trạng thái Thắng (TT Thắng) là TT mà nếu biết cách đánh, ta sẽ chiến thắng chung cuộc, bất kể đối phương đánh như thế nào.
  • TT Thua là TT mà cho dù nước đi kế tiếp như thế nào thì đều đặt đối phương vào TT Thắng.

Rõ ràng, định nghĩa 2 khái niệm này có tính chất đệ quy. Bạn đọc tinh ý sẽ nhận ra:

  • TT Thắng là TT mà tồn tại ít nhất 1 nước đi kế tiếp dẫn đến TT Thua.
  • TT Thua là TT mà tất cả các nước đi kế tiếp đều dẫn đến TT Thắng.

Câu hỏi đặt ra là: nếu chúng cứ định nghĩa dựa vào nhau mãi như vậy thì đâu là điểm dừng? Trong lập trình, điều này sẽ gây ra Tràn Stack. Điểm dừng ở đây chính là trạng thái “hết cờ”, tức mất Vua, hay mất Tướng. Vậy nên, để kiểm tra 1 TT là Thắng hay Thua, đầu tiên cần xem nó có còn quân Vua hay ko đã, nếu ko còn thì kết luận luôn là TT Thua. Đây cũng chính là TT kết thúc của trò chơi.

Quá trình đi đánh giá 1 TT A là Thắng hay Thua chính là quá trình duyệt theo chiều sâu trên 1 cây gốc A, gọi là cây trò chơi, mỗi nút của cây là 1 TT. Lá của cây chính là TT kết thúc (hết cờ).

Giả sử, trong trường hợp lý tưởng, ta đã xây dựng xong cây trò chơi này với nút gốc là TT bắt đầu trò cờ Vua. Nghĩa là, với mọi TT có thể có của trò cờ Vua, ta đều đã biết nó là TT Thắng hay Thua. Tại 1 thời điểm nào đó, đến phiên máy đi, bàn cờ đang ở TT A, máy phải chọn 1 nước đi để đến TT B. Chiến lược của máy sẽ như sau:

  • Nếu A là TT Thắng: tùy vào mode người chơi chọn ban đầu mà có chiến lược phù hợp: nếu là Hard thì cho máy theo nước đi mà đến B là TT Thua (tức là làm bất lợi cho người chơi); nếu là Easy thì đến B là TT Thắng (nếu có B như vậy, còn ko thì cho đi giống như mode Hard); nếu là Medium thì random ngẫu nhiên.
  • Nếu A là TT Thua: tức B toàn là TT Thắng, thì dù ở mode nào ta cũng cho máy đi random.

Tuy nhiên, vấn đề lớn nhất của chúng ta là: để xây dựng được cây trò chơi đầy đủ như trên thì ko thể, do số lượng TT của bàn cờ vua quá khổng lồ! Ko có bộ nhớ nào lưu đủ và cũng ko có con chíp nào chạy đủ nhanh để tính toán xong hết. Hướng giải quyết là chỉ xét 1 bộ phận con của cây trò chơi mà thôi. Ví dụ, cây có 1000 tầng (level) phát sinh từ nút A thì ta chỉ xét đến tầng thứ 10-15 thôi. Việc chọn số tầng này cũng cần cân nhắc, tùy khả năng xử lý của thiết bị cũng như loại cờ. Thông thường trong cờ Vua, với PC bình thường, nên chọn là 10 tầng.

Cách tiếp cận này lại nảy ra vấn đề: khi duyệt đến tầng 10, mà TT này lại chưa phải là TT hết cờ, làm sao đây? Lúc này ta cần phải có 1 cách đánh giá tương đối thế cờ đó nhanh chóng. Cách phổ biến là gán cho mỗi quân cờ 1 điểm số, rồi đánh giá thông qua tổng điểm số mỗi bên, bên nào nhiều điểm hơn thì sẽ là TT Thắng và ngược lại.

Các chương trình đánh cờ hay thường có hàm lượng giá rất tốt và tinh vi, nhiều khi được lưu sẵn trong database những thế cờ kinh điển, và máy chỉ cần móc ra là có ngay kết quả đánh giá.

Oke, đến đây, nếu bạn đã hiểu tất cả những gì tôi nói, và thử cài đặt code, thì thấy rằng chương trình vẫn còn dở. Cùng 1 mode (Hard, Easy, Medium) nhưng lúc thì máy tỏ ra thông minh, lúc thì ngu đần. Nguyên nhân là vì chúng ta chưa chi tiết thêm nữa các TT Thắng, Thua: Thắng đậm hay Thắng sát nút, Thua đậm hay Thua sát nút? Để khắc phục, cần phải đặt cho mỗi TT 1 con số, dương là thắng, âm là thua. Càng dương là thắng càng đậm, càng âm là thua càng đậm.

Sẽ tiếp tục trong phần 2, với code C++ minh họa :)

Advertisements

3 thoughts on “Trí tuệ nhân tạo trong đánh cờ (P.1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s