A. Lý thuyết trò chơi trong lập trình:
Có lẽ đối với các bạn đã học qua lập trình thi đấu nói riêng và thuật toán nói chung, lý thuyết trò chơi là một khái niệm không quá xa lạ.
Cùng xét một bài toán kinh điển sau.
Bài toán 1:
Tóm tắt: Hai bạn A và B cùng chơi một trò chơi với N viên bi trong một chiếc hộp. Ở mỗi lượt, người chơi phải lấy 1, 2, hoặc 3 viên ra khỏi chiếc hộp. Biết rằng A và B sẽ luôn chơi một cách tối ưu và A là người đi trước, hãy tìm ra người chiến thắng.Phân tích:
- Với N không chia hết cho 4, tức là N = r (mod 4) với r < 4, A có thể lấy r viên bi để số bi còn lại chia hết cho 4. Sau đó, với mỗi lượt B chọn 1/2/3 viên bi, A sẽ chọn tương ứng là 3/2/1 viên bi để tổng số bi lấy ra của 2 lượt luôn là 4 và do đó, số bi còn lại luôn chia hết cho 4. Vì 0 chia hết cho 4 nên chắc chắn số bi sẽ được lấy hết ở lượt của A nên A sẽ là người chiến thắng. Với N chia hết cho 4, B sẽ thực hiện chiến thuật tương tự để giành chiến thắng.
Như vậy, với bài toán này, chúng ta đã xét được với mọi trường hợp, ai sẽ là người chiến thắng và với chiến thuật như thế nào. Đây cũng là mục đích chính của các bài toán về lý thuyết trò chơi trong lập trình thi đấu, khi mà 2 hoặc nhiều người sẽ cùng chơi một trò chơi và ta cần tìm ra chiến thuật thắng của một người nào đó.
Tiếp theo, ta sẽ xét một trò chơi kinh điển khác.
Bài toán 2: Cờ vua
(Nguồn: chessable.com)
Tóm tắt: Trò chơi sẽ có 2 người chơi thuộc phe màu trắng hoặc màu đen, mỗi người sẽ điều khiển các quân cờ thuộc phe của mình trên bàn cờ vua 8 x 8, mỗi quân cờ sẽ có những cách đi khác nhau. Ví dụ, quân xe (bắt đầu tại 4 góc của bàn cờ, như ảnh) có thể di chuyển tự do theo hàng ngang hoặc dọc nếu không có vật cản. Người chơi sẽ chiến thắng nếu như tiêu diệt được quân vua của đối phương, và phe trắng sẽ được đi trước.Phân tích:
- Theo lý thuyết trò chơi, ta hoàn toàn có thể tìm ra chiến thuật thắng dành cho một trong 2 phe. Bởi vì có thể biết được tất cả các trạng thái của bàn cờ, và mỗi người đều thực hiện bước đi một cách lần lượt, ta có thể xây dựng một cây trò chơi (game tree, đọc thêm tại đây).
- Tuy nhiên, như chúng ta đều biết, hiện nay con người vẫn chưa thể tìm ra được chiến thuật tối ưu cho trò chơi cờ vua này, bởi vì số lượng trạng thái là rất lớn. Để dễ hình dung, ở một trạng thái nào đó, mỗi quân cờ có thể nằm ở 1 trong 64 ô, hoặc nằm ở ngoài (đã bị ăn mất), và chúng ta có 32 quân cờ, do đó số lượng trạng thái khác nhau trên cây trò chơi có thể lên đến tầm 3265≈10100. Xét trên một chiếc máy tính bình thường với tốc độ xử lý khoảng 108 phép tính / giây, thì ta sẽ cần đâu đó tầm 3 tỷ tỷ tỷ tỷ tỷ tỷ tỷ tỷ tỷ năm để duyệt qua hết tất cả các trạng thái. Vậy nên, con người chỉ có thể tìm cách áp dụng AI và các thuật toán Heuristic để cố gắng tìm ra những bước đi tốt nhất có thể.
Cuối cùng, ta sẽ xét một trò chơi khác, cũng thú vị không kém.
Bài toán 3: Kho báu đại dương
Bản đồ kho báu, trong đó S là khiên, D là vật cản, còn lại là số lượng vàng
Tóm tắt: Hai đội chơi sẽ thi đấu với 2 chiếc thuyền trên vùng biển hình chữ nhật M x N, mỗi ô sẽ có vàng, vật cản, hoặc khiên. Ở mỗi lượt chơi, cả 2 đội sẽ cùng đưa ra quyết định di chuyển đến một trong số các ô bên cạnh, và đội đạt được nhiều vàng hơn khi trò chơi kết thúc (sau một số lượt chơi, hoặc cả 2 đều bị đắm tàu) sẽ chiến thắng.(Nguồn: Đấu Trường AI – Cuộc thi học thuật Thách Thức 2023)
Phân tích:
- Về lý thuyết, do ở mỗi lượt chơi, cả 2 đội sẽ đưa ra quyết định cùng lúc và trạng thái trò chơi sẽ thay đổi dựa trên quyết định của cả 2 bên, ta sẽ không thể dự đoán chính xác và có chiến thuật đảm bảo chiến thắng trong trò chơi này. Do đó, các đội chơi chỉ có thể cố gắng tìm ra những chiến thuật đi tốt nhất có thể. Ví dụ, một trong những chiến thuật đơn giản là cố gắng đi đến những ô với số lượng vàng cao nhất.
Như vậy, ta đã có một cái nhìn sơ bộ về ứng dụng của lý thuyết trò chơi trong các bài toán lập trình mà ở đó, ta cần tìm ra người thắng cuộc trong một loại trò chơi nào đó. Tuy nhiên, mọi chuyện không đơn giản đến thế. Sẽ không có những môn học, những vị tiến sĩ, giáo sư dành nhiều năm trời nghiên cứu về lý thuyết trò chơi chỉ để chiến thắng một trò chơi.
Ta sẽ cùng xét đến nguồn gốc và ý nghĩa thật sự của lý thuyết trò chơi.
B. Nguồn gốc lý thuyết trò chơi
Dù đã tồn tại một số nghiên cứu trước đó, khái niệm “lý thuyết trò chơi” lần đầu tiên xuất hiện vào 1944, khi các nhà toán học John von Neumann và Oskar Morgenstern đã xuất bản cuốn sách Theory of Games and Economic Behavior (tạm dịch: Lý thuyết trò chơi và hành vi kinh tế). Cuốn sách này đã đưa ra các khái niệm cơ bản của lý thuyết trò chơi và các ứng dụng của nó trong kinh tế.
(Nguồn: amazon.com)
Từ đó, lý thuyết trò chơi đã phát triển nhanh chóng và được áp dụng rộng rãi trong các lĩnh vực khác nhau, từ kinh tế học, chính trị học đến khoa học xã hội và kỹ thuật. Các nhà nghiên cứu đã phát triển nhiều mô hình và công cụ để phân tích các tình huống tương tác phức tạp, từ các trò chơi đơn giản đến các tình huống tương tác đa phương tiện. Trong những năm 1950 và 1960, lý thuyết trò chơi đã được áp dụng rộng rãi trong lĩnh vực kinh tế học và tài chính. Nó đã giúp các nhà kinh tế phát triển các mô hình phân tích tài chính, đặc biệt là về các quyết định đầu tư và quản lý rủi ro. Lý thuyết trò chơi cũng đã được sử dụng để phân tích các chiến lược cạnh tranh trong các thị trường. Trong những năm 1970 và 1980, lý thuyết trò chơi đã được áp dụng rộng rãi trong các lĩnh vực khác nhau, từ chính trị học đến tâm lý học. Các nhà nghiên cứu đã phát triển nhiều mô hình mới và công cụ để phân tích các tình huống tương tác phức tạp hơn, từ các trò chơi đa phương tiện đến các tình huống tương tác trong mối quan hệ xã hội.
Như vậy, có thể thấy, lý thuyết trò chơi vốn không được tạo ra để giải quyết các trò chơi. Ta sẽ cùng xét một số ứng dụng của nó.
C. Một số ứng dụng của lý thuyết trò chơi
1/ Tiến thoái lưỡng nan:
Tóm tắt: Hai kẻ bị tình nghi là tội phạm bị cảnh sát bắt. Cảnh sát không có đủ chứng cớ để kết án họ, và đã cách ly họ. Cảnh sát gặp từng người một và làm cùng thoả thuận: nếu một người tố cáo mà người kia im lặng, người im lặng sẽ bị phạt 10 năm tù và người tố cáo sẽ được thả tự do. Nếu cả hai đều im lặng, cảnh sát chỉ phạt được mỗi tù nhân 2 năm tù vì một tội nhỏ khác. Nếu cả hai đều phản bội, tố cáo đối phương, mỗi người sẽ bị phạt 5 năm.Phân tích:
- Gọi 2 tù nhân là A và B, xét sự lựa chọn của tù nhân A (như ảnh):
- Nếu biết trước B chọn tố cáo, A sẽ chọn tố cáo vì sẽ nhận 5 năm tù thay vì 10 năm.
- Nếu biết trước B chọn im lặng, A cũng sẽ chọn tố cáo vì sẽ được tự do thay vì nhận 2 năm tù.
- Như vậy, nếu chỉ xét đơn phương 1 phía A hoặc B, lựa chọn tố cáo sẽ là lựa chọn tốt nhất. Tuy nhiên, do cả 2 đều hướng tới sự lựa chọn tốt nhất cho bản thân mình, kết quả là cả 2 sẽ nhận 5 năm tù giam. Trong khi đó, một trường hợp khác rõ ràng tốt hơn là cả 2 cùng giữ im lặng và chỉ nhận 2 năm tù giam. Tuy nhiên, vấn đề là cả 2 không thể liên lạc để thỏa thuận với nhau cũng như không thể biết được đối phương sẽ chọn phương án nào, nên việc lựa chọn im lặng và mong đối phương cũng hợp tác với mình là rất khó. Hơn nữa, kể cả khi có thể thỏa thuận với nhau, họ cũng chưa chắc sẽ tin đối phương sẽ không phản bội.
- Tuy nhiên, nếu xét tính huống này lặp lại nhiều lần, và cho họ thỏa thuận với nhau, họ có thể sẽ lựa chọn khác. Cụ thể, nếu một trong 2 người phản bội ở lựa chọn đầu tiên, người kia có thể “trừng phạt” bằng cách phản bội lại ở lựa chọn tiếp theo, và rõ ràng nếu cứ tiếp tục phản bội thì kết quả chung của cả 2 sẽ ngày càng tệ đi. Do đó, việc lặp lại nhiều lần sẽ cho phép cả 2 đều có cơ hội trừng phạt đối phương nếu không hợp tác, và do đó, kết quả rất có thể sẽ là sự hợp tác.
Trong thực tế, một trường hợp hoàn toàn giống như trên thường không xãy ra, tuy nhiên, những trường hợp tương tự trong những lĩnh vực khác lại xuất hiện khá thường xuyên.
2/ Kinh tế:
Lý thuyết trò chơi được sử dụng để phân tích các quyết định kinh tế của các công ty, chính phủ và các tổ chức khác. Nó có thể giúp các nhà quản lý đưa ra quyết định thông minh về giá cả, sản xuất, tiếp thị và phân phối.
Ví dụ: 2 công ty A và B cùng sản xuất một loại sản phẩm và muốn phân phối trên cùng một thị trường, một cách tương đối, sẽ có 3 trường hợp xảy ra:
- A và B đều cạnh tranh một cách quá quyết liệt, dẫn đến việc giảm giá sản phẩm quá thấp hoặc sản xuất quá nhiều để giành thị phần, họ có thể bị dẫn đến những tổn thất nặng nề.
- A hoặc B quyết tâm giành thị phân, bên còn lại không cạnh tranh, dẫn đến một công ty thì hoàn toàn chiếm được thị trường và thành công tuyệt đối, trong khi công ty còn lại sẽ phá sản vì không thể cạnh tranh được.
- A và B hợp tác với nhau, phân chia thị phần và cùng thỏa thuận về giá cả, họ sẽ vẫn đạt được lợi nhuận cao dù không hoàn toàn độc chiếm thị trường đó.
Như vậy, cả 2 công ty nên hợp tác với nhau để đạt được kết quả tốt nhất. Đây cũng là một tình huống gần giống với song đề tù nhân.
3/ Chính trị:
Tương tự, lý thuyết trò chơi cũng được sử dụng để phân tích các quyết định chính trị của các quốc gia và các nhà lãnh đạo. Nó có thể giúp các nhà nghiên cứu phân tích các chiến lược ngoại giao, chiến tranh và hòa bình. Ví dụ, lý thuyết trò chơi đã được sử dụng để phân tích các chiến lược của các quốc gia trong các cuộc xung đột vũ trang.
4/ Khoa học xã hội:
Lý thuyết trò chơi được sử dụng để phân tích các tình huống tương tác xã hội, chẳng hạn như các quyết định về việc đầu tư vào giáo dục, sức khỏe và an ninh. Nó cũng có thể được sử dụng để nghiên cứu các tình huống tương tác trong các cộng đồng nhỏ hoặc trong mối quan hệ gia đình.
5/ Pháp luật:
Lý thuyết trò chơi cũng được sử dụng để giải quyết các vấn đề liên quan đến pháp lý. Nó có thể được sử dụng để phân tích các tình huống tranh chấp giữa các bên và giúp đưa ra các quyết định tối ưu trong các vụ kiện.
6/ Khoa học máy tính:
Lý thuyết trò chơi được sử dụng để phát triển các thuật toán thông minh và hệ thống trí tuệ nhân tạo. Nó cũng được sử dụng để thiết kế các hệ thống phân phối thông minh và tối ưu hóa các mạng lưới giao thông.
Tạm kết
Tóm lại, mặc dù có tên gọi như vậy, nhưng lý thuyết trò chơi không phải chỉ để chơi, hoặc ít nhất, những “trò chơi” mà nó giải quyết cũng sẽ mang tầm vĩ mô hơn rất nhiều.
Nguồn tham khảo:
Aumann, Robert J (1987), The New Palgrave: A Dictionary of Economics
Poundstone, William (1992). Prisoner’s Dilemma: John von Neumann, Game Theory, and the Puzzle of the Bomb