Đồ án tốt nghiệp đại học lập trình động trong lý thuyết trò chơi

Đồ án tốt nghiệp: Ứng dụng lập trình động giải quyết bài toán trong lý thuyết trò chơi. Tìm hiểu thuật toán, phân tích kết quả và ứng dụng thực tế.

• Tác giả: Lê Thị Lâm Oanh
• Người hướng dẫn: TS. Phạm Hồng Phong
• Trường học: Trường Đại học Xây dựng Hà Nội
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Lập trình động trong lý thuyết trò chơi
• Loại tài liệu: Đồ án tốt nghiệp
• Năm xuất bản: 2024
• Địa điểm: Hà Nội

Tóm tắt

I. Hướng dẫn toàn diện về lập trình động trong lý thuyết trò chơi

Đồ án tốt nghiệp về lập trình động trong lý thuyết trò chơi là một chủ đề học thuật chuyên sâu, kết hợp hai lĩnh vực quan trọng của khoa học máy tính. Lập trình động, hay còn gọi là quy hoạch động, là một phương pháp tối ưu hóa mạnh mẽ được sử dụng để giải quyết các bài toán phức tạp bằng cách chia chúng thành các bài toán con đơn giản hơn. Nguyên tắc cốt lõi của kỹ thuật này là giải mỗi bài toán con chỉ một lần và lưu trữ kết quả của nó, thường trong một bảng hoặc mảng, để tránh việc tính toán lại. Phương pháp này đặc biệt hiệu quả đối với các vấn đề có hai đặc tính chính: cấu trúc con tối ưu (lời giải tối ưu của bài toán lớn có thể được xây dựng từ lời giải tối ưu của các bài toán con) và các bài toán con chồng chéo (cùng một bài toán con được sử dụng để giải quyết nhiều bài toán lớn khác nhau). Trong khi đó, lý thuyết trò chơi là một ngành toán học ứng dụng chuyên nghiên cứu về các tình huống chiến lược, nơi kết quả của một người tham gia phụ thuộc vào lựa chọn của những người khác. Nó cung cấp một khung phân tích để mô hình hóa xung đột và hợp tác giữa các cá nhân hoặc tổ chức thông minh và có lý trí. Sự kết hợp giữa hai lĩnh vực này tạo ra một công cụ cực kỳ hữu hiệu. Lập trình động cung cấp cơ chế tính toán để tìm ra chiến lược tối ưu trong các mô hình do lý thuyết trò chơi thiết lập. Bằng cách biểu diễn trò chơi dưới dạng các trạng thái trò chơi và các bước chuyển đổi giữa chúng, lập trình động cho phép xác định nước đi tốt nhất tại mỗi bước, dựa trên việc phân tích các kết quả tiềm năng trong tương lai. Điều này đặc biệt quan trọng trong các trò chơi có thông tin hoàn hảo, như cờ vua hoặc trò chơi Nim, nơi mỗi người chơi đều biết tất cả thông tin về trạng thái hiện tại của trò chơi.

1.1. Khái niệm cốt lõi của quy hoạch động và các nguyên tắc chính

Quy hoạch động (Dynamic Programming) là một kỹ thuật giải quyết vấn đề bằng cách phá vỡ nó thành các bài toán con nhỏ hơn. Điểm mấu chốt là các bài toán con này chồng chéo lên nhau. Thay vì giải quyết các bài toán con lặp đi lặp lại, quy hoạch động sẽ tính toán lời giải cho mỗi bài toán con một lần duy nhất và lưu kết quả vào một cấu trúc dữ liệu như mảng hoặc bảng băm. Khi gặp lại bài toán con đó, lời giải đã lưu sẽ được truy xuất thay vì tính toán lại. Kỹ thuật này dựa trên nguyên lý tối ưu của Bellman, phát biểu rằng một chính sách tối ưu có thuộc tính là dù trạng thái và quyết định ban đầu là gì, các quyết định còn lại phải tạo thành một chính sách tối ưu đối với trạng thái kết quả từ quyết định đầu tiên. Các đặc điểm chính của một bài toán có thể giải bằng quy hoạch động là cấu trúc con tối ưu và các bài toán con chồng chéo.

1.2. Lý thuyết trò chơi là gì và vai trò trong khoa học máy tính

Lý thuyết trò chơi là một lĩnh vực nghiên cứu sử dụng các mô hình toán học để phân tích sự tương tác chiến lược giữa những người ra quyết định hợp lý. Trong một "trò chơi", kết quả cho mỗi người tham gia phụ thuộc vào các hành động của tất cả mọi người. Trong khoa học máy tính, lý thuyết trò chơi có vai trò quan trọng trong trí tuệ nhân tạo, an ninh mạng, thuật toán và hệ thống mạng. Nó giúp thiết kế các tác tử thông minh có thể đưa ra quyết định tối ưu trong môi trường cạnh tranh hoặc hợp tác. Các khái niệm như Cân bằng Nash hay Định lý Minimax cung cấp nền tảng để dự đoán hành vi và tìm ra các chiến lược ổn định trong các hệ thống phức tạp, từ đó giải quyết các vấn đề liên quan đến phân bổ tài nguyên, định tuyến mạng, và đấu giá thuật toán.

II. Thách thức khi giải bài toán tối ưu trong lý thuyết trò chơi

Việc áp dụng lập trình động trong lý thuyết trò chơi đối mặt với nhiều thách thức đáng kể, đòi hỏi sự phân tích sâu sắc và các phương pháp tiếp cận hiệu quả. Thách thức lớn nhất đến từ sự phức tạp vốn có của việc tìm kiếm một chiến lược tối ưu. Trong hầu hết các trò chơi, một nước đi tốt không chỉ phụ thuộc vào trạng thái hiện tại mà còn phải tính đến tất cả các nước đi phản hồi có thể có của đối thủ. Điều này tạo ra một cây quyết định khổng lồ, và việc duyệt qua tất cả các nhánh để tìm ra con đường tối ưu thường không khả thi về mặt tính toán. Một ví dụ điển hình là việc xác định trạng thái trò chơi là thắng (Winning state) hay thua (Losing state). Một trạng thái được coi là thắng nếu tồn tại ít nhất một nước đi dẫn đến trạng thái thua của đối thủ. Ngược lại, một trạng thái là thua nếu mọi nước đi đều dẫn đến trạng thái thắng của đối thủ. Việc phân loại này đòi hỏi phải phân tích ngược từ các trạng thái kết thúc của trò chơi, một quá trình có thể rất phức tạp. Thêm vào đó, một thách thức cơ bản khác là vấn đề các bài toán con chồng chéo. Khi sử dụng phương pháp đệ quy thuần túy để phân tích cây trò chơi, nhiều trạng thái trò chơi giống nhau sẽ được đánh giá lặp đi lặp lại, dẫn đến sự lãng phí tài nguyên tính toán và thời gian thực thi tăng theo cấp số nhân. Ví dụ, trong bài toán tính chuỗi Fibonacci, việc tính F(n) bằng đệ quy sẽ gọi F(n-1) và F(n-2), và cả hai lời gọi này đều cần tính F(n-3), gây ra sự trùng lặp. Đây chính là lúc lập trình động phát huy vai trò của mình bằng cách lưu trữ kết quả của các bài toán con đã giải.

2.1. Vấn đề các bài toán con chồng chéo và tính toán dư thừa

Hiện tượng các bài toán con chồng chéo là một đặc điểm cốt lõi của nhiều bài toán tối ưu. Khi một bài toán lớn được chia thành các bài toán con, các bài toán con này không hoàn toàn độc lập mà thường gọi lại lẫn nhau. Một giải pháp đệ quy ngây thơ sẽ giải quyết cùng một bài toán con nhiều lần, dẫn đến độ phức tạp thời gian theo hàm mũ. Ví dụ, trong việc tìm đường đi ngắn nhất, đường đi đến một nút trung gian có thể là một phần của nhiều đường đi tổng thể khác nhau. Lập trình động giải quyết vấn đề này bằng cách sử dụng kỹ thuật ghi nhớ (memoization) hoặc lập bảng (tabulation) để đảm bảo rằng mỗi bài toán con chỉ được tính toán một lần, qua đó giảm đáng kể độ phức tạp.

2.2. Khó khăn khi xác định trạng thái trò chơi và chiến lược tối ưu

Việc xác định trạng thái trò chơi và xây dựng một chiến lược tối ưu là một trong những khía cạnh khó khăn nhất. Một trạng thái phải chứa đủ thông tin để mô tả tình hình hiện tại của trò chơi và cho phép đưa ra quyết định tiếp theo. Trong nhiều trò chơi, không gian trạng thái có thể rất lớn hoặc thậm chí vô hạn. Chiến lược tối ưu yêu cầu người chơi phải dự đoán được nước đi tốt nhất của đối thủ. Điều này dẫn đến các thuật toán như Minimax, nơi người chơi cố gắng tối đa hóa lợi ích tối thiểu của mình. Tuy nhiên, việc áp dụng Minimax trên toàn bộ cây trò chơi thường không thực tế, đòi hỏi các kỹ thuật cắt tỉa như Alpha-Beta hoặc các phương pháp heuristic để giảm không gian tìm kiếm.

III. Cách lập trình động giải quyết bài toán trong lý thuyết trò chơi

Phương pháp lập trình động trong lý thuyết trò chơi cung cấp một bộ công cụ hiệu quả để vượt qua các thách thức về tính toán dư thừa và tìm kiếm chiến lược. Hai kỹ thuật tiếp cận chính là Top-Down (từ trên xuống) với ghi nhớ và Bottom-Up (từ dưới lên) với lập bảng. Cả hai phương pháp đều nhằm mục đích giải quyết mỗi bài toán con một lần duy nhất, nhưng cách tiếp cận của chúng khác nhau về cấu trúc và luồng thực thi. Cách tiếp cận Top-Down, hay ghi nhớ (memoization), bắt đầu từ bài toán gốc và sử dụng đệ quy để chia nó thành các bài toán con nhỏ hơn. Điểm khác biệt so với đệ quy thông thường là nó sử dụng một bộ nhớ đệm (cache), chẳng hạn như một mảng hoặc bảng băm, để lưu trữ kết quả của các bài toán con đã được giải. Trước khi tính toán một bài toán con, thuật toán sẽ kiểm tra xem kết quả đã có trong cache hay chưa. Nếu có, nó sẽ trả về kết quả đã lưu; nếu không, nó sẽ tính toán, lưu kết quả vào cache, rồi trả về. Cách tiếp cận này thường trực quan và dễ triển khai hơn vì nó theo sát cấu trúc đệ quy của bài toán. Ngược lại, phương pháp Bottom-Up, hay lập bảng (tabulation), giải quyết bài toán theo hướng ngược lại. Nó bắt đầu bằng cách giải quyết các bài toán con nhỏ nhất, đơn giản nhất trước. Sau đó, nó sử dụng kết quả của những bài toán con này để xây dựng lời giải cho các bài toán con lớn hơn và phức tạp hơn một cách tuần tự. Quá trình này tiếp diễn cho đến khi giải được bài toán gốc. Phương pháp này thường được triển khai bằng các vòng lặp và sử dụng một bảng (ví dụ: mảng DP) để lưu trữ các kết quả trung gian. Lập bảng thường hiệu quả hơn về mặt không gian bộ nhớ vì nó không yêu cầu ngăn xếp đệ quy, và trong một số trường hợp, nó có thể nhanh hơn do chi phí truy cập mảng thấp hơn.

3.1. Kỹ thuật Top Down Ghi nhớ và ứng dụng thực tiễn

Kỹ thuật ghi nhớ (memoization) là một chiến lược tối ưu hóa được sử dụng để tăng tốc các chương trình máy tính bằng cách lưu trữ kết quả của các lệnh gọi hàm tốn kém và trả về kết quả đã được lưu trong bộ nhớ cache khi cùng một đầu vào xuất hiện trở lại. Trong bối cảnh lập trình động, nó được áp dụng cho các giải pháp đệ quy. Cách tiếp cận này rất tự nhiên khi cấu trúc của bài toán có bản chất đệ quy. Ưu điểm của nó là chỉ tính toán các bài toán con thực sự cần thiết để giải quyết vấn đề ban đầu. Tuy nhiên, nó có thể phát sinh chi phí cho các lệnh gọi đệ quy và có nguy cơ tràn ngăn xếp nếu độ sâu đệ quy quá lớn.

3.2. Kỹ thuật Bottom Up Lập bảng để tăng hiệu quả tính toán

Kỹ thuật lập bảng (tabulation) là một phương pháp tiếp cận từ dưới lên. Nó giải quyết vấn đề bằng cách điền vào một bảng, thường là một mảng đa chiều, theo một thứ tự cụ thể. Nó bắt đầu với các trường hợp cơ sở (các bài toán con nhỏ nhất) và tính toán dần các giá trị cho các bài toán con lớn hơn cho đến khi đạt được lời giải cho bài toán cuối cùng. Cách tiếp cận này tránh được đệ quy, do đó loại bỏ được chi phí liên quan đến các lệnh gọi hàm và nguy cơ tràn ngăn xếp. Nó thường hiệu quả hơn về hiệu suất, đặc biệt là khi tất cả các bài toán con đều cần được giải quyết. Đây là phương pháp phổ biến trong các cuộc thi lập trình cạnh tranh.

IV. Cách áp dụng các định lý Game Theory vào lập trình động

Việc tích hợp các định lý nền tảng của lý thuyết trò chơi vào lập trình động tạo ra một khuôn khổ vững chắc để phân tích và giải quyết các trò chơi chiến lược. Các định lý như Sprague-Grundy, Minimax và khái niệm Cân bằng Nash cung cấp các nguyên tắc toán học, trong khi lập trình động cung cấp công cụ tính toán để thực thi các nguyên tắc đó. Định lý Sprague-Grundy là một kết quả cơ bản trong lý thuyết trò chơi tổ hợp, đặc biệt là cho các trò chơi công bằng (impartial games), nơi các nước đi hợp lệ chỉ phụ thuộc vào trạng thái của trò chơi chứ không phụ thuộc vào người chơi nào đang thực hiện nước đi. Định lý này phát biểu rằng mọi trò chơi công bằng đều tương đương với một đống trong trò chơi Nim. Giá trị tương đương này được gọi là số Grundy (hoặc nim-value). Số Grundy của một trạng thái trò chơi được định nghĩa là giá trị loại trừ nhỏ nhất (MEX - Minimum Excluded value) của tập hợp các số Grundy của các trạng thái có thể đạt được từ trạng thái hiện tại. Lập trình động là phương pháp lý tưởng để tính toán các số Grundy này, thường là theo cách tiếp cận Bottom-Up, bắt đầu từ các trạng thái kết thúc (có số Grundy bằng 0) và tính toán ngược lại. Đối với các trò chơi hai người có tổng điểm bằng 0, Định lý Minimax, do John von Neumann phát triển, là trọng tâm. Nó mô tả chiến lược tối ưu trong đó người chơi cố gắng tối đa hóa lợi ích tối thiểu của mình (maximin) hoặc tối thiểu hóa tổn thất tối đa của đối thủ (minimax). Lập trình động được sử dụng để triển khai thuật toán Minimax bằng cách xây dựng một bảng lưu trữ giá trị của từng trạng thái trò chơi, tránh việc phải tính toán lại.

4.1. Định lý Sprague Grundy và cách tính số Grundy hiệu quả

Định lý Sprague-Grundy cho phép phân tích các trò chơi phức tạp bằng cách quy chúng về trò chơi Nim. Trọng tâm của nó là số Grundy g(s) của một trạng thái s, được tính bằng công thức g(s) = MEX({g(s') | s' là trạng thái có thể đến từ s}). Một trạng thái là trạng thái thua (P-position) nếu và chỉ nếu số Grundy của nó bằng 0. Để tính toán hiệu quả, ta có thể sử dụng lập trình động. Bắt đầu từ các trạng thái cuối cùng (terminal positions) có g-value bằng 0, ta xây dựng dần giá trị cho các trạng thái khác dựa trên các trạng thái đã được tính toán. Đối với một trò chơi tổng hợp gồm nhiều trò chơi con, số Grundy của trạng thái tổng hợp là tổng Nim (phép XOR) của các số Grundy của từng trò chơi con.

4.2. Tìm kiếm chiến lược tối ưu với Định lý Minimax và Cân bằng Nash

Định lý Minimax là nền tảng cho việc ra quyết định trong các trò chơi đối kháng có tổng bằng không. Nó giúp xác định giá trị của trò chơi và chiến lược tối ưu cho mỗi người chơi. Thuật toán Minimax có thể được triển khai bằng đệ quy và tối ưu hóa bằng lập trình động (ghi nhớ) để lưu trữ giá trị của các trạng thái đã được đánh giá. Cân bằng Nash, được đặt theo tên nhà toán học John Nash, là một trạng thái trong đó không người chơi nào có thể hưởng lợi bằng cách đơn phương thay đổi chiến lược của mình, trong khi các người chơi khác giữ nguyên chiến lược. Mặc dù lập trình động không trực tiếp tìm Cân bằng Nash trong mọi trường hợp, nó có thể được sử dụng để tính toán các hàm hữu dụng (payoff functions) trong các trò chơi lặp lại, từ đó giúp xác định các điểm cân bằng.

V. Phân tích đồ án Ứng dụng lập trình động giải trò chơi n đồng xu

Một ứng dụng thực tiễn và kinh điển của lập trình động trong lý thuyết trò chơi là giải quyết trò chơi n đồng xu. Bài toán này mô tả một kịch bản cạnh tranh giữa hai người chơi, nơi mỗi người cố gắng tối đa hóa tổng giá trị các đồng xu mà họ thu thập được. Đây là một trò chơi có thông tin hoàn hảo, tuần tự, và có tổng bằng không, làm cho nó trở thành một ví dụ lý tưởng để áp dụng các nguyên tắc của cả hai lĩnh vực. Bối cảnh của trò chơi như sau: có một hàng gồm n đồng xu, mỗi đồng xu có một giá trị nhất định. Hai người chơi lần lượt thực hiện nước đi. Trong mỗi lượt, người chơi có thể chọn một đồng xu từ một trong hai đầu của hàng. Trò chơi kết thúc khi tất cả các đồng xu đã được lấy. Mục tiêu của mỗi người chơi là kết thúc với tổng giá trị cao hơn đối thủ. Để giải quyết bài toán này bằng lập trình động, bước đầu tiên là định nghĩa trạng thái của bài toán. Một trạng thái có thể được xác định bởi chỉ số bắt đầu i và chỉ số kết thúc j của đoạn đồng xu còn lại. Hàm mục tiêu là dp[i][j], đại diện cho giá trị tối đa mà người chơi hiện tại có thể thu được từ đoạn đồng xu từ i đến j. Việc xây dựng công thức truy hồi dựa trên nguyên tắc của Định lý Minimax: người chơi hiện tại sẽ đưa ra lựa chọn (lấy đồng xu i hoặc j) để tối đa hóa lợi ích của mình, trong khi giả định rằng đối thủ cũng sẽ chơi tối ưu để tối thiểu hóa lợi ích của người chơi hiện tại. Công thức này cho thấy sự đan xen giữa quyết định của hai người chơi, một đặc trưng cơ bản của lý thuyết trò chơi.

5.1. Mô hình hóa bài toán n đồng xu theo nguyên tắc lý thuyết trò chơi

Việc mô hình hóa trò chơi n đồng xu bắt đầu bằng việc xác định các thành phần của một trò chơi chiến lược: người chơi, các hành động có thể, và hàm hữu dụng (payoff). Có hai người chơi, và tại mỗi trạng thái (được xác định bởi đoạn xu [i, j]), người chơi có hai hành động: chọn coins[i] hoặc coins[j]. Vì đây là trò chơi hai người có tổng điểm bằng 0 (lợi ích của người này là thiệt hại của người kia), mục tiêu của người chơi 1 là tối đa hóa (Điểm của người chơi 1) - (Điểm của người chơi 2). Việc áp dụng lập trình động cho phép tính toán giá trị tối ưu này cho mọi trạng thái con có thể xảy ra, từ đó tìm ra nước đi tốt nhất ở trạng thái ban đầu.

5.2. Xây dựng ma trận DP và tìm lời giải cho chiến lược tối ưu

Để tìm lời giải, ta xây dựng một ma trận dp[n][n]. dp[i][j] lưu giá trị tối đa người chơi có thể nhận được từ đoạn [i, j]. Quá trình tính toán diễn ra theo cách Bottom-Up, bắt đầu với các đoạn có độ dài 1, sau đó là 2, và cứ thế đến n. Với một đoạn [i, j], người chơi có hai lựa chọn: 1. Lấy đồng xu i: Người chơi nhận coins[i]. Đối thủ sẽ chơi tối ưu trên đoạn [i+1, j], để lại cho người chơi hiện tại giá trị tối thiểu trong các lựa chọn tiếp theo. 2. Lấy đồng xu j: Tương tự, người chơi nhận coins[j] và đối mặt với lựa chọn của đối thủ trên đoạn [i, j-1]. dp[i][j] sẽ là giá trị lớn hơn trong hai kịch bản này. Kết quả cuối cùng là dp[0][n-1].

5.3. So sánh hiệu quả giữa giải pháp lập trình động và đệ quy

Một giải pháp đệ quy thuần túy cho trò chơi n đồng xu sẽ có độ phức tạp thời gian theo hàm mũ, vì nó tính toán lại giá trị cho cùng một đoạn [i, j] nhiều lần. Ngược lại, giải pháp lập trình động, dù là Top-Down với ghi nhớ hay Bottom-Up với lập bảng, đều giải quyết vấn đề các bài toán con chồng chéo. Bằng cách lưu trữ kết quả của các đoạn con vào ma trận DP, mỗi trạng thái (i, j) chỉ được tính một lần. Điều này làm giảm độ phức tạp thời gian xuống còn O(n²), với n là số đồng xu. Độ phức tạp không gian cũng là O(n²) để lưu trữ bảng DP. Rõ ràng, lập trình động mang lại hiệu quả vượt trội cho bài toán này.

VI. Tương lai của lập trình động trong lý thuyết trò chơi và AI

Sự giao thoa giữa lập trình động và lý thuyết trò chơi không chỉ là một chủ đề học thuật hấp dẫn mà còn mở ra những hướng đi đột phá cho tương lai, đặc biệt trong lĩnh vực Trí tuệ Nhân tạo (AI). Khi các hệ thống AI ngày càng phức tạp và được yêu cầu tương tác trong các môi trường đa tác tử (multi-agent environments), khả năng ra quyết định chiến lược trở nên cực kỳ quan trọng. Lập trình động cung cấp một nền tảng thuật toán vững chắc để tìm kiếm các chiến lược tối ưu trong các mô hình trò chơi, từ các trò chơi đối kháng đơn giản đến các kịch bản kinh tế và xã hội phức tạp. Trong tương lai, các thuật toán lập trình động sẽ được cải tiến để xử lý các không gian trạng thái lớn hơn và phức tạp hơn. Các kỹ thuật như lập trình động xấp xỉ (Approximate Dynamic Programming) và học tăng cường (Reinforcement Learning), vốn có nguồn gốc sâu sắc từ các nguyên lý của lập trình động, đang trở thành trọng tâm. Học tăng cường, cụ thể là các thuật toán như Q-learning hay Deep Q-Networks (DQN), có thể được xem như một dạng lập trình động không cần mô hình (model-free), cho phép các tác tử AI học chiến lược tối ưu thông qua thử và sai mà không cần biết trước toàn bộ quy tắc của môi trường. Sự kết hợp này đặc biệt mạnh mẽ trong việc giải quyết các trò chơi có thông tin không hoàn hảo hoặc có yếu tố ngẫu nhiên. Các ứng dụng tiềm năng của lập trình động trong lý thuyết trò chơi rất đa dạng, từ việc phát triển các AI chơi game siêu phàm (như AlphaGo) đến tối ưu hóa chuỗi cung ứng, quản lý giao thông đô thị, và thiết kế các cơ chế đấu giá tự động.

6.1. Tổng kết giá trị và đóng góp của đề tài nghiên cứu

Đề tài nghiên cứu về lập trình động trong lý thuyết trò chơi đã chứng minh được sự liên kết chặt chẽ và sức mạnh tổng hợp của hai lĩnh vực này. Nó cung cấp một cái nhìn sâu sắc về cách các bài toán ra quyết định chiến lược có thể được mô hình hóa toán học và giải quyết một cách hiệu quả bằng các thuật toán máy tính. Đóng góp chính của đề tài là hệ thống hóa kiến thức, từ các khái niệm cơ bản như quy hoạch động và trạng thái trò chơi đến các định lý nâng cao như Sprague-Grundy và Minimax. Thông qua việc phân tích và triển khai giải pháp cho các bài toán cụ thể như trò chơi n đồng xu, đề tài đã làm rõ cách áp dụng lý thuyết vào thực tiễn, đồng thời so sánh và đánh giá hiệu quả của các phương pháp tiếp cận khác nhau.

6.2. Hướng phát triển và các ứng dụng tiềm năng trong tương lai

Hướng phát triển trong tương lai sẽ tập trung vào việc mở rộng khả năng áp dụng của lập trình động cho các loại trò chơi phức tạp hơn, bao gồm các trò chơi có nhiều người chơi, thông tin không hoàn hảo, và các yếu tố ngẫu nhiên. Lĩnh vực học tăng cường sâu (Deep Reinforcement Learning) hứa hẹn sẽ là một hướng đi đột phá, kết hợp sức mạnh của mạng nơ-ron sâu để xấp xỉ các hàm giá trị trong không gian trạng thái khổng lồ. Các ứng dụng thực tiễn bao gồm việc xây dựng các hệ thống tự trị thông minh hơn trong robotics, xe tự lái, các hệ thống đàm phán và giao dịch tài chính tự động, nơi các tác tử AI cần phải dự đoán và phản ứng lại hành vi chiến lược của các tác tử khác trong môi trường.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: TỔNG QUAN VỀ LẬP TRÌNH ĐỘNG 1.1 Giớithiệuchung 1.1 Kháiniệmvềquyhoạchđộng Lậptrìnhđộng(DynamicProgramming)làmộtphươngphápđượcsửdụngtrong toánhọcvàkhoahọcmáytínhđểgiảiquyếtcácvấnđềphứctạpbằngcáchchia chúngthànhnhữngbàitoánconđơngiảnhơn.Bằngcáchgiảimỗibàitoánconchỉ mộtlầnvàlưutrữkếtquả,nótránhđượccácphéptínhdưthừa,dẫnđếngiảipháp hiệuquảhơnchonhiềubàitoán.2 Lậptrìnhđộnghoạtđộngnhưthếnào? Xácđịnhcácvấnđềphụ:chiavấnđềchínhthànhcácvấnđềphụnhỏhơn,độc lập. Lưutrữgiảipháp:giảiquyếttừngbàitoánconvàlưutrữgiảiphpastrongmột bảnghoặcmảng. Xâydựnggiảipháp:sửdụngcácgiảiphápđượclưutrữđểxâydựnggiảiphápcho vấnđềchính. Tránhdưthừa:bằngcáchlưutrữlờigiải,quyhoạchđộngđảmbảorằngmỗibài toánconchỉđượcgiảimộtlần,giảmthờigiantínhtoán.

Ví dụ về lập trình động:XétbàitoántìmdãyFibonacci Hình1:DãyFibonacci ChuỗiFibonaccisửdụnglậptrìnhđộng:  Cácbàitoáncon:F(0),F(1),F(2),F(3),….  Giảipháplưutrữ:TạomộtbảngđểlưutrữcácgiátrịcủaF(n)khichúng đượctínhtoán.  Xâydựnglờigiải:ĐốivớiF(n),hãytracứuF(n-1)vàF(n-2)trongbảngvà cộngchúnglại.  Tránhdưthừa:Bảngđảmbảorằngmỗibàitoáncon(vídụF(2))chỉđược giảimộtlần.

Bằngcáchsửdụnglậptrìnhđộng,chúngtacóthểtínhtoándãyFibonaccimột cáchhiệuquảmàkhôngcầnphảitínhtoánlạicácbàitoáncon.3 Khinàosửdụnglậptrìnhđộng Lậptrìnhđộnglàmộtkỹthuậttốiưuhóađượcsửdụngkhigiảiquyếtcácvấnđề baogồmđặcđiểmsau: 1.1 Cấutrúctốiưu: Cấutrúctốiưucónghĩalàchúngtakếthợpcáckếtquảtốiưucủacácbàitoán conđểđạtđượckếtquảtốiưucủabàitoánlớnhơn. Vídụ: Xétvấnđềtìmđườngdẫnchiphítốithiểutrongbiểuđồcótrọngsốtừnút nguồnđếnnútđích.Chúngtachiabàitoánnàythànhcácbàitoánconnhỏ hơn:  Tìmđườngđicóchiphítốithiểutừnútnguồnđếnmỗinúttrung gian.  Tìmđườngđicóchiphítốithiểutừmỗinúttrunggianđếnnútđích.2 Cácbàitoánconchồngchéo Cácbàitoáncongiốngnhauđượcgiảilặpđilặplạiởcácphầnkhácnhaucủa bàitoán. Vídụ:XétbàitoántínhdãyFibonacci.ĐểtínhsốFibonaccitạichỉsốn,chúng tacầntínhsốFibonaccitạichỉsốn-1vàn-2.Điềunàycónghĩalàbàitoáncon tínhsốFibonaccitạichỉsốn-1đượcsửdụnghailầntronglờigiảichobàitoán lớnhơnlàtínhsốFibonaccitạichỉsốn 1.4 Cácphươngpháplậptrìnhđộng Lậptrìnhđộngcóthểđạtđượcbằnghaicáchtiếpcận: 1.1 Cáchtiếpcậntừtrênxuống(Top-Down) Trongcáchtiếpcậntừtrênxuống,cònđược gọilàghinhớ(memoization), chúngtabắtđầuvớilờigiảicuốicùngvàchianóthànhcácbàitoánconnhỏ hơnmộtcáchđệquy.Đểtránhtínhtoándưthừa,chúngtôilưutrữkếtquả củacácbàitoánconđãgiảitrongbảngghinhớ.

Phântíchcáchtiếpcậntừtrênxuống:  Bắtđầuvớilờigiảicuốicùngvàchiathànhcácbàitoánconnhỏhơn.  Lưutrữlờigiảicủacácbàitoáncontrongmộtbảngđểtránhtínhtoán dưthừa.  Thíchhợpkhisốlượngbàitoánconlớnvànhiềubàitoánconđượcsử dụnglại.2 Cáchtiếpcậntừdướilên(Bottom-Up) Trongcáchtiếpcậntừdướilên,cònđượcgọilàlậpbảng( tabulation),chúng tabắtđầuvớicácbàitoánnhỏnhấtvàdầndầnxâydựngđếnlời giảicuối cùng.Chúngtalưutrữukếtquảcủacácbàitoánconđãgiảitrongmộtbảngđể tránhtínhtoándưthừa. Phântíchcáchtiếpcậntừdướilên:  Bắtđầuvớinhữngbàitoánnhỏnhấtvàdẫndầnxâydựnglờigiảicuối cùng.

 Điềnvàibảngcácgiảiphápchocácbàitoáncontheocáchtừdướilên.  Thíchhợpkhisốlượngbàitoánconnhỏvàlờigiảitốiưucóthểđược tínhtrựctiếptừlờigiảicủabàitoánconnhỏhơn.5 Ứngdụngcủalậptrìnhđộng Lậptrìnhđộngcónhiềuứngdụng,baogồm:  Tốiưuhóa:bàitoánbalo,đườngđingắnnhất,mảngcontốiđa.  Khoahọcmáytính:dãyconchungdàinhất,chỉnhsửakhoảngcách,khớp chuỗi.  Nghiêncứuhoạtđộng:quảnlýhàngtồnkho,lậpkếhoạch,phânbổnguồn lực.2 Đặcđiểmcủalậptrìnhđộng Lậptrìnhđộnglàmộttrongnhữngkỹthuậtmạnhmẽnhấtđểgiảiquyếtmộtloạivấn đềnhấtđịnh.

Cómộtcáchhayđểhìnhthànhcáchtiếpcậnvàquytrìnhtưduyrấtđơngiản,đồng thờiphầnmãhóacũngrấtdễdàng. Vềcơbản,đólàmộtlýtưởngđơngiản,saukhigiảiquyếtmộtvấnđềvớimộtđầu vàonhấtđịnh,lưujeetsquảlàmtàiliệuthamkhảođểsửdụngchotươnglai. Lờigiảicủacácbàitoánconđượclưutrữutrongmộtbảnghoặcmảng(ghinhớ)hoặc theocáchtừdướilên(lậpbảng)đểtránhtínhtoándưthừa. Lờigiảibàitoáncóthểđượcxâydựngtừlờigiảicủacácbàitoáncon.

Lậptrìnhđộngcóthểđượctriểnkhaibằngthuậttoánđệquy,trongđógiảiphápcho cácbàitoánconđượctìmthấyđệquyhoặcsửdụngthuậttoánlặp,giảiphápđược tìmthấybằngcáchgiảiquyếtcácbàitoáncontheomộtthứutựcụthể.3 Lậptrìnhđộngdựatrêncácnguyêntắc Đặctrungcấutrúccủalờigiảitốiưu,tứclàxâydựngmôhìnhtoánhọccủalờigiải. Xácđịnhđệquygiátrịcủagiảipháptốiưu. Sửdụngphươngpháptiếpcậntừdướilên,tínhtoángiátrịcủalờigiảitốiưucho từngbàitoánconcóthểxảyra. Xâydựnggiảipháptốiưuchobàitoánbanđầubằngcáchsửdụngthôngtinđược tínhtoánởbướctrước.4 Cácbướcgiảibàitoánbằnglậptrìnhđộng Bước1:xemxétbàitoáncóthểchiathànhcácbàitoánconthảomãnnguyênlý Bellmankhông.

Bước2:Xácđịnhhệthứctruyhồichobàitoántốiưu. Bước 3: Tìm nghiệmtối ưu của bài toán bằng haiphương pháp Top-Down hoặc Bottom-Up.1 Xemxétbàitoán Xácđịnhxembàitoáncóthểchiathànhcácbàitoánconnhỏhơnkhông,cóthể giảiquyếtđộclậpvớinhau. KiểmtraxembàitoáncóthỏamãnnguyênlýBellmanhoặccácđặcđiểmcủaquy hoạchđộnghaykhông.Nhữngđặcđiểmbaogồmbàitoánconchồngchéovàcấu trúctốiưuphụthuộc.2 Xácđịnhhệthứcxãhội Xâydựngmộthệthốngtruyhồiđểtínhtoángiátrịtốiưucủabàitoántừcácbài toánconnhỏhơn. Địnhnghãicáchbiểudiễncáctrạngtháivàcáchchuyểnđổigiữachúng.

Xácđịnhcôngthứchoặcquytắcđểtínhtoángiátrịtốiưudựatrêncácgiátrịcủa cáctrạngtháicon.3 Tìmnghiệmtốiưu Cóhaiphươngphápchínhđểtìmnghiệmtốiưucủabàitoán:Top-Down(Đệquy vớighinhớ)vàBottom-Up(Lậpbảng). TrongphươngphápTop-Down,chúngtasửdụngđệquyvàlưutrữcácgiátrịđã tínhtoántrướcđóđểkhôngphảitínhlại. TrongphươngphápBottom-Up,chúngtasửdụngmộtbảngđểlưutrữcácgiátrị tốiưuvàđiềnvàobảngtheothứtựcáctrườnghợpcơbảnđếnphứctạp.5 Mộtsốkỹthuậtgiảibàitoánlậptrìnhđộng Cóhaihướngtiếpcậnđểgiảiquyếtmộtbàitoánbằnglậptrìnhđộng 1.1Top-Down(Từtrênxuống–Ghinhớ) TheohướngtiếpcậnTop-Downchúngtasẽbắtđầubằngbàitoánlớnnhấthaybài toánởmứctrêncùngsauđódùngphươngphápđệquyđểgọilờigiảichocácbài toánconởmứcthấphơntiếptheo.Quátrìnhtiếptụcchođếnkhigặpbàitoánnhỏ nhất.Đệquysẽtựđộngtổhợpkếtquảcácbàitoánconđểđượckếtquảbàitoánban đầu.Cáchnàyđòihỏitốnnhiềuthờinguyênđểghinhớtấtcảkếtquảcủacácbài toáncon. Việcthựchiệncácloạighinhớphụthuộcvàocácthamsốthayđổichịutráchnhiệm giảiquyếtvấnđề.Cónhiềukíchthuốckhác nhaucủa bộnhớđệmđược sửdụng trongkỹthuậtghinhớ.Dướiđâylàmộttrongsốđó: Ghinhớ1D:Hàmđệquychỉcómộtđốisốcógiátrịkhôngđổisaumỗilầngọihàm.

Ghinhớ2D:Hàmđệquychỉcóhaiđốisốcógiátrịkhôngđổisaumỗilầngọihàm. Ghinhớ3D:Hàmđệquychỉcóbađốisốcógiátrịkhôngđổisaumỗilệnhgọihàm. Kếtluận:Ghinhớlàmộtkháiniệmlậptrìnhvàcóthểđượcápdụngchobấtkỳngôn ngữnào.Mụctiêutuyệtđốicủanólàtốiưuhóachươngtrình.Thôngthườngvấnđề nàyxuấthiệnkhicácchươngtrìnhthựchiệncácphéptínhnặng.Kỹthuậtnàyđược lưutrữtátcảkếtquảđượctínhtoántrướcđóđểkhôngphảitínhtoánlạichocùng mộtvấnđề.2Bottom-Up(Từdướilên–Lậpbảng) HướngtiếpcậnBottom-Upđầutiênchúngtagiảicácbàitoánconởmứcthấpnhất sauđódùngcáckếtquảnàyđểtínhbàitoánởmứctrên.Quátrìnhtiếptụcchođến khichúngtatìmđượckếtquảbàitoánmứccaonhất.Hướngnàykhôngđòihỏiphải lưulạikếtquảcủatấtcảcácbàitoáncon. Chiếnlượctừdướilêntronglậptrìnhđộnglàlậpbảng Kếtquảcủacácbàitoánconđượclưutrữtrongmộtbảng,thườnglàmộtmảng Sosánhviệclậpbảngvớiviệcghinhớvềđộphứctạpvềthờigian,việclậpbảng thườngsẽhiệuquảhơn.

Việclậpbảngđượcthựchiệntheocácbướcsau:  Xácđịnhcácyếutốcầntốiưuvàxácđịnhrõràngvấnđềcầngiảiquyết.  Tạomộtbảngđểchứakếtquảcủacácbàitoáncon(thườnglàmộtmảng).Sự cốxácđịnhkíchthướccủabảng.  Tạotrườnghợpcơsởhoặcgiátrịbanđầuchobảng.Nhữngconsốnàyđại diệnchocâutrảlờichocácbàitoánconnhỏnhất.  Điềnvàobảngtừcácbàitoánconnhỏnhấtđếnbàitoánlớnnhấtbằngcáchsử dụngphéplặp(thườnglàcácvònglặp).Dựatrêncácbàitoánconđãtínhtoán trướcđó,hãyxácđịnhlờigiảichotừngbàitoáncon.

 Khibảngđượcđiềnđầyđủ,kếtquảcuốicùngthườngđượctìmthấyởmục cuốicùngcủabảng. Kếtluận:Lậpbảnglàmộtkỹthuâthmạnhmẽtrongquyhoạchđộngđểgiảiquyết cácvấnđềphứctạpmộtcáchhiệuquảbằngcáchlưutrữkếtquảcácbàitoáncon trongmảng.2 Sosánhlậpbảngvàghinhớ Ghinhớ:Cáchtiếpcậntừtrênxuống Lưutrữkếtquảcủalệnhgọi Hàmtriểnkhaiđệquy Rấtphùhợpchocácbàitoáncótậphợpđầuvàotươngđốinhỏ Đượcsửdụngkhicácbàitoánconcócácbàitoánconchồngchéo. Lậpbảng:Cáchtiếpcậntừdướilên Lưutrữkếtquảcủacácbàitoáncontrongmộtbảng Triểnkhailặplại Phùhợpchoáccbàitoáncótậphợpđầuvàolớn Đượcsửdụngkhicácbàitoánconkhôngtrùngnhau. Lậpbảng Ghinhớ Tìnhtrạng Quan  hệ  chuyển  trnagj  thái  rất Quanhệchuyểntrạngtháidễnghĩ khónghĩ Mãsố Mã  trở  nên  phứuc  tạp  khi  yêu Mãdễdàngvàítphứctạphơn cầunhiềuđiềukiện Tốcđộ Nhanh  chóng,  vì  truy  cập  trực Chậmdocónhiềulệnhgọiđệquy tiếpvàocác trạngthái trước đó vàbáocáotrảvề từbảng Giải quyết vấn Nếu  một  số  bài  toán  con  trong đềphụ khônggianbài Các mục trong bảng Tiếpcận Lập  bảng  là  một  cách  tiếp  cận Ghi nhớlà một cách tiếpcận đệ lặpđilặplại quy Bảng1:Sosánhlậpbảngvàghinhớ CHƯƠNG 2: TÌM HIỂU VỀ LÝ THUYẾT TRÒ CHƠI 2.1Cáckháiniệmchung Lýthuyếttròchơilàmộtmôhìnhtoánhọcđượcsửdụngđểraquyếtđịnh.Nócóứng dụngtrong mọilĩnh vực khoahọc xã hội,cũng nhưlogic vàkhoa họcmáy tính.Lý thuyếttròchơingàycàngđóngmộtvaitròquantrọngtronglogicvàkhoahọcmáytính.

Đểđượcxácđịnhđầyđủ,mộttròchơiphảixácđịnhrõcácyếutốsau:ngườichơitrong tròchơi,thôngtinhànhđộngcósẵnchomỗingườichơitạimỗithờiđiểmquyếtđịnhvà phầnthưởngchomỗikếtquả.Hầuhếtcáctròchơihợptácđượctrìnhbàydướidạnghàm đặctrưng,trongkhidạngmởrộngvàthôngthườngđượcsửdụngđểxácđịnhcáctrò chơikhônghợptác. Tronglýthuyếttròchơi,dạngthôngthườnghaycònđượcgọilàdạngchiếnlượclàsự môtảvềmộttròchơi.Tròchơithôngthườngthườngđượcthểhiệnbằngmộtmatrận hiểnthịngườichơi,chiếnlượcvàphầnthưởng.Khimộttròchơiđượctrìnhbàyởdạng bìnhthường,ngườitachorằngmỗingườichơihànhđộngđồngthờihoặcítnhấtlàkhông biếthànhđộngcủangườikia. Lýthuyếttròchơilàmộtchủđềtronglậptrìnhcạnhtranhliênquanđếnmộtloạivấnđề nhấtđịnh,trongđócómộtsốngườichơitròchơidựatrêncácnguyêntắcnhấtđịnhvà nhiệmvụthườnglàtìmrangườichiếnthắnghoặcnướcđichiếnthắng Mụctiêulýthuyếttròchơicholậptrìnhcạnhtranh  Ởđâychúngtasẽtậptrungvàocáctròchơihaingườichơikhôngchứacácyếutố ngẫunhiên  Mụctiêucủachúngtalàtìmramộtchiếnlượcmàchúngtacóthểápdụngđể dànhchiếnthắngtrongtròchơibấtkểđốithủcólàmgìnếuchiếnlượcđótồntại  Lýthuyếttròchơihoặclýthuyếttròchơitổhợptrongđóchúngtacóthôngtin hoànhảo(khôngcósựngẫunhiênnhưtungđồngxu)chẳnghạnnhưluậytròchơi, lượtcủangườichơi,mứctốithiểuvàtốiđaliênquanđếncácphátbiểuvấnđề cũngnhưmộtsốđiềukiệnvàràngbuộc  Sẽcóbatrườnghợpcóthểxảyralàthắng,thuahoặchòa  Điềukiệnđầucuốiđượcxácđịnhrõràng  Ngườitachorằngtròchơisẽkếtthúcvàomộtthờiđiểmnàođósaumộtsốnước đicốđịnh.Khônggiốngnhưcờvua,nơibạncóthểcóvôsốnướcđi 2.2Trạngtháitròchơi Chúngtacùngxemxétmộttròchơikhibanđầucóngậy.NgườichơiAvàBdi chuyểnluânphiên,vàngườichơiAbắtđầu.Mốilầnđi,ngườichơiphảiloạibỏ1,2 hoặc3câygậycuốicùngsẽchiếnthắngtròchơi. Vídụ:n=10thìtròchơisẽđượctiếnhànhnhưsau NgườiAloạibỏ2câygậy(còn8câygậy) NgườiBloạibỏ3câygậy(còn5câygậy) NgườiAloạibỏ1câygậy(còn4câygậy) NgườiBloạibỏ2câygậy(còn2câygậy) NgườiAloạibỏ2câycònlạivàchiếnthắng.

Tròchơinàybaogồmcacstrạngthái0,1,2,…,nsốlượngtrạngtháiphụthuộcvàosố gậycònlại. Cáctrạngtháichiếnthắngvàthuacuộc(Winning-Losing) Trạngtháichiếnthắnglàtrạngtháikhingườichơisẽthắngtròchơinếuhọchơitối ưu,vàtrạngtháithualàtrạngtháikhingườingườichơisẽthuatròchơinếuđốithủ tốiưu.Chúngtacóthểphânloạitấtcảcáctrạngtháicủatròchơisaochomỗitrạng tháicócảtrạngtháithắngvàtrạngtháithua. Trongtròchơitrên,trạngthái0làtrạngtháithuacuộcvìngườichơikhôngthểthực hiệnbấtkỳnướcđinào.  Trạngthái1,2và3làtrạngtháichiếnthắngvìchúngtacóthểloạibỏ1,2hoặc3 gậyvàgiànhchiếnthắngtrongtròchơi  Ngượclại,trạngthái4làtrạngtháithua,vìbấtkỳnướcđinàocũngdẫnđếntrạng tháithắngcủađốiphương.

Tổngquáthơn,nếucómộtđộngtháidẫnđếntừtrạngtháihiệntạisangtrạngthái thuacuộcthùtrạngtháihiệntạilàtrạngtháithắng,cònngượclạilàthìtrạngtháithua cuộc. Bằngcáchsửdụngquansátnày,chúngtacóthểphânloạitấtcảcáctrạngtháicủa mộttròchơibắtđầubằngnhữngtrạngtháithuakhikhôngcónướcđinàocóthểthực hiệnđược. Cáctrạngthái0,1,2,…9củatròchơitrêncóthểđượcphânloạinhưsau(W-Thắngvà L-Thua) Trạng 0 1 2 3 4 5 6 7 8 9 thái Kết L W W W L W W W L W quả Bảng2:TrạngtháiW-L Từcáchphânloạinày,chúngtacóthểrútramộtchiếnlượctốiưu:luônđểlạisốgậy chiahếtcho4.Chiếnthuậtnàyđảmbảorằngđốithủluônrơivàotìnhtrạngthua cuộc,vớiđiềukiệnsốgậybanđầukhôngchiahếtcho4.3Đồthịtrạngtháicủatròchơi(Stategraph) Xétmộttròchơigậykhác,khitrongmỗitrạngtháik,tađượcphéploạibỏsốlượngx gậybấtkỳnàosaochoxnhỏhơnkvàchiahếtchok Vídụtrongtrạngthái8chúngtacóthểbỏ1,2hoặc4gậy,nhưngtrongtrạngthái7 chúngtachỉđượcloạibỏ1gậy. Hìnhsauchỉracáctrạngthái1…9củatròchơibằngđồthịtrạngthái,khimỗiđỉnhlà mộttrạngtháivàcáccạnhlàcácđườngđigiữachúng. Hình2:Trạngtháicủatròchơitrênđồthịtrạngthái Trạngtháicuốicùngtrongtròchơinàyluônlàtrạngthái1,làtrạngtháithuavìkhông cónướcđihợplệ.Việcphânloạicáctrạngthái1…9nhưsau: Trạn 1 2 3 4 5 6 7 8 9 gthái Kết L W L W L W L W L quả Bảng3:TrạngtháiL-Wcủađồthịtrạngthái Trongtròchơinày,tấtcảcáctrạngtháisỗchẵnlàcáctrạngtháisốchẵnđềulàtrạng tháithắngvàtấtcảcáctrạngtháisốlẻlàtrạngtháithua.4Tròchơitổhợpcânbằng 2.1Môtả Trò chơi tổ hợplàtròchơigồm:hai người chơi (ở đây gọi người chơi trước là 𝐴 và người chơi sau là 𝐵),mộttập hữu hạn các trạng thái𝑆(viếttắtcủaState)cóthểđạt đượccủatròchơi.Mỗingườichơi có mộttập các bước di chuyển hợp lệ𝑄 đểdi chuyểntừtrạngtháinàysangtrạngtháikhác(gọilàluậtchơi)vàmộttậpcáctrạng thái  kết  thúc  gọi  là𝑇⊂𝑆(viết  tắt  của  Terminal).

 Hai  người  chơi  sẽ  luân  phiên  di chuyểntừtrạngtháinày sangtrạngtháikhác.Ngườiđếnđượctrạngtháikếtthúc trướcsẽlàngườichiếnthắng. Tròchơitổhợpcânbằnglàtròchơiđốikhángthỏamãnnhữngđiềukiệnsau:  Có2ngườichơi  Cómộttậphữuhạncácvịtrícóthểxảyra(cáctrạngthái)củatròchơi  Cóquy luậtchơi ápdụngchohaingườichơilà cân bằng,nghĩalà mỗi ngườichơiđếnlượtmìnhđềucóquyềnchọnmộtphépdichuyểnhợplệtùy ý  Haingườichơilầnlượt,mỗilầnthựchiệnmộtphépdichuyểnhợplệ  Tròchơikếtthúckhiđạttớivịtríkếtthúc.Thôngthườngquyđịnhngười chơidichuyểnđượccuốicùnglàngườichiếnthắng,ngườinàođếnlượtmà kdichuyểnđượcnữathìthua  Nếutròchơikhôngbaogiờkếtthúcsẽcómộtthôngbáorútthăm.Cóthể bổsungthêmđiềukiệnnàođóđểtròchơikếtthúckhoongcângthôngbáo rútthămnhưPtròchơisẽkếtthúckhiđãcóđủsốlầndichuyểnnhấtđịnh màkhôngaithắngthìhaiđấuthủhòa.2TậpP,tậpNvàcáchtìm Đểthuậntiệnchoviệcxâydựngthuậttoán(giànhthắng)củatròchơi,ngườitađưara kháiniệmtậpPvàtậpN.Đólàhaitậpthỏamãncáctínhchấtsau:  N:tậpcáctrạngtháixSsaochonếutrạngtháibanđầucủatròchơilà xthìngười chơi trướcluônchiếnthắng  P:tậpcáctrạngtháixSsaochonếutrạngtháibanđầucủatròchơilà xthìngười chơi sauluônởtrạngtháithắng. Từđịnhnghĩatrên,NvàPsẽthỏamãnbatínhchấtsau: TậpPphảichứatoànbộtrạngtháikếtthúc VớimỗitrạngtháisthuộctậpN,tồntạiítnhấtmộttrạngtháis’đếnđượctừsmà thuộctậpP VớimỗitrạngtháisthuộctậpP,tấtcảcáctrạngtháis’đếnđượctừsphảithuộcN Ràngbuộcđầutiênxácđịnhtrườnghợpcơbảnnhất.Hairàngbuộcsausẽgiúpchúng taliêntụcđệquytừtrườnghợpcơbảnđểxâydựngđượctậpPvàNhoànchỉnh.Ta sẽthấyrõđiềunàyởphầnThuật toán xác định tập P vI N. KhixâydựngđượctậpPvàNtheocácràngbuộctrên,tacóthểdễdàngxâydựng chiếnthuậtthắngchongườichơiAnhưsau(dođâylàtròchơitổhợpcânbằngnên chiếnthuậtthắngcủaBcũngsẽtươngtự): 1.

Nếu𝐴bắt đầu ở trạng thái thuộc N,luôn đi tới trạng thái thuộc Pđể épBđivàotrạngtháithuộcN.Dongườithắnglàngườiđivàotrạngtháikết thúc,màtrạngtháikếtthúclạithuộcPnênchắcchắnAsẽthắng. NếuAbắtđầuởtrạngtháithuộcP,Achỉcóthểkéodàivánđấuvàđợisơ hởcủaB(BđivàovịtríthuộcN)vàdùngchiếnthuậtthắngởtrườnghợp đầu.TuynhiênnếuBcũngchơitốiưuthìchắcchắnAsẽthua.3TổngNimvàtròchơiNim Tổng Nim: TổngNimcủahaisốnguyênkhôngâmlàkếtquảcủaphépcộngkhôngnhớcủahai sốđótronghệcơsố2(còngọilàcộngtheomodun2). Vídụ:  Số 3 hệthập phân viết dưới dạng 11 cơsố2là Số 5 hệthập phân viết dưới dạng 101 cơsố2là Số 8 hệthập phân viết dưới dạng 1000 cơsố2là TổngNimcủachúnglà: 1110(là14tronghệthậpphân) Vậytacó:358=14 Phéptoán(tínhtổngNim)làxorcótínhchấtkếthợp,giaohoán.Đặcbiệt: 0a=a,aa=0,dođónếuab=acthìb=c Trò chơi Nim: Tròchơi Nimlà một trò chơiđơn giảnnhưng cómột vaitrò quantrọng tronglý thuyếttròchơi,vìnhiềutròchơikháccóthểđượcchơibằngchiếnlượctươngtự. Đầutiênchúngtasẽtậpchungvàonim,sauđóchúngtasẽtạorachiếnlượcchocác tròchơikhác. Cónđốnggậytrongnim,vàmỗiđốngbaogồmmộtsốcâygậy.

 Ngườichơilầnlượtdichuyểnvàởmỗilượt,ngườichơichọnmộtđốngcònchứa gậyvàloạibỏsốlượnggậybấtkỳkhỏiđó Ngườichiếnthắnglàngườiloạibỏcâygậycuốicùng. Chúngtacóthểdễdàngphânloạibấtkỳtrạngtháinimnàobằngcáchtínhtổngnims =x1x2…xn,trongđólàphéptoánxor. Cáctrạngtháicótổngnim=0làtrạngtháithuavàtấtcảcáctrạngtháikháclàtrạng tháithắng. Trạng thái thua:trạngtháicuốicùng[0,0,…0]làtrạngtháithua,vàtổngnimcủa nólà0.

Trongcáctrạngtháithuakhác,baogồmbấtkỳnướcđinàodẫnđếntrạngtháithắng, vìkhigiátrịxkthayđổi,tổngnimcũngthayđổi,dođótổngnimkhác0saunướcđi. Trạng thái thắng:chúngtacóthểdichuyểnđếntrạngtháithuanếucómộtđốngbất kỳmàxks<xk. Trongtrườnghợpnày,chúngtacóthểloạibỏgậytừđốngksaochonócònchứaxk sgậy,cáinàysẽdẫnđếntrạngtháithua. Vídụ:xéttrạngthái[10,12,5] Trạngtháinàylàtrạngtháithắngvìtổngnimcủanólà3 Nhưvậy,phảicómộtbướcdẫnđếntrạngtháithua. Tổngnimcủatrạngtháinhưsau: 10 1010 12 1100 5 0101 3 0011 Trongtrườnghợpnày,đốngcó10gậylàđốngduynhấtcómộtbitởvịtríbitngoài cũngbêntráicủatổngnim: 10 1010 12 1100 5 0101 3 0011 Kíchthướcmớicủagậyphảilà103=9,vìvậychúngtasẽchỉloạibỏmộtgậy. Sauđó,trạngtháisẽlà[9,12,5]làmộttrạngtháithua: 9 1001 12 1100 5 0101 0 0000 2.5ĐịnhlýBouton ĐịnhlýBoutonlàtrạngtháicủatròchơiNim(x1,x2,…,xn)thuộcPkhivàchỉkhi tổngnimbằng0. Vídụ: Trạngthái[5,7,9]tươngứngvới579=11>0nênnólàvịtríN Trạngthái[4,12,8]tươngứngvới4128=0nênnólàvịtríP TừđịnhlýsuyrachiếnthuậtgiànhthắngtrongtròchơiNimchuẩnnhưsau: Giảsửhiệntạilà(x1,x2,…,xn)tươngứngvớitổngNimlà: g=x1x2…xn>0 Cóthểchứngminhsẽtồntạithànhphầnximàxi’=g xixi.Cáchđểgiànhchiến thắnglàgiảmxithànhx’i.

Trạngtháimới(x1,x2,…,x(i-1),x’i,x(i+1),…,xn)cótổngNimlàg’=0vì: g’=x1x2…x(i-1)x(i+1)…xn =x1x2…x(i-1)[gx]x(i+1)…xn =(x1x2…x(i-1)xix(i+1)…xn)g=gg=0 QuađịnhlýBouton,chúngtacómộtcáchxácđịnhPvàNdựatrêntổngNim,vàtừ việcchứngminhđịnhlýBouton,takhôngchỉbiếtđượctrạngtháithắng–thuacủa tròchơimàcòncóthểxâydựngđượcmộtchiếnthuậtthắngcụthể.6Tròchơitrênđồthị Mộtsốđồchơicóthểmôtảbằngđồthịcóhướng.Mỗivịtrícủatròchơiđượccoi nhưmộtđỉnhcủađồthịvàmỗiphépdichuyểnhợplệđượcxemnhưmộtcũngdẫntừ đỉnhnàysangđỉnhkhác.ChúngtasẽđinhjnghĩahàmSprague–Grundy(SG)đểxác địnhđượccácvịtríPhoặcNcủatròchơitrênđồthị. ĐồthịtròchơilàđồthịcóhướngG=(X,F)vớiXlàtậpđỉnhkhôngrỗng–làtậpcác vịtrícủatròchơivàFlàhàmtrêntậpXsaochovớimỗix XthìF(x)làmộttập conthuộcXtứclàxXF(x)X.CácđỉnhthuộcF(x)đượcgọilàcácđỉnhcó thểtớitừđỉnhx.NếuF(x)rỗngthìxlàđỉnhkếtthúc.Mộtphépdichuyểnhợplệlàđi từđỉnhxtớimộtđỉnhthuộcF(x). Tròchơitổhợpcânbằngcó2ngườiđượcmôphỏngtrênđồthịG=(X,F)vớiđỉnh xuấtphátx0Xvàtuântheocácquytắcsau: (1) Ngườichơithứunhấtđitrướcvàbắtđầutừđỉnhx0 (2) Haingườichơilầnlượtthựchiệnphépdichuyểntrênđồthị (3) Tạivịtríx,ngườichơiđượcdichuyểnđếnbấtkìyF(x) (4) Ngườichơinàođếnlượtphảinhậnđỉnhkếtthúclàngườithua.7ĐịnhlýSprague–Grundy ĐịnhlýSprague–Grundyphátbiểurằng:mọitròchơitổhợpcânbằngkếtthúctrong hữuhạnbướcđềutươngđươngvớitròchơiNimmộtcột,trongđótrạngtháixcủatrò chơihiệntạitươngứngvớitrạngtháitròchơiNimmộtcộtcóg(x)viênsỏi,trongđó g(x)làgiátrịcủaSprague–Grundycủax. Giảsửcómộttròchơitổnghợp(nhiềuhơnmộttròchơiphụ)gồmcóNtròchơiphụ vàhaingườichơiAvàB.KhiđóĐịnhlýSprague-GrundynóirằngnếucảAvàB đềuchơitốiưu(tứclàhọkhôngmắcbấtkỳsailầmnào),thìngườichơibắtđầutrước đượcđảmbảogiànhchiếnthắngnếuXORcủasốvịtríkhóhiểutrongmỗitròchơi phụkhibắtđầutròchơikhác0.Ngượclại,nếuXORđánhgiábằng0thìngườichơi Achắcchắnsẽthua,bấtkểthếnàođichăngnữa.

CácbướccơbảnkhichúngtaápdụngđịnhlýSprague–Grundytrongbấtkỳtròchơi nào: 1. Chiatròchơitổnghợpthànhcáctròchơiphụ 2. Sauđó,mỗitròchơiphụ,hãytínhsốGrundyởvịtríđó 3. SauđótínhxorcủatấtcảcácsốGrundyđượctínhtoán 4.

Nếugiá trị xorkhác0thìngười chơisắpđến lượt(người chơi đầutiên)sẽ thắng 2.8CáchtínhGrundyNumbers Cách tính Grundy Numbers TrướckhitínhGrundyNumberschúngtacầntìmhiểuvềmộtsốthuậtngữkhác– Mex. Mex lI gì? Mexlàsốloạitrừtốithiểucủamộttậphợpsốkhôngâmnhỏnhấtkhôngcótrong tậphợpđó. GiảsửtacómộttậphợpcácsốnguyênkhôngâmS.MexcủatậphợpS-kýhiệu làmex(S),làsốnguyênnhỏnhấtkhôngcótrongS Mex(S)=min{kN{0}:kS} Vídụ,mex({0,1,3})=2.NếukhôngdichuyểntrongmộttrạngtháisốGrundycủa nólà0,vìmex()=0.Vídụtrongđồthịtrạngthái Hình3:Đồthịtrạngthái CócácsốGrundynhưsau: Hình4:ĐồthịtrạngtháicócácsốGrundy SốGrundycủatrạngtháithualà0,vàsốGrundycủatrạngtháithắnglàsốdương. SốGrundycủamộttrạngtháitươngứngvớisốlượnggậytrongmộtđốngnim. NếuGrundylà0chúngtachỉdichuyểnđếncáctrạngtháicósốGrundylàsố dương,nếuGrundylàx>0chúngracóthểdichuyểnđếncáctrạngtháicósố Grundylàcácsố0,1,…,x-1.

Vídụ,xemxétmộttròchơimàngườichơidichuyểnnhânvật(figure)trongmột mêcung(maze).Mỗiôvuôngtrongmêcungcóthểlàsànhoặctường.Mỗilầnđi, ngườichơiphảidichuyểnnhânvậtmộtsốbướcsangtráihoặclên.Ngườithắng tròchơilàngườithựchiệndichuyểncuốicùng. Hìnhsauminhhọamộttrạngtháikhởiđầucóthểcủatròchơi,khi@kýhiệunhân vậtvà*kýhiệucácôvuôngmànócóthểdichuyển. Hình5:Trạngtháikhởiđầucủatròchơimêcung Cáctrạngtháicủatròchơilàtấtcảcácôsàncủamêcung.Trongmêcungtrêncác sốGrundylànhưsau: Hình6:TrạngtháicủatròchơimêcungcócácsốGrundy Vìthế,mỗitrạngtháicủamêcungtươngứngvớimộtđốngtrongtròchơinim.Ví dụ,sốGrundycủaôdướicùngbênphảilà2,vìnólàmộttrạngtháithắng.Chúng tacóthểđiđếnmộttrạngtháithuavàchiếnthắngtròchơibằngcáchdichuyển4 bướcbêntráihoặctiếnlên2bước.9Tròchơiphụ Chúngtasẽgiảđịnhrằngtròchơicủachúngtabaogồmnhiềutròchơiphụ,và mỗilượtđi,đầutiênngườichơichọnmộttròchơiphụvàsauđódichuyểntrong tròchơiphụnày.Tròchơikếtthúckhikhôngthểthựchiệnbấtkỳdichuyểnnào trongcáctròchơiphụ. Trongtrườnghợpnày,sốGrundycủatròchơilànimsumcácsốGrundycủacác tròchơiphụ.Tròchơicóthểđượcchơinhưtròchơinim,bằngcáchtínhtấtcảcác sốGrundychocáctròchơiphụvàsauđónimsumchúng.

Vídụ,xemxéttròchơicó3mêcung.Trongtròchơinày,mỗilượtđi,ngườichơi chọnmộtmêcungvàsauđódichuyểnnhânvậttrongmêcungnày.Giảthiếtrằng trạngtháibanđầucủatròchơilànhưsau: Hình7:Trạngtháibanđầucủatròchơiphụ SốGrundycủacácmêcunglànhưsau: Hình8:TrạngtháicủatròchơiphụcócácsốGrundy Trongtrạngtháibắtđầu,nimsumcủacácsốGrundylà2  3  3=2,vìthế ngườichơiđầutiêncóthểchiếnthắngtròchơi.Mộtdichuyểntốiưulàdichuyển 2bướctrongmêcungđầutiên,đểtạoranimsumlà033=0. Vídụ:banđầu,cómộtđốngchứangậy.Mỗilượtđi,ngườichơichọnmộtđống vàchianóvào 2đốngkhôngrỗngsaochocácđốngcókíchthướckhácnhau. Ngườichơinàothựchiệndichuyểncuốicùnglàngườichiếnthắngtròchơi. Chof(n)làsốGrundycủađốngcóngậy.SốGrundycóthểđượctínhbằngcách duyệtquatấtcảcáccáchđểchiamộtđốngthành2đống.Vídụ,khin=8,cáckhả năngcóthểlà1+7,2+6và3+5,vìthế:f(8)=mex({f(1)f(7),f(2)f(6), f(3)f(5)}).

Trongtròchơinày,giátrịcủaf(n)đượcdựatrêncácgiátrịcủaf(1),…,f(n-1). Trườnghợpcơbảnlàf(1)=f(2)=0,vìkhôngthểchiamộtđốngcó1và2gậy. côngthứctínhf(n)đượctínhnhưsau:f(n)=mex({f(n-1),f(n-2),f(n-3),…}) Vd:f(3)=mex({f(2),f(1)})=mex({0,0})=1 TươngtựcócácsốGrundylà: f(1)=0 f(2)=0 f(3)=1 f(4)=0 f(5)=2 f(6)=1 f(7)=0 f(8)=2 SốGrundycủan=8là2,vìvậycókhảnăngchiếnthắngtròchơi.Mộtdichuyển tốiưulàtạoracácđống1+7,vìf(1)f(7)=0.5Tròchơihaingườicótổngđiểmbằng0 2.1ĐịnhlýMinimax ĐịnhlýMinimaxlàmộtlýthuyếtcơbảntronglĩnhvựctròchơivàtrítuệnhân tạo,đặcbiệtlàtrongcáctròchơihaingườicótínhcạnhtranhvàcóthôngtinhoàn toàn(zero-sumgames).Địnhlýnàynóivềmốiquanhệgiữahaingườichơitrong tròchơinàyvàmôtảcáchtốiưuhóachiếnlượccủamỗingườichơi. Các yếu tố chính của định lý Minimax lI: Zero-sum game (trò chơi tổng điểm bằng 0):ĐịnhlýMinimaxápdụngchocác tròchơizero-sum,nghĩalàtổngsốđiểmcủacácngườichơilàkhôngđổisaumỗi nướcđi.Nếumộtngườichơiđạtđượclợiích,thìngườichơicònlạisẽchịuthiệt hạitươngứng.

Tối ưu hóa chiến lược: ĐịnhlýMinimaxchobiếtcáchmỗingườichơinênlựa chọnnướcđitốiưunhấtdựatrêncáclựachọncósẵncủađốiphương.Mụctiêulà tốiđahóalợiíchcủangườichơihiệntại,đồngthờitốithiểuhóalợiíchtốiđacủa đốiphương. Cây quyết định (game tree):ĐịnhlýMinimaxđượcápdụngtrêncâyquyếtđịnh củatròchơi,trongđómỗinútđạidiệnchomộttìnhhuốngtròchơisaumỗinước đi.Cácnútláđạidiệnchocáctrạngtháikếtthúccủatròchơi. ĐịnhlýMinimaxlàmộtkháiniệmquantrọngtronglýthuyếttròchơi,đặcbiệtlà trongcáctròchơitổng-không(zero-sumgame)giữahaingườichơi,nơilợiích củamộtngườichínhlàtổnthấtcủangườikia.Địnhlýnàyđượcpháttriểnbởi JohnvonNeumann,vànóđặtnềntảngchohiểubiếtvềchiếnlượctốiưutrongcác tìnhhuốngcạnhtranh. Giải thích Định lý Minimax: ĐịnhlýMinimaxkhẳngđịnh rằngtrongmộttròchơitổng-khôngvớithôngtin hoànchỉnh,cómộtgiátrịcụthể(gọilàgiátrịMinimax)màtạiđó:  Ngườichơithứnhất(gọilà"Maximizer")cóthểđảmbảorằng,vớichiếnlượctối ưucủamình,ítnhấtsẽthuđượcgiátrịnàybấtkểchiếnlượccủangườichơithứ hai.

 Ngườichơithứhai(gọilà"Minimizer")cóthểngănchặnngườichơithứnhấtthu đượcnhiềuhơngiátrịnàyvớichiếnlượctốiưucủamình. Công thức: maxx∈X miny∈Y f(x,y)=miny∈Y maxx∈X f(x,y) Trongđó:  xvàylàcácchiếnlượccủahaingườichơi.  f(x,y)làhàmchitrả,đolườngkếtquảcủatròchơidựatrênsựlựachọnchiếnlược củacảhaingườichơi.  Ngườichơi"Maximizer"tìmcáchtốiđahóagiátrịtốithiểumàhọcóthểbịép nhận.

 Ngườichơi"Minimizer"tìmcáchtốithiểuhóagiátrịtốiđamàđốithủcóthểđạt được. Ý nghĩa: Địnhlýnàycungcấpcơsởchochiếnlượctốiưukhicácngườichơiđốiđầunhau vớimụctiêuhoàntoànđốilập.Nóchophépmỗingườichơixácđịnhcáclựachọn tốiưucủahọkhibiếtđốithủcũngsẽchơimộtcáchtốiưu.Điềunàyđặcbiệtquan trọngtronglậpkếhoạchchiếnlượcvàraquyếtđịnh,từtròchơicờtớiđàmphán kinhdoanh,vàthậmchílàtronglĩnhvựcquânsự. Trong  các  trò  chơi  thực  tế  như  trò  chơi  chọn  đồng  xu,  việc  áp  dụng  định  lý Minimaxgiúpngườichơixácđịnhnhữnglựachọnmanglạilợiíchtốithiểuan toànnhấttrongkịchbảnxấunhất,từđóđảmbảokếtquảtốtnhấtcóthểkhicảhai bêncạnhtranhđềuchơitốiưu. Cách áp dụng công thức Minimax trong bIi toán: Công thức cập nhật dp[i][j]: dp[i][j]=max(min(A,B),min(C,D)) Trongđó:  A =coins[i]+dp[i+2][j]:Điểmsốkhingườichơichọnđồngxui,vàsauđó đốithủchọnđồngxui+1.

 B =coins[i]+dp[i+1][j−1]:Điểmsốkhingườichơichọnđồngxui,vàđối thủchọnđồngxuj.  C =coins[j]+dp[i+1][j−1]:Điểmsốkhingườichơichọnđồngxuj,vàđối thủchọnđồngxui.  D =coins[j]+dp[i][j−2]:Điểmsốkhingườichơichọnđồngxuj,vàsauđó đốithủchọnđồngxuj-1. Minimax trong công thức:  Maximization:Ngườichơichọngiữahailựachọn(chọnđồngxuihoặcj) đểtốiđahóađiểmsốtốithiểumàhọcóthểthuđược.Điềunàythểhiệnvai tròcủa"Maximizer"trongMinimax.

 Minimization:Đốithủsẽcốgắngtốithiểuhóađiểmsốmàngườichơicó thểthuđượctronglượttiếptheobằngcáchchọnđồngxutốiưucủahọ. Điềunàythểhiệnvaitròcủa"Minimizer". Chiến lược tối ưu:Chiếnlượcnàyđảmbảorằngdùđốithủcólựachọnnhưthế nào,ngườichơicũngđãchọnđượclựachọntốtnhấtcóthểdựatrêngiảđịnhđối thủchơitốiưu.2CânbằngNash Cân bằng Nash:Trạngtháitrongđókhôngcóngườichơinàocóđộngcơđểthay đổichiếnlượccủamìnhmộtcáchđơnphương. Cân bằng Nashlàmộtkháiniệmquantrọngtronglý thuyết trò chơi mang lại kết quả tối ưutrongtrườnghợpngườichơikhông đi chệchkhỏichiếnlượcban đầucủahọ.Điềunàyđượcthựchiệnđểđáplạiviệckhôngcóđộngcơnàocung cấpchongườichơivềsựsailệchnhưvậy.TròchơinàyđượcđặttheotêncủaNhà toánhọcJohnNash,ngườixácđịnhlờigiảicủamộttròchơikhônghợptáccósự thamgiacủahaingườichơitrởlên.

Bởivìchiếnlượcvẫntốiưuvàngườidùngkhôngnhậnđượcbấtkỳưuđãinào cũngbiểuthịrằngnhữngngườichơiđãbiếtvềchiếnlượccủanhauvàdođósẽ khôngđichệchhướngchútnào. Vìngười chơikhác vẫnkhôngthay đổichiếnlược của mìnhnênmột cá nhân khôngthểnhậnđượclợiíchgiatăngnàotừsựsailệchđó.Một trò chơi có thể có nhiều hoặc không có điểm cân bằng Nash. Những điểm chính  CânbằngNashcungcấpmộtgiải pháp tối ưuđểđạtđượckếtquảmong muốnbằngcáchkhôngđichệchkhỏichiếnlượcbanđầucủahọ.  Vìcáccánhânđãbiếtvềchiếnlượccủanhaunêncả hai người chơi đều giInh chiến thắngkhimọingườiđềunhậnđượckếtquảmàhọnghĩra.

 Mộtvídụđiểnhìnhlàtình thế tiến thoái lưỡng nan của người tù.  Vìngười chơimong muốngiànhchiến thắngnên họsẽ thựchiệnchiến lượcđóđểdẫnhọđếntrạngtháinhưvậy.Vìvậy,chiếnlượcđượclựachọn làgiảipháptốtnhấtvàtốiưunhấtmàhọcóthểsửdụng.Điềunàycũng kếthợp với chiến lược thống trị.  Hơnnữa,nhưđãnêu,khôngthểcóbấtkỳtrạngtháicânbằngNashnào trongtròchơi.Vìvậy,không phải lúc nIo chiến lược được chọn cũng lI chiến lược tối ưu. Cách tìm điểm cân bằng Nash ĐểtìmđiểmcânbằngNash,trướctiênngườitaphảiđưaratấtcảcáctìnhhuống cóthểxảyratrongmộttròchơivàsauđótìmratìnhhuốngtốiưutrongsốđó.

Trongtròchơicóhaingườichơi,họsẽphảivượtquatấtcảcáccáchchơimàmột ngườicóthểchơi.Trongtrườnghợpkhôngaitrongsốhọđichệchkhỏichiếnlược củamìnhthìchúngtacóthểnói,trạngtháicânbằngNashđãđến. Vídụ:bàitoánMatchingPennies Trongtròchơinày,cóhaingườichơiAvàB,mỗingườicóhailựachọnHead(H) hoặcTail(T).Kếtquảcủatròchơiphụthuộcvàosựkhớpgiữalựachọncủa2 ngườichơinhưsau:  Nếucảhaingườichơichọncùngmặt(cùngHhoặccùngT),NgườichơiAthắng vàNgườichơiBthua.  Nếuhaingườichơichọnkhácmặt(mộtchọnHvàmộtchọnT),NgườichơiA thuavàNgườichơiBthắng. Matrậnlợiích(PayoffMatrix) MatrậnlợiíchchotròchơiMatchingPenniesđượcbiểudiwwnxnhưsau: BchọnH BchọnT AchọnH (1,-1) (-1,1) AchọnT (-1,1) (1,-1) Trongmatrậnnày: CặpsốđầutiêntrongmỗiôlàlợiíchcủangườichơiA CặpsốthứhaitrongmỗiôlàlợiíchcủangườichơiB NếuAchọnHvàBchọnH,lợiíchcủaAlà1vàlợiíchcủaBlà-1 NếuAchọnHvàBchọnT,lợiíchcủaAlà-1vàlợiíchcủaBlà1 Chiếnlượctốiưu:Chiếnlượctốiưuchomỗingườichơidựatrênmụctiêutốiđa hóathưởnghoặctốithiểuhóarủiro.

CHƯƠNG 3: ỨNG DỤNG LẬP TRÌNH ĐỘNG TRONG LÝ THUYẾT TRÒ CHƠI N ĐỒNG XU 3.1Giớithiệuvềtròchơinđồngxu Bốicảnh:cónđồngxutrênbàn,mỗiđồngxucógiátrịkhácnhau.Haingườichơi thaynhauchọnmộtđồngxutừmộttronghaiđầucủadãyxu Mụctiêu:mỗingườicốgắngthuthậpsốtiềnnhiềunhấtcóthể.Ngườichiếnthắng làngườicótổngsốtiềnnhiềuhơnkhitấtcảcácđồngxuđềuđãđượcchọn. Chiếnlược:sửdụnglậptrìnhđộngđẻxácđịnhchiếnlượctốiưucủamỗingười chơi.Mỗiquyếtđịnhsedựavàotrạngtháihiệntạicủatròchơivàgiátrịdựkiến củacácnướcđitươnglai.2Cáckhíacạnhcủalýthuyếttròchơitrongbàitoánnày Chiến lược Tối ưu:Trongbàitoánnày,mỗingườichơicầnphảixemxétchiến lượctốiưukhôngchỉdựatrêngiátrịhiệntạimàcòndựatrêncáclựachọntiếp theocủađốithủ.Chiếnlượcnàydựatrênviệcdựđoánvàphảnứnglạihànhđộng củađốithủ,điểnhìnhcholýthuyếttròchơi. Dự đoán hInh động của đối thủ:Ngườichơikhôngchỉtínhtoánlựachọndựa trêngiátrịtrựctiếpcủađồngxumàcòncầnphảidựđoánlựachọntốiưucủađối thủđểtốiđahóakếtquảcủamìnhtrongtươnglai.Điềunàyđòihỏiviệcxemxét tấtcảcáckhảnăngvàlựachọnphảnứngtốtnhất. Minimax Algorithm:Côngthứctínhgiátrịdp[i][j]trongtròchơichọnđồngxu phảnánhthuậttoánMinimax,nơimỗingườichơicốgắngtốiđahóalợiíchtối thiểumàhọcóthểnhậnđượcdựatrênsựlựachọntốiưucủađốithủ.Trongđó, ngườichơisẽchọnđộngtháimàtốiđahóalợiíchtốithiểucóthểđạtđược,dựa trêngiảđịnhrằngđốithủcũngchơitốiưu.

Nash Equilibrium:Trongbốicảnhnày,mỗingườichơichọnđồngxusaocho khôngcólựachọntốthơnnếubiếttrướclựachọncủađốithủ,đạtđếnđiểmcân bằngNash,nơikhôngaicóthểcảithiệnvịthếcủamìnhbằngcáchthayđổiđơn phươnglựachọncủahọ.3 BIi toán VớitròchơiNđồngxu,chúngtacóthểmôphỏngchiếnlượcsửdụnglậptrình độngthôngquamộtvídụcụthể.Giảsửcó4đồngxucógiátrịlầnlượtlà2,4, 6và8.Chúngtasẽtìmchiếnlượctốiưuchongườichơiđầutiên,ngườicố gắngthuthậpsốtiềnnhiềunhất. Bước 1: Xác định các trạng thái vI giá trị Mỗitrạngtháicủatròchơiđượcbiểudiễnbởicácđồngxucònlạitrênbàn.Chúng tasẽxâydựngmộtmatrậndptrongđódp[i][j]làsốtiềntốiđamàngườichơiđầu tiêncóthểthuđượckhichỉcòncácđồngxutừvịtríiđếnj. Bước 2: Xây dựng bảng lập trình động Cáchtínhtoándp[i][j] sẽdựatrênviệcngườichơiđólựachọnđồngxuởđầu i hoặccuốij  Nếungườichơichọnđồngxui,đốithủsẽtốiưuhóasốtiềnmàhọcóthểthuđược từđoạn[i+1,j],vìvậysốtiềnngườichơinàythuđượcsẽlàcoins[i]+(tổngđoạn -dp[i+1][j]).  Tươngtự,nếuchọnđồngxuj,sốtiềnsẽlàcoins[j]+(tổngđoạn-dp[i][j-1]).

Trongđótổngđoạnlàtổnggiátrịcủađồngxutừiđếnj. Bước 3: Tính toán bảng giá trị Giảsửcácđồngxucógiátrịnhưđãđềcập:[1,2,3,4].Tasẽxâydựngbảngdp dựatrêncáctrườnghợpcơbản:  Khii==j,tứcchỉcómộtđồngxu,dp[i][j]=coins[i]vìngườichơisẽchọnđồng xuđó. Giảithíchtừngbiến: 1. Biến a:Đâylàtrườnghợpsaukhingườichơihiệntạichọnđồngxuởvịtríi,đối thủcóthểchọnđồngxutiếptheoởi+1.Nếuđiềunàyxảyra,lựachọntiếptheo củangườichơihiệntạisẽlàtrongphạmvitừ i+2 đến j.Biến a lưugiátrịcủa dp[i+2][j],tứcsốtiềntốiđamàngườichơihiệntạicóthểthuđượctừđoạncònlại nếuđốithủchọnđồngxuởi+1.Nếui+2lớnhơnj,tứclàkhôngcònđồngxunào đểchọn,giátrịcủaasẽlà0,vìkhôngcònlựachọnnàokhảthi.

Biến b:Đâylàtrườnghợpngườichơihiệntạichọnđồngxuởivàđốithủchọn đồngxuởjhoặcngượclại.Sauđó,lựachọntiếptheocủangườichơihiệntạisẽlà trongphạmvitừi+1đếnj-1.Biếnblưugiátrịcủadp[i+1][j-1],tứcsốtiềntốiđa màngườichơihiệntạicóthểthuđượctừđoạncònlại.Nếui+1lớnhơnj-1,không cònđồngxunàogiữahaivịtrínày,giátrịcủabsẽlà0. Biến c:Đâylàtrườnghợpsaukhingườichơihiệntạichọnđồngxuởvịtríj,đối thủcóthểchọnđồngxutiếptheoởj-1.Sauđó,lựachọntiếptheocủangườichơi hiệntạisẽlàtrongphạmvitừi đến j-2.Biến clưugiátrịcủadp[i][j-2],tứcsố tiềntốiđamàngườichơihiệntạicóthểthuđượctừđoạncònlạinếuđốithủchọn đồngxuởj-1.Nếuilớnhơnj-2,tứclàkhôngcònđồngxunàođểchọn,giátrịcủa csẽlà0.4 Khởi tạo vI Định nghĩa 3.1Khởitạomatrậndp Mộtmatrậnkíchthước4x4vớitấtcảcácgiátrịkhởitạolà0. Các trường hợp cơ bản:Đốivới dp[i][i] vớimọi i,giátrịsẽbằnggiátrịcủa đồngxutạivịtríđó,vìchỉcómộtđồngxuđểchọn.2Cậpnhậtmatrận Khitínhdp[i][j],chúngtađangcốgắngtìmsốtiềntốiđamàngườichơihiệntại cóthểthuđượcnếuhọbắtđầuchơitrongphạmvitừđồngxu i đếnđồngxu j. Trongcôngthứcnày: dp[i][j]=max(coins[i]+min(dp[i+2][j],dp[i+1][j-1]),coins[j]+min(dp[i+1][j- 1],dp[i][j-2]))  Ngườichơiđầutiên(lượtchọni):  Chọnđồngxu i,sauđóđốithủsẽchọntốiưu(nghĩalà  min(dp[i+2][j], dp[i+1][j-1])).

 Ngườichơithứhai(lượtchọnj):  Chọnđồngxuj,sauđóđốithủsẽchọntốiưu(nghĩalà min(dp[i+1][j-1], dp[i][j-2])). Cácgiátrịa,b,vàcđượcsửdụngđểtínhcáctrườnghợpkhácnhaumàđốithủcó thểchọnsaulượtcủangườichơihiệntại:  a=dp[i+2][j]:Đâylàsốtiềntốiđamàngườichơihiệntạicóthểthuđượcsaukhi họchọnđồngxuởvịtríivàđốithủchọnđồngxuởvịtríi+1. Vídụ,nếui=0vàj=3,vàngườichơichọnđồngxuởvịtrí0(i),đốithủchọnđồng xuởvịtrí1(i+1),thìasẽlàgiátrịcủadp[2][3],làsốtiềntốiđamàngườichơicó thểthuđượctừhaiđồngxucònlại(6và8). Vídụ,bsẽlàgiátrịcủadp[1][2]nếungườichơichọnđồngxuởvịtrí0vàđốithủ chọnđồngxuởvịtrí3.  c=dp[i][j-2]:Đâylàsốtiềntốiđamàngườichơihiệntạicóthểthuđượcnếuhọ chọnđồngxuởvịtríjvàđốithủchọnđồngxuởvịtríj-1. Vídụ,csẽlàgiátrịcủadp[0][1]nếungườichơichọnđồngxuởvịtrí3vàđốithủ chọnđồngxuởvịtrí2.3Tínhgiátrịtốiưuchocácđoạnđồngxucóđộdàilớnhơn1 Xétcáckhoảngcó2đồngxu(length=2) Vớii=0,j=1 a=dp[2][1]=0(vìkhôngtồntại) b=dp[1][0]=0(vìkhôngtồntại) c=0 dp[0][1]=max(coins[0]+min(a,b),coins[1]+min(b,c))=max(2+0,4+0)= 4 Xétcáckhoảngcó3đồngxu(length=3) Vớii=0,j=2 a=dp[2][2]=6 b=dp[1][1]=4 c=dp[0][0]=2 dp[0][2]=max(coins[0]+min(a,b),coins[2]+min(b,c))=max(2+4,6+2)= 8 Vớii=1,j=3 a=dp[3][3]=8 b=dp[2][2]=6 c=dp[1][1]=4 dp[1][3]=max(coins[1]+min(a,b),coins[3]+min(b,c))=max(4+6,8+4)= 12 Xétkhoảngtừ0đến3(length=4) Vớii=0,j=3 a=dp[2][3]=8 b=dp[1][2]=6 c=dp[0][1]=4 dp[0][3]=max(coins[0]+min(a,b),coins[3]+min(b,c))=max(2+6,8+4)= 12 Giátrịtốiưucủatròchơilàdp[0][3]=12.

Code:  Giảibàitoántròchơinđồngxubằngphươngphápđệquy Sosánhlậptrìnhđộngvàđệquy 3.1 Đệquy Ưuđiểm:  Dễhiểuvàtriểnkhai  Giảipháptrựctiếpdựatrênđịnhnghĩacủabàitoán  Phùhợpvớicácbàitoáncókíchthướcnhỏhoặcgiảithuật đơngiản Nhượcđiểm  Cóthểgặphiệntượngtrùnglặptínhtoánvìmộtsốtrượng hợpconđượctínhtoánnhiềulần  Hiệusuấtkhôngtốtđốivớicácbàitoáncókíchthướclớn.2 Lậptrìnhđộng Ưuđiểm:  Loạibỏhiệntượngtrùnglặpbằngcáchlưutrữcáckếtquả củacácbàitoánconđãđượctínhtoán  Cảithiệnhiệusuấtnhờbộnhớlưutrữ  Phùhợpvớicácbàicókíchthướclớn Nhượcđiểm:  Phứctạphơnsovớitriểnkhaiđệquyđơnthuần  Yêucầunhiềubộnhớhơn. TÀI LIỆU THAM KHẢO 1.Pub_Tai-Lieu-Giao-Khoa-Chuyen-Tin-Quyen-3-3.com/file/d/1fGOSJgBkO7H_Ae2Hm0SqkR6rZXXyXxt/view? fbclid=IwZXh0bgNhZW0BMQABHQIKKZ0Ausqrk8ahM2itaPjVxQpG2AsK7ci5nKe WfAUOrPWQAUTA69NqJg_aem_AWJEtwlneb275WJ5PLpYF5xhX- 7HZLZRGfmlFThmYkKxXoEu0fk_SDfyv9mHkjjuyt0 2.Antti Laaksonen,Competitive Programmer’s Handbook,DraftOctober15,2017.  An  introduction  to  dynamic  games. Dynamic Programming-Quy hoạch động trong lập trình.What are the most effective ways to use dynamic programming in game theory? (2024, February27).Game Theory and Strategy.

 The  Mathematical  Association  of America.OntheTheoryofGamesofStrategy.Contributions to the Theory of Games.Theory of Games and Economic Behavior.TrươngMinhHuyVũ.Lý thuyết trò chơi và chính trị quốc tế.