+2

Zero-sum games với hữu hạn hai người (phần 1)

Giới thiệu

Bài viết này đề cập đến các trò chơi hai người chơi, trong đó mỗi người chơi chọn từ rất nhiều chiến lược thuần túy hoặc ngẫu nhiên trong số các chiến lược và tổng phần thưởng của những người chơi luôn bằng 0.

Định nghĩa và định lý cơ bản

Vì tất cả dữ liệu của một trò chơi có tổng bằng 0 hữu hạn hai người có thể được tóm tắt trong một ma trận, những trò chơi như vậy được gọi là matrix game.

Định nghĩa 1 (Matrix game) Matrix game là một ma trận A kích thước m×nm \times n gồm các số thực, trong đó mm là số hàng và nn là số cột. Chiến lược của người chơi 1 là phân phối xác suất pp trên các hàng của A, tức là một phần tử của tập hợp

Imgur

Tương tự, chiến lược (hỗn hợp) của người chơi 2 là phân phối xác suất qq trên các cột của A, tức là một phần tử của tập hợp

Imgur

Chiến lược p của người chơi 1 được gọi là thuần túy nếu tồn tại hàng ii với pi=1p_i = 1. Chiến lược này cũng được ký hiệu là eie^i. Tương tự, chiến lược q của người chơi 2 được gọi là thuần túy nếu có cột jj với qj=1q_j = 1. Chiến lược này cũng được ký hiệu là eje^j.

Việc giải thích một matrix game A như sau. Nếu người chơi 1 chơi hàng ii (tức là chiến lược thuần túy eie^i) và người chơi 2 chơi cột jj (tức là chiến lược thuần túy eje^j), thì người chơi 1 nhận phần thưởng aija_{ij} và người chơi 2 phải trả aija_{ij} (và do đó, nhận aij-a_{ij}), trong đó aija_{ij} là giá trị trong hàng ii và cột jj của ma trận A. Nếu người chơi 1 chơi chiến lược p và người chơi 2 chơi chiến lược q, thì người chơi 1 sẽ nhận được phần thưởng mong muốn, đó là

Imgur

và người chơi 2 nhận -pAq.

Để giải quyết matrix game, tức là, thiết lập những gì người chơi thông minh sẽ hoặc nên làm, các khái niệm về chiến lược maximin và minimax là rất quan trọng.

Định nghĩa 2 (chiến lược Maximin và Minimax) Chiến lược p là chiến lược maximin của người chơi 1 trong matrix game A nếu:

Imgur

Chiến lược q là chiến lược minimax của người chơi 2 trong matrix game A nếu:

Imgur

Nói cách khác: chiến lược maximin của người chơi 1 tối đa hóa phần thưởng tối thiểu (đối với chiến lược của người chơi 2) của người chơi 1 và chiến lược minimax của người chơi 2 tối thiểu hóa mức tối đa (đối với chiến lược của người chơi 1) mà người chơi 2 phải trả cho người chơi 1. (Có thể chứng minh bằng phân tích toán học cơ bản rằng chiến lược maxin và minimax luôn tồn tại) Tất nhiên, sự bất đối xứng trong các định nghĩa này là do thực tế là, theo quy ước, một matrix game đại diện cho chi phí mà người chơi 2 phải trả cho người chơi 1.

Để kiểm tra xem chiến lược p của người chơi 1 có phải là chiến lược maximin hay không, cần kiểm tra xem bất đẳng thức đầu tiên trong Định nghĩa 2.2 có đúng với eje^j với mọi j=1,...,nj = 1,...,n hay không hay mọi q n\in △^n. Một quan sát tương tự cũng áp dụng cho các chiến lược minimax. Nói cách khác, để kiểm tra xem một chiến lược có phải là maximin (minimax) hay không, cần phải xem xét hiệu suất của nó so với mọi chiến lược thuần túy, tức là cột (hàng).

Tại sao chúng ta lại quan tâm đến những chiến lược như vậy? Thoạt nhìn, những chiến lược này dường như thể hiện một thái độ rất dè dặt hoặc bi quan, đề phòng trường hợp xấu nhất. Tuy nhiên, lý do cho việc xem xét các chiến lược maximin/minimax được cung cấp bởi định lý minimax, nói rằng với mọi matrix game A có một số thực v=v(A)v = v(A) với các tính chất sau:

(a) Một chiến lược p của người chơi 1 đảm bảo phần thưởng ít nhất là vv cho người chơi 1 (tức là pAq v\ge v cho tất cả các chiến lược q của người chơi 2) khi và chỉ khi p là chiến lược maximin.

(b) Chiến lược q của người chơi 2 đảm bảo trả nhiều nhất vv từ người chơi 2 cho người chơi 1 (tức là pAq v\le v cho tất cả các chiến lược p của người chơi 1) khi và chỉ khi q là chiến lược minimax.

Do đó, người chơi 1 có thể nhận được phần thưởng ít nhất là vv bằng cách chơi chiến lược maximin và người chơi 2 có thể đảm bảo trả không nhiều hơn vv — do đó, đảm bảo phần thưởng ít nhất là vv — bằng cách chơi chiến lược minimax. Vì những lý do này, giá trị v=v(A)v = v(A) còn được gọi là giá trị của trò chơi A — nó đại diện cho giá trị của người chơi 1 khi chơi trò chơi A — và chiến lược maximin và minimax được gọi là chiến lược tối ưu tương ứng cho người chơi 1 và 2. Vì vậy, ‘giải quyết’ trò chơi A, đương nhiên có nghĩa là xác định các chiến lược tối ưu và giá trị của trò chơi.

Định nghĩa 3 (Điểm yên ngựa) Vị trí (i,j)(i,j) trong matrix game A được gọi là điểm yên ngựa (saddlepoint) nếu:

aijakja_{ij} \ge a_{kj} với mọi k=1;...;mk = 1; ...; maijaika_{ij} \le a_{ik} với mọi k=1;...;nk = 1; ...; n

tức là, aija_{ij} là cực đại trong cột jj và cực tiểu trong hàng ii.

Rõ ràng, nếu (i,j)(i,j) là điểm yên ngựa, thì người chơi 1 có thể đảm bảo phần thưởng ít nhất là aija_{ij} bằng cách chơi chiến thuật thuần túy hàng ii, vì aija_{ij} là tối thiểu ở hàng thứ ii. Tương tự, người chơi 2 có thể đảm bảo phần thưởng ít nhất là aij-a_{ij} bằng cách chơi chiến thuật thuần túy cột jj, vì aija_{ij} là cực đại trong cột jj. Do đó, aija_{ij} phải là giá trị của trò chơi A: v(A)=aijv(A) = a_{ij}, eie^i là chiến lược tối ưu (maximin) của người chơi 1 và eje^j là chiến lược tối ưu (minimax) của người chơi 2.

Tài liệu tham khảo

  1. Giải thuật và lập trình - Thầy Lê Minh Hoàng
  2. cp-algorithms.com
  3. Handbook Competitive Programming - Antti Laaksonen
  4. Competitve programming 3 - Steven Halim, Felix Halim
  5. Game Theory - Giacomo Bonanno

©️ Tác giả: Trần Quang Hiệp từ Viblo


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí