Báo cáo bài tập lớn môn Trí tuệ nhân
tạo
Đề tài: “ Tìm hiểu về thuật toán Minimax “
GVHD : T.S Nguyễn Thị Thủy
Sinh viên thực hiện :
Bùi Thành Nam . Msv: 522977
Phan Thị Chương. Msv: 522931
Nguyễn Hồng Linh. Msv:522968
Nguyễn Thị Xuân Mai
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 1
Mục Lục
Báo cáo bài tập lớn môn Trí tuệ nhân tạo 1
Đề tài: “ Tìm hiểu về thuật toán Minimax “ 1
Mục Lục 2
A.Thuật toán Minimax 3
I.Thuật toán minimax 3
II.Thuật toán cắt Alpha-beta
5
B.Trò chơi tíc tắc toe 10
I.Giới thiệu trò chơi 10
II.Mục tiêu trò chơi 10
III.Hướng giải quyết 10
V.Giới thiệu chương trình 17
1.Giao diện chính của chương trình 17
C.Tài liệu tham khảo 21
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 2
A. Thuật toán Minimax
I. Thuật toán minimax
Thuật toán minimax chứa đựng tất cả các khả năng của việc chuyển
đổi các trạng thái từ 1 trạng thái được đưa ra và từ đó bao phủ lên các
khoảng trống .

người chơi có thể chọn di chuyển tốt hơn đến lượt mình. Các tính toán quá
trình trong một trò chơi Minimax được minh họa dưới đây fig. 4,12 (b).
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 4
Hàm Minnimax
1.mở rộng toàn bộ các không gian trống sau các nút
2. gán các giá trị {+1,0,-1} tùy thuộc vào các bước đi của MAXIMIZER hay
của MINIMIZER tương ứng
3. đối với mỗi node con tương ứng đó thì làm
Begin
Nếu đó là nút của MAXIMIZER , thì giá trị của nó sẽ là giá trị cực đại
trong các giá trị ; Nếu đó là nút của MINIMIZER ,thì giá trị của nó sẽ là
giá trị cực tiểu trong các giá trị
End For;
End.
II. Thuật toán cắt Alpha-beta
Thuật toán Minimax đã được nói ở trên yêu cầu mở rộng tới toàn bộ
khoảng không gian trống . Đây là 1 hạn chế nghiêm trọng , đặc biệt với vấn
đề mở rộng khoảng trống . Để giải quyết khó khăn này một cách giải quyết
là dung đánh giá heuristic tình trạng bước đi tiếp theo của người chơi để
chọn một bước đi hiện tại cho cùng 1 người chơi.Chúng ta sẽ minh họa quá
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 5
trình tính toán của các biện pháp heuristic của một nút dưới đây với sự nổi
tiếng trò chơi TIC TAC TOE
Xét 1 hàm heuristic e(n) [3], [5] tại nút n đánh giá sự khác biệt của các dòng
có thể giành chiến thắng của mỗi người chơi
e(n) =M(O)- O(n)
trong đó M (n) = số dòng của tôi có thể giành chiến thắng
và O (n) = số dòng giành chiến thắng của đối thủ.
Ví dụ, trong fig. 4,13 M (n) = 6, O (n) = 5 và vì thế e (n) = 1.
Bây giờ, chúng tôi sẽ thảo luận về một loại mới của thuật toán, mà không

lên đến độ sâu (d + 2).
ii) Tính e (n) cho tất cả để lại (rìa) các nút n trong cây.
iii) Tính α '
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 7
min (cho các nút tối đa) và β '
tối đa các giá trị (đối với các nút min) tại
tổ tiên của các nút rìa bởi các nguyên tắc sau đây.
Ước tính tối thiểu của các giá trị (e hoặc α) sở hữu do
β của trẻ em của một nút MINIMIZER N và gán nó '
tối đa giá trị.
Tương tự như vậy, ước tính tối đa của các giá trị (e hoặc β) sở hữu
do con của một nút Maximizer N và gán nó giá trị αmin .
Fig. 4.15: Những cách nghĩ để có thể di chuyển thay thế F và cũng tự sinh ra
ở lớp tiếp theo là G e(G)=-1, β max ở F =-1, , β max ở F nhỏ hơn so với α
min ở A
Như vậy ko có nhu cầu tìm kiếm dưới F, G có thể bớt không gian tìm kiếm
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 8
Fig. 4.16:
Nút G đã bị cắt tỉa , các nút C, D và E được mở rộng e(n ) được thiết lập ở n
= H , I , J và K và giá trị của αmin được ước lượng tại các nút C, D, E.Bởi
vì giá tri αmin ở C lớn hơn giá trị βmax ở B, giá tri αmin ở D bằng giá trị
βmax ở B, ở đó ko cần tìm kiếm dưới nút C và D
IV) Nếu các nút của MAXIMIZER có các giá trị αmin. Sau đó giá trị αmin =
MAX(αmin). Một mặt khác nếu các nút của MINIMIZER có giá trị βmax và
sau đó βmax = MAX(βmax)
V) Nếu thiết lập giá trị βmax ở nút MINIMIZER tại N nhỏ hơn αmin của nút
cha MAXIMIZER tại N’ thì sau đó ko cần tìm kiếm dưới nút N. Tương tự
Nếu thiết lập giá trị αmin ở nút MAXIMIZER tại N nhỏ hơn αmin của nút
cha MINIMIZER tại N’ thì sau đó ko cần tìm kiếm dưới nút N
Những bước ở trên được thực hiện cho đến khi nào trò chơi kết thúc

nhất mà đối thủ này có thể đạt được . Các giá trị này sẽ được dùng để lựa
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 10
chọn các bước đi có thể có. Kết quả của việc áp dụng Minnimax vào đồ thị
không gian trạng thái đối với trò chơi Nim được thể hiện như hình trên. Vì
tất cả các nước đi đầu tiên có thể sảy ra cho MIN sẽ dần đến giá trị 1 nên đối
thủ MAX luôn có thể bắt trò chơi giành thắng lợi cho mình bất kể nước đi
đầu tiên của MIN như nào
IV. Thuật toán
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 11
using System;
using System.Collections.Generic;
using System.Text;
public enum GameState
{
InProgress,
ComputerWins,
HumanWins,
Draw
}
class Board
{
#region Declare field and delegate
public static readonly int Empty = 0;
public static readonly int X = -1;
public static readonly int O = 1;
public GameState BoardState; //represents
the state of the game
public int iBoardSize; //Size of
board in one dimension
public int iEmptySquares; //Count of unplayed

int i, j;
for (i = 0; i < this.iBoardSize; i++)
{
for (j = 0; j < this.iBoardSize; j++)
{
this.aiBoard[i, j] = board.aiBoard[i,
j];
}
}
}

//
// Apply a move
//
public void MakeMove(int CurrentPlayer, Move move)
{
aiBoard[move.iCol, move.iRow] =
CurrentPlayer;

//Check for draw condition
iEmptySquares ;
if (iEmptySquares == 0)
this.BoardState = GameState.Draw;
}

//
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 13
// Checks the board for a winner and reassigns
// this.BoardState as appropriate.
//

{
iTotal += aiBoard[i, j];
}
if (iTotal == -iBoardSize)
{
this.BoardState =
GameState.ComputerWins;
return;
}
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 14
if (iTotal == iBoardSize)
{
this.BoardState = GameState.HumanWins;
return;
}
}
//Check Top-Left to Bottom-Right diagonal
iTotal = 0;
for (i = 0; i < iBoardSize; i++)
{
iTotal += aiBoard[i, i];
}
if (iTotal == -iBoardSize)
{
this.BoardState = GameState.ComputerWins;
return;
}
if (iTotal == iBoardSize)
{
this.BoardState = GameState.HumanWins;

3. Kết quả của trò chơi
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 19
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 20
C. Tài liệu tham khảo
Artificial Inteligence and Soft Computing - Amit Konar
http://codeprovn.com
http://ddth.com/
http://www.manguon.com/
Khoa công nghệ thông tin trường đại học Công Nghiệp Hà Nội Page 21