ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
----------------
NGUYỄN THỊ LỆ
GIẢI THUẬT TÌM KIẾM MINIMAX VÀ ỨNG DỤNG TRONG
CÁC TRÒ CHƠI CÓ TỔNG BẰNG KHÔNG
Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán
Mã số: 60.46.35
LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN THỊ HỒNG MINH
Hà Nội - 2009
2
Mục lục
LỜI NÓI ĐẦU.........................................................................................................5
CHƯƠNG 1: TỔNG QUAN VỀ CÁC VẤN ĐỀ TÌM KIẾM..............................7
1.1 Bài toán tìm kiếm và không gian trạng thái....................................................................7
1.1.1 Bài toán tìm kiếm......................................................................................................7
1.1.2 Không gian tìm kiếm.................................................................................................9
1.2 Các kỹ thuật tìm kiếm cơ bản.........................................................................................12
1.2.1 Tìm kiếm không có thông tin..................................................................................13
1.2.2 Tìm kiếm có thông tin.............................................................................................16
1.2.3 Tìm kiếm đối kháng................................................................................................17
CHƯƠNG 2: GIẢI THUẬT TÌM KIẾM MINIMAX.........................................21
2.1 Giới thiệu........................................................................................................................21
2.1.1 Trò chơi có tổng bằng không (Zero-sum-game).....................................................22
2.1.2Định lý Minimax......................................................................................................27
2.2 Giải thuật Minimax.........................................................................................................28
2.2.1 Ý tưởng....................................................................................................................28
2.2.2 Áp dụng giải thuật Minimax đến độ sâu lớp cố định.............................................32
2.2.3 Thủ tục Minimax.....................................................................................................34
2.2.4 Đánh giá...................................................................................................................39

hợp quá lớn của cây trò chơi mà cả người và máy không thể (và không bao giờ) có
thể tìm kiếm vét cạn (hết mọi khả năng). Do đó phương pháp tìm kiếm duy nhất là
chỉ tìm kiếm đến một độ sâu giới hạn nào đó và chọn nước đi dẫn đến một thế cờ có
lợi nhất cho mình. Do phải tính cả khả năng chống trả của đối phương nên ta không
dùng được các thuật toán tìm kiếm thông thường mà phải dùng một thuật toán tìm
kiếm riêng cho cây trò chơi, đó là thuật toán theo chiến lược Minimax. Đây cũng là
chiến lược hiệu quả áp dụng trong các trò chơi có tổng bằng không. Chúng ta đều
biết, nhiều tình huống trong thực tế đặc biệt là trong lĩnh vực Kinh tế, Chính trị có thể
nhìn nhận như một trò chơi có tổng bằng không. Do đó việc nghiên cứu chiến lược
tìm kiếm nước đi cho dạng trò chơi này có thể mang lại những ý nghĩa thực tiễn nhất
định.
Nội dung của luận văn tìm hiểu và nghiên cứu về thuật toán tìm kiếm đối
kháng Minimax, các cải tiến của nó và ứng dụng trong trò chơi có tổng bằng không.
Nội dung bản luận văn được chia làm 3 chương:
 Chương 1 trình bày một cách tổng quan về các vấn đề tìm kiếm : bài toán tìm
kiếm, biểu diễn vấn đề bằng không gian trạng thái và các kỹ thuật tìm kiếm cơ bản.
5
 Chương 2 trình bày giải thuật tìm kiếm Minimax và giải thuật cải tiến Alpha-
beta áp dụng cho các trò chơi với tổng bằng không. Mỗi giải thuật được trình bày
gồm các nội dung: ý tưởng, thủ tục thực hiện giải thuật và đánh giá.
 Chương 3 trình bày một ứng dụng của thuật toán tìm kiếm Minimax áp dụng
cho trò chơi xếp các quân hậu lên bàn cờ có chướng ngại vật.
Trong thời gian học tập và nghiên cứu để hoàn thành luận văn này, tác giả đã
nhận được sự quan tâm, hướng dẫn, đóng góp của các thầy cô, các bạn bè và người
thân.
Trước hết, tác giả xin được dành lời cảm ơn chân thành và lòng biết ơn sâu
sắc nhất tới giáo viên hướng dẫn của mình là Tiến sĩ Nguyễn Thị Hồng Minh, người
đã định hướng, gợi mở những ý tưởng sâu sắc và hiệu quả, đã tận tình chỉ bảo giúp
đỡ tác giả về mọi mặt để có thể hoàn thành nhiệm vụ nghiên cứu.
Luận văn được thực hiện bằng những kiến thức mà tác giả được trang bị trong

⊆
Γ
+
và

T là một máy Turing, thì T tính f nếu:
- Nếu mỗi x có một số giá trị y mà R(x,y) thì T truy nhập vào với đầu ra z mà R(x,z)
( có thể có nhiều y, và T chỉ cần một trong số chúng)
- Nếu với giá trị x mà không có giá trị y thỏa mãn R(x,y) thì T loại bỏ x.
Chú ý rằng đồ thị của hàm bộ phận là một quan hệ nhị phân, và nếu T tính một hàm
bộ phận thì hầu hết mọi giá trị có thể cho đầu ra.
7
Một quan hệ R có thể được biểu diễn như một bài toán tìm kiếm, và một máy Turing
tính R còn được gọi để giải quyết nó. Mọi bài toán tìm kiếm đều tương ứng với bài
toán quyết định, cụ thể là:
L(R) = { x |
∃
yR(x,y)}.
Tìm kiếm nghĩa là tìm một hay nhiều mẩu thông tin đã được lưu trữ. Thông
thường, thông tin được chia thành các mẩu tin (record), mỗi mẩu tin đều có một
KHÓA (key) dùng cho việc tìm kiếm. Ta sẽ luôn có một khoá cho trước giống như
khoá của các mẩu tin mà ta cần tìm. Mỗi mẩu tin được tìm thấy sẽ chứa toàn bộ
thông tin để cung cấp cho một quá trình xử lý nào đó. Việc tìm kiếm được áp dụng
rất đa dạng và rộng rãi.
Ví dụ: Một Ngân hàng nắm giữ tất cả thông tin của rất nhiều tài khoản khách
hàng và cần tìm kiếm để kiểm tra các biến động. Một hãng Bảo hiểm hay một hệ
thống trợ giúp bán vé xe, vé máy bay….Việc tìm kiếm thông tin để đáp ứng việc sắp
đặt ghế và các yêu cầu tương tự như vậy là thực sự cần thiết.
Một phát biểu Bài toán tìm kiếm thường được sử dụng nhất là: “Cho một bảng
gồm n bản ghi R

o
, Op, T
G
) hoặc bộ 5: (S, T
0
, Op, T
G
,, Pcost).
Trong đó: S là tập các trạng thái, T
0
là trạng thái ban đầu, Op là tập các toán tử hay
tập các phép chuyển trạng thái mà có thể chuyển một trạng thái này sang trạng thái
khác, T
G
là trạng thái đích. Pcost là chi phí đường đi. Mục đích của bài toán là tìm ra
cách chuyển từ trạng thái ban đầu sang trạng thái đích, nếu theo bộ 5 có thêm Pcost
thì bài toán cần tìm nghiệm tốt nhất nghĩa là tìm cách chuyển từ trạng thái ban đầu
đến trạng thái đích với chi phí nhỏ nhất (hoặc lớn nhất).
Phát biểu chi tiết hơn của cách biểu diễn này chúng ta sẽ xét trong mục không gian
tìm kiếm dưới đây.
1.1.2 Không gian tìm kiếm
1.1.2.1 Không gian tìm kiếm
Khi muốn giải quyết một vấn đề nào đó bằng tìm kiếm, trước hết ta phải xác
định không gian tìm kiếm. Không gian tìm kiếm bao gồm tất cả các đối tượng mà ta
cần quan tâm để tìm ra trong đó đối tượng yêu cầu. Đó có thể là không gian liên tục,
chẳng hạn không gian các véctơ thực n chiều; hoặc cũng có thể là không gian các đối
tượng rời rạc như tập các nút của đồ thị hay tập các lời giải của bài toán [7].
Một cách chung nhất, nhiều bài toán phức tạp đều có dạng "tìm đường đi
trong đồ thị" hay nói một cách hình thức hơn là "xuất phát từ một đỉnh của một đồ
thị, tìm đường đi hiệu quả nhất đến một đỉnh nào đó". Một phát biểu khác thường

gồm tất cả các trạng thái có thể có của bài toán và Pcost(T
i-1
,T
i
) là chi phí để biến đổi
từ trạng thái T
i-1
sang trạng thái T
i
. Tuy nhiên, từ một trạng thái T
i-1
ta có nhiều cách
để biến đổi sang trạng thái T
i
. Khi nói đến một biến đổi cụ thể từ T
i-1
sang T
i
ta sẽ
dùng thuật ngữ hướng đi (với ngụ ý nói về sự lựa chọn).
Hình 1.1: Mô hình chung của các vấn đề-bài toán phải giải quyết bằng phương pháp
tìm kiếm lời giải. Không gian tìm kiếm là một tập hợp trạng thái - tập các nút của đồ
thị. Chi phí cần thiết để chuyển từ trạng thái này sang trạng thái khác

được biểu diễn
dưới dạng các con số nằm trên cung nối giữa hai nút tượng trưng cho hai trạng thái.
1.1.2.2 Biểu diễn vấn đề trong không gian trạng thái
Ta sẽ xét việc biểu diễn một vấn đề trong không gian trạng thái sao cho việc
giải quyết vấn đề được quy về việc tìm kiếm trong không gian trạng thái. Một phạm
vi rộng lớn các vấn đề, đặc biệt các câu đố, các trò chơi, có thể mô tả bằng cách sử

G
các trạng thái kết thúc (trạng thái đích). T
G
là tập con của không
gian S. Trong nhiều vấn đề (chẳng hạn các loại cờ) có thể có nhiều trạng thái đích và
ta không thể xác định trước được các trạng thái đích. Nói chung trong phần lớn các
vấn đề hay, ta chỉ có thể mô tả các trạng thái thỏa mãn một số điều kiện nào đó.
Khi biểu diễn một vấn đề thông qua các trạng thái và các phép chuyển, thì
việc tìm nghiệm của bài toán được quy về việc tìm đường đi từ trạng thái ban đầu tới
trạng thái đích. (Một đường đi trong không gian trạng thái là một dãy phép chuyển
dẫn một trạng thái tới một trạng thái khác).
Chúng ta có thể biểu diễn không gian trạng thái bằng đồ thị định hướng, trong
đó mỗi đỉnh đồ thị tương ứng với một trạng thái. Nếu có phép chuyển R biến đổi
trạng thái u thành trạng thái v, thì có cung gán nhãn R đi từ đỉnh u tới đỉnh v. Khi đó
một đường đi trong không gian trạng thái sẽ là một đường đi trong đồ thị.
Sau đây chúng ta sẽ xem xét một ví dụ về không gian trạng thái được xây dựng cho
bài toán 8 số.
Ví dụ : Bài toán 8 số. Cho bảng 3x3 ô và tám quân mang số hiệu từ 1 đến 8, còn lại
một ô trống. Mỗi quân ở cạnh ô trống có thể được chuyển dịch tới ô trống đó. Yêu
cầu của bài toán là tìm ra một dãy các chuyển dịch để biến đổi trạng thái ban đầu của
11
bảng (hình bên trái) thành một trạng thái xác định nào đó, chẳng hạn trạng thái trong
hình bên phải. Xem hình minh họa dưới đây:
Hình 1.2: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số.
Trong bài toán này, trạng thái ban đầu là trạng thái ở bên trái hình, còn trạng
thái kết thúc ở bên phải hình. Tương ứng với các quy tắc chuyển dịch các quân, ta có
bốn phép chuyển: up (đẩy quân lên
↑
), down (đẩy quân xuống
↓

theo cây) sẽ cần một khoảng thời gian đáng kể cho các ví dụ nhỏ. Sau đây ta sẽ giới
thiệu một số dạng tìm kiếm không có thông tin tiêu biểu ứng với các cách tổ chức dữ
liệu.
1.2.1.1 Tìm kiếm trên danh sách
Các giải thuật tìm kiếm trên danh sách là loại giải thuật tìm kiếm cơ bản nhất.
Mục đích là tìm trong một tập hợp một phần tử chứa một khóa nào đó. Các giải thuật
tìm kiếm tiêu biểu nhất trên danh sách là: Tìm kiếm tuần tự (hay tìm kiếm tuyến
tính), tìm kiếm nhị phân.
Tìm kiếm tuần tự kiểm tra từng phần tử trong danh sách theo thứ tự của danh
sách đó. Nó có thời gian chạy khá lớn: O(n), trong đó n là số phần tử trong danh sách,
nhưng có thể sử dụng cho một danh sách bất kỳ mà không cần tiền xử lý.
Tìm kiếm nhị phân là một thuật toán cao cấp hơn so với thuật toán tìm kiếm
tuần tự với thời gian chạy là O(log n). Đối với các danh sách lớn, thuật toán này tốt
hơn hẳn tìm kiếm tuyến tính nhưng nó đòi hỏi danh sách phải được sắp xếp từ trước
và đòi hỏi khả năng truy cập ngẫu nhiên. Thuật toán tìm kiếm nội suy tốt hơn so với
thuật toán tìm kiếm nhị phân đối với danh sách rất lớn và với phân bố gần đều.
Ngoài ra bảng băm (hash table) cũng được dùng cho tìm kiếm trên danh sách.
Nó đòi hỏi thời gian hằng số trong trường hợp trung bình, nhưng lại cần nhiều chi phí
về không gian bộ nhớ và thời gian chạy O(n) cho trường hợp xấu nhất. Một phương
pháp tìm kiếm khác dựa trên các cấu trúc dữ liệu chuyên biệt sử dụng cây tìm kiếm
nhị phân cân bằng (self-balancing binary search tree) và đòi hỏi thời gian chạy O(log
13
n). Các giải thuật loại này có thể coi là mở rộng của tư tưởng chính về tìm kiếm nhị
phân để cho phép chèn và xóa nhanh.
1.2.1.2 Tìm kiếm trên cây
Tìm kiếm trên cây là trung tâm của các kỹ thuật tìm kiếm. Các thuật toán này
tìm kiếm trên các cây gồm các nút, cây này có thể là cây tường minh hoặc được xây
dựng dần trong quá trình tìm kiếm.
Nguyên lý cơ bản là: một nút được lấy ra từ một cấu trúc dữ liệu, các nút con
của nó được xem xét và bổ sung vào cấu trúc dữ liệu đó. Bằng cách thao tác trên cấu

có lời giải.
Tìm kiếm chiều sâu và tìm kiếm chiều rộng đều là các phương pháp tìm kiếm
có hệ thống và chắc chắn tìm ra lời giải. Tuy nhiên, do bản chất là vét cạn nên với
những bài toán có không gian lớn thì ta không thể dùng hai chiến lược này được. Hơn
nữa, hai chiến lược này đều có tính chất "mù quáng" vì chúng không chú ý đến
những thông tin (tri thức) ở trạng thái hiện thời và thông tin về đích cần đạt tới cùng
mối quan hệ giữa chúng. Các tri thức này vô cùng quan trọng và rất có ý nghĩa để
thiết kế các giải thuật hiệu quả hơn. Do đó hai chiến lược trên được cải tiến thành
một số thuật toán tìm kiếm mới trên cây bao gồm: tìm kiếm lặp sâu dần, tìm kiếm
chiều sâu giới hạn, tìm kiếm hai chiều và tìm kiếm chi phí đều [7].
1.2.1.3 Tìm kiếm trên đồ thị
Nhiều dạng bài toán tìm kiếm cụ thể trên đồ thị như: Tìm đường đi ngắn nhất,
tìm cây bao trùm nhỏ nhất, tìm bao đóng bắc cầu,…Tuy nhiên ứng với mỗi dạng bài
toán có một số giải thuật tìm kiếm thích hợp để giải quyết. Chẳng hạn thuật toán
Dijkstra, thuật toán Kruskal, giải thuật láng giềng gần nhất và giải thuật Prim
[3]. Các thuật toán này có thể được coi là các mở rộng của các thuật toán tìm kiếm
trên cây: tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng.
Thuật toán Dijkstra là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn
đơn trong một đồ thị có hướng không có cạnh mang trọng số âm. Thuật toán này có
thể tính toán tất cả các đường đi ngắn nhất từ một đỉnh xuất phát cho trước s tới mọi
đỉnh khác mà không làm tăng thời gian chạy.
Thuật toán Kruskal là thuật toán xây dựng cây bao trùm ngắn nhất bằng cách chọn
thêm dần các cung vào cây.
Thuật toán Prim: là thuật toán nhằm xây dựng cây bao trùm ngắn nhất. Tư tưởng
của thuật giải Prim là chọn đưa dần vào cây T các đỉnh kề “tốt nhất” trong số các
đỉnh còn lại. Thời gian thực hiện giải thuật Prim là O(n
2
).
15
1.2.2 Tìm kiếm có thông tin

ở mức tiếp theo, còn trong tìm kiếm tốt nhất - đầu tiên ta chọn đỉnh để phát triển là
đỉnh tốt nhất được xác định bởi hàm đánh giá (tức là đỉnh có giá trị hàm đánh giá là
nhỏ nhất), đỉnh này có thể ở mức hiện tại hoặc ở các mức trên.
Thuật toán tìm kiếm leo đồi: thực chất là thuật toán tìm kiếm theo chiều sâu
được hướng dẫn bởi hàm đánh giá. Song khác với tìm kiếm theo chiều sâu, khi ta
phát triển một đỉnh u thì bước tiếp theo, ta chọn trong số các đỉnh con của u đỉnh có
nhiều hứa hẹn nhất để phát triển, đỉnh này cũng được xác định bởi hàm đánh giá.
1.2.3 Tìm kiếm đối kháng
Tìm kiếm đối kháng còn gọi là tìm kiếm có đối thủ là chiến lược tìm kiếm
được áp dụng để tìm ra nước đi cho người chơi trong các trò chơi đối kháng. Chơi cờ
có thể xem như vấn đề tìm kiếm trong không gian trạng thái. Sau đây chúng ta sẽ
xem thế nào trò chơi đối kháng và chiến lược tìm kiếm nào sẽ được áp dụng.
1.2.3.1 Trò chơi đối kháng
Trong 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), có một cây trò chơi bao gồm tất cả các nước đi có thể của cả hai đấu thủ
và các cấu hình bàn cờ là kết quả của các nước đi đó. Ta có thể tìm kiếm trên cây này
để có được một chiến lược chơi hiệu quả. Các trò chơi 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ủ. Trong trò chơi này phải tính đến mọi nước đi mà đối thủ của ta có thể sử dụng.
Đặ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.
17
Thông thường các trò chơi này hay được gọi là các loại cờ, đôi khi còn được gọi 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). Thuật toán áp dụng cho dạng bài toán này là thuật toán tìm kiếm Minimax ta
sẽ trình bày chi tiết trong chương 2.

tiếc rằng, cách làm này lại không thể thực hiện được do có hiện tượng 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 = b
2
. Cứ như vậy ở độ sâu d sẽ có b
d
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 16
100
hay xấp xỉ 10
120
- một con số quá
lớ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.
Th
ời
gi
an
Số đỉnh
Hàm mũ
b

2.1 Giới thiệu
Thuật toán Minimax là thuật toán tìm kiếm chuyên dùng để trả về chuỗi nước
đi tối ưu cho một người chơi trong trò chơi có tổng bằng không [8]. Minimax (còn
gọi là minmax) là một phương pháp trong lý thuyết quyết định có mục đích là tối
thiểu hóa (minimize) tổn thất vốn được dự tính có thể là tối đa (maximize). Có thể
hiểu ngược lại là, nó nhằm tối đa hóa lợi ích vốn được dự tính là tối thiểu (maximin).
Thuật toán này cũng được mở rộng cho nhiều trò chơi phức tạp hơn và giúp đưa ra
các quyết định chung khi có sự hiện diện của sự không chắc chắn.
Một phiên bản của giải thuật áp dụng cho các trò chơi như tic-tac-toe, khi mà
mỗi người chơi có thể thắng, thua, hoặc hòa. Nếu người chơi A có thể thắng trong
một nước đi, thì "nước đi tốt nhất" chính là nước đi để dẫn đến kết quả thắng đó. Nếu
người B biết rằng có một nước đi mà dẫn đến tình huống người A có thể thắng ngay
ở nước đi tiếp theo, trong khi nước đi khác thì sẽ dẫn đến tình huống mà người chơi
A chỉ có thể tốt nhất là hòa thì nước đi tốt nhất của người B chính là nước đi sau.
Ta sẽ nắm rõ, thế nào là một nước đi "tốt nhất". Giải thuật Minimax giúp tìm
ra nước đi tốt nhất, bằng cách đi ngược từ cuối trò chơi trở về đầu. Tại mỗi bước, nó
sẽ ước định rằng người A đang cố gắng tối đa hóa cơ hội thắng của A khi đến phiên
anh ta, còn ở nước đi kế tiếp thì người chơi B cố gắng để tổi thiểu hóa cơ hội thắng
của người A (nghĩa là tối đa hóa cơ hội thắng của B).
Lý thuyết trò chơi coi trò chơi là sự kết hợp hoặc trao đổi giữa hai hay nhiều
đối thủ ở đó mỗi đối thủ cố gắng lựa chọn tối ưu hành động (hay nước đi) của mình
nhằm đạt được lợi ích tối đa. Trong lý thuyết trò chơi có một cách phân loại các trò
chơi thành hai loại: trò chơi có tổng bằng không và trò chơi có tổng khác không.
Trong những trò chơi có tổng khác không, lợi ích thu được của người chơi này
không nhất thiết dẫn tới sự mất mát của người chơi kia. Các tình huống này tồn tại
với điều kiện tổng kết quả (mà người thắng được hưởng) không bị giới hạn hay cố
21
định. Về bản chất đây là trường hợp kiến tạo kết quả thay vì chia sẻ kết quả giữa các
đối thủ. Chẳng hạn như khi nghe hoà nhạc, người ta không phải thích một bản hoà
tấu vì người khác không thích nghe. Việc ai đó không thích nghe chẳng có ảnh hưởng

,…, a
m
},
P
2
có một tập n chiến lược thuần túy B={b
1
, b
2
, …, b
n
}.
1. Mỗi người chơi sẽ được lợi với mỗi cặp (a
i
, b
j
) của chiến lược. Lợi nhuận của P
1
ký hiệu là U
1
(a
i
, b
j
) và lợi nhuận của P
2
ký hiệu là U
2
(a
i

và việc chơi mỗi chiến lược thuần túy với một xác suất cố định. Ký hiệu p
i
là xác suất
mà người chơi 1 sẽ chơi a
i
và
j
q
là xác suất mà người chơi 2 chọn b
j
. Vì p và q là xác
suất nên chúng phải thỏa mãn:
(a)
∀
i
i
p
≥
0,
∀
j
j
q

≥
0.
(b)
.q ,p
n
1j

) là xác suất mà b
j
được chơi.
Với mỗi cặp chiến thuật ngẫu nhiên
),( qp
lợi nhuận (kết cục)
),( qpM
được định
nghĩa là:
∑∑
= =
=
m
i
n
j
jjii
qbaMpqpM
1 1
),(),(
Ta ký hiệu lợi nhuận do người chơi 1 dùng chiến lược thuần túy a
i
và người chơi 2
dùng chiến lược hỗn hợp q là:
.),(),
1
(
j
n
j

lược ngẫu nhiên q từ Q sao cho cực đại lợi ích của nó, nghĩa là làm cực tiểu M(p, q).
Các luật chơi yêu cầu mỗi người chơi chọn chiến lược của mình một cách hoàn hảo
bỏ qua sự lựa chọn của đối thủ.
5. Mỗi chiến lược hỗn hợp p thuộc P, mức độ đảm bảo của người chơi 1 được định
nghĩa là:
v
1
(p)=
),(min qpM
q
.
Bởi vì
∑
=
=
n
j
jj
qbpMqpM
1
),(),(
là tổng trọng số của n lợi ích M(p,b
j
), giá trị M( p,q)
này đạt cực tiểu khi tất cả các giá trị M(p,b
j
) được gán bằng giá trị nhỏ nhất của
chúng, ta ký hiệu giá trị nhỏ nhất này là v
1
(p) và được xác định như sau:

sao cho:
v
1
(p
*
)
≥
v
1
(p)
∀
p
∈
P.
Ký hiệu v
1
là mức độ đảm bảo cực đại thì
v
1
(p
*
)= v
1
=
)()(max
11
pvpv
p
≥
(1)

*
được gọi là chiến lược Maximin.
Sự tổn thất cực tiểu
6. Bởi vì trò chơi có tổng bằng không, nên khi người chơi 2 cực đại mức độ đảm
bảo của nó thì lợi nhuận của người chơi 1 sẽ đạt cực tiểu. Nếu người chơi 2 dùng
chiến lược q thì người chơi 1 không thể nhận được một giá trị lớn hơn.
v
2
(q)=
).,(max qpM
p
Giá trị v
2
đôi lúc được gọi là tổn thất. Người chơi 1 cố gắng để cực đại mức đảm bảo,
người chơi 2 cố gắng cực tiểu tổn thất. Vì vậy người chơi 2 muốn cực tiểu tổn thất
của nó, thì người chơi 2 phải chọn một chiến lược q
*
sao cho:
v
2
= v
2
(q
*
)
≤
v
2
(q)
∀