TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT
NAM
KHOA CÔNG NGHỆ THÔNG TIN
-----***-----

BÁO CÁO BÀI TẬP LỚN
HỌC PHẦN “TRÍ TUỆ NHÂN TẠO”

Đề tài:
TRỊ CHƠI TIC TAC TOE
GV hướng dẫn:
Sinh viên thực hiện:

Hồ Quang Huy – MSV: 78333
Nguyễn Linh Chi – MSV: 77305


Hải phòng, tháng 11 năm 2020


TRƯỜNG ĐẠI HỌC HÀNG HẢI
KHOA CÔNG NGHỆ THÔNG TIN
-----***-----

BÀI TẬP LỚN
HỌC PHẦN: TRÍ TUỆ NHÂN TẠO

1. Tên đề tài
Trị chơi Tic Tac Toe
2. Mục đích
- Tìm hiểu và xây dựng trị chơi Tic Tac Toe.

3. Cơng việc
- Tìm hiểu về đề tài.
- Tìm hiểu về cây trị chơi và thuật tốn Minimax.
- Viết chương trình cho bài tốn.
- Làm báo cáo bài tập lớn.
4. Yêu cầu
- Làm báo cáo
- Nộp báo cáo

i


Hải Phòng,

tháng 10 năm 2019

NGƯỜI HƯỚNG DẪN

MỤC LỤ

ii


MỤC LỤC.......................................................................................................iii
DANH MỤC CÁC HÌNH VẼ, BẢNG BIỂU...............................................iv
DANH MỤC CÁC TỪ VIẾT TẮT................................................................v
MỞ ĐẦU..........................................................................................................1
CHƯƠNG 1: GIỚI THIỆU BÀI TỐN........................................................2
1.1.


Mơ tả bài toán.......................................................................................................................2

1.2.

Mụ c têu................................................................................................................................3

1.3.

Hướng giải quyêết bài toán.....................................................................................................3

CHƯƠNG 2: CƠ SỞ LÝ THUYẾT...............................................................4
2.1.

Cây trị chơi...........................................................................................................................4

2.2.

Thuật tốn Minimax..............................................................................................................5

2.3.

Mơ phỏng giải thuật Minimax cho trò ch ơi Tic Tac Toe .........................................................6

2.4.

Đánh giá thuật tốn...............................................................................................................8

2.5.

2.4.1.


Ưu điểm.....................................................................................................................8

2.4.2.

Nhược điểm...............................................................................................................8

Ngơn ngữ lập trình (cơng cụ cài đặt) sử d ụng ........................................................................8

CHƯƠNG 3: CHƯƠNG TRÌNH CÀI ĐẶT BÀI TOÁN.............................9
1.

Code lệnh.................................................................................................................................. 9

2.

Kêết quả....................................................................................................................................18

/>
iii


DANH MỤC CÁC HÌNH VẼ, BẢNG BIỂU
Hình vẽ

Trang

iv



Recommandé pour toi

26

Suite du document ci-dessous

Tổng ôn ngữ pháp tiếng anh Chuyên ĐỀ 16 - LIÊN TỪ
Công nghệ thông tin

18

100% (1)

123doc-imc-plan-cho-thuong-hieu-baemin
Business Leadership

100% (5)


DANH MỤC CÁC TỪ VIẾT TẮT
Từ

Ý nghĩa

v


MỞ ĐẦU
Hiện nay, nền CNTT đang ngày càng phát triển mạnh mẽ với sự phát
triển của KH-CN. Việc ứng dụng trí tuệ nhân tạo trong các ứng dụng hàng

ngày làm cho máy móc biết suy nghĩ hay giải quyết những bài tốn một cách
thơng minh nhất và việc phát triển game đã trở nên vô cùng phổ biến, đặc biệt
là những game mang tính trí tuệ cao. Và Tic Tac Toe là một game như vậy.
Chính vì lý do đó mà chúng em đã quyết định lựa chọn Tic Tac Toe làm
đề tài cho bài tập lớn. Đây là tài liệu dùng để miêu tả một cách cơ bản về việc
xây dựng game Tic Tac Toe. Trong game có sử dụng thuật toán MiniMax với
độ sâu là 4 và thuật tốn cắt cụt alpha-beta để giảm thời gian tính tốn. Tài
liệu này giúp ta có một cái nhìn tổng qt về việc áp dụng thuật toán
MiniMax và cắt cụt alpha-beta vào game cờ Caro.
Do thời gian có hạn nên chúng em chưa thể tối ưu được các thuật toán
sử dụng trong game, nhưng chúng em sẽ cố gắng hoàn thiện trong thời gian
sớm nhất. Nhóm thực hiện đề tài này với mục đích xây dựng game Caro có
tính nhân tạo cao. Tuy nhiên trong q trình thực hiện khơng thể tránh khỏi có
những sai sót, chúng em rất mong nhận được những góp ý và đánh giá của cơ.

1


CHƯƠNG 1: GIỚI THIỆU BÀI TỐN
1.1.

Mơ tả bài tốn

Tic-tac-toe là một dạng đơn giản của trò đánh cờ Caro. Đây trị chơi phổ
biến dùng viết trên bàn cờ giấy có 9 ô, 3x3 gồm hai người chơi, một người
dùng ký hiệu O, người kia dùng ký hiệu X.

Hình 1: Trị chơi Tic Tac Toe

Luật chơi: Hai người chơi lần lượt điền ký hiệu của mình vào một ơ bất kỳ

(ơ đó chưa được đánh) trên bàn cờ. Khi 9 ơ được điền đầy, trò chơi kết thúc ở
1 trong 3 trạng thái:
 Khi có 3 quân thẳng hàng ( ngang, dọc hoặc chéo) liên tiếp
o Người chơi ký hiệu X thắng
o Người chơi ký hiệu O thắng
 Khi khơng có 1 đường thẳng/chéo nào được ghi: 2 người chơi sẽ cùng
hịa

Hình 2: 3 trạng thái kết thúc trị chơi


1.2.
-

Mục tiêu

Đến lượt chơi của mình, người chơi cố gắng tạo ra 3 nước cờ thẳng
hàng thì sẽ chiến thắng.

-

Hoặc cố ngăn cản đối thủ của mình tạo ra 3 nước cờ thẳng hàng.

1.3.

Hướng giải quyết bài toán

* Để giải quyết bài tốn này và tìm ra nước đi tối ưu, chúng ta sẽ sử
dụng thuật tốn Minimax
• Có 2 người chơi là Min và Max.

• MAX: là người chơi cố gắng dành chiến thắng
• MIN: là người chơi ngăn cản điểm số của MAX
 Áp dụng vào game Tic Tac Toe
- Người chơi cầm qn X đóng vai trị như Max
- Người chơi cầm qn O đóng vai trị như Min.
- Để quyết định nước đi tiếp theo, ta xây dựng một thủ tục đệ quy gồm 2
hàm:
max_value() để tìm nước đi tiếp theo cho quân X
min_value() để tìm nước đi tiếp theo cho quân O.

3


CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
2.1.

Cây trò chơi

- Cây trò chơi là 1 sơ đồ hình cây thể hiện các trạng thái hoặc các trường hợp
của trò chơi theo từng nước đi.

Hình 3: Cây trị chơi Tic Tac Toe

- 1 cây trò chơi bao gồm tất cả các nước đi có thể có của 2 người chơi và mỗi
node của cây thể hiện 1 trạng thái bàn cờ sau khi nhận một nước đi từ người
chơi. Từ một node có nhiều lựa chọn cho nước đi tiếp theo.
- TTBĐ là sự sắp xếp các quân cờ trong lúc đầu của cuộc chơi. Trong hình trên
( Hình 3 ) người chơi O chỉ có thể đặt quân cờ đầu tiên vào 3 vị trí. Lượt đi
tiếp theo dành cho người chơi X, tại vị trí thứ nhất có 5 cách đi qn cờ, vị trí
thứ 2 có 2 cách đi qn cờ, vị trí thứ 3 có 5 cách đi qn cờ. Tương tự cho các

lượt đi tiếp theo, số lượt đi tối đa cho cả 2 đối thủ trong trò chơi là 9.
Cách xây dựng cây trò chơi:
4


 Gốc của cây ứng với trạng thái u
 Có thể gọi đỉnh ứng với TT X ( O ) đưa ra nước đi là đỉnh X ( O )
 Nếu 1 đỉnh là X ( O ) ứng với trạng thái u thì đỉnh con của nó là tất cả
các đỉnh biểu diễn trạng thái , v nhận được từ u do X ( O ) thực hiện
nước đi hợp lệ nào đó
2.2.

Thuật tốn Minimax

- Đây là 1 thuật tốn đệ quy được dùng trong tìm kiếm có đối thủ và được sử
dụng làm chiến lược cho tìm kiếm nước đi trong KGTK của trị chơi có tính
chất đối kháng.
Ví dụ: Trong trị chơi đối kháng (cờ Vua, cờ Tướng, cờ Caro,…) khi người
chơi đánh với máy, thì KGTT là cả bàn cờ đó – KGTT là cách mà máy tính
biểu diễn bàn cờ thực hiện lên bộ nhớ máy tính. Với mỗi nước đi, sẽ làm cho
KGTT của bàn cờ thay đổi thành một KGTT mới. Như vậy để tìm ra nước đi
tốt nhất cho máy chiến lược tìm kiếm nước đi Minimax sẽ được sử dụng.
Hàm đánh giá:
- Hàm đánh giá sẽ quyết định chất lượng của một chương trình
- Để thiết kế 1 hàm đánh giá cần phụ thuộc vào các yếu tố: các quân cờ
của 2 bên, số lượng quân cờ còn lại, sự sắp xếp các quân cờ,…
Eval(u) = (Rows, Columns, Diagonal còn mở đối với MAX)
= (Rows, Columns, Diagonal còn mở đối với MIN)

5



2.3.

Mơ phỏng giải thuật Minimax cho trị chơi Tic Tac Toe

 MAX: người chơi sử dụng ký hiệu O.
 MIN: người chơi sử dụng ký hiệu X.
- Trong trò chơi từ TT hiện tại sẽ dự đoán được nước đi của TT tiếp theo cho
đến khi gặp TT chiến thắng (Node lá). Nếu nó khơng là node lá (trị chơi
chưa kết thúc nhưng vì giới hạn các ơ nên khơng thể tính đến node lá).
TTKT là trạng thái có 3 ô liên tiếp ngang, dọc, chéo có cùng một quân cờ X
hoặc O ( Là X thì MIN win, là O thì MAX win, các ơ đều kín và TT chưa
kết thúc thì 2 bên hịa )
- Ta chỉ tính giá trị của các node ở mức cao nhất được giới hạn. Các node ở
mức trước được tính dựa trên các node con của nó. Node đó đang là MAX
thì giá trị của nó sẽ là giá trị của node lớn nhất trong tất cả các node con của
nó. Node đó đang là MIN thì giá trị của nó sẽ là giá trị của node nhỏ nhất
trong các node con của nó. Mỗi node MAX hoặc MIN sẽ chọn node con có
giá trị bằng nó để làm nước đi tối ưu.

6


7


2.4.

Đánh giá thuật tốn


2.4.1. Ưu điểm

- Thuật tốn giúp tìm kiếm tất cả nước đi tiếp theo sau và lựa chọn nước đi
tốt nhất
2.4.2. Nhược điểm

- Tốn thời gian ( vì phải duyệt hết tất cả các trạng thái)
2.5.

Ngơn ngữ lập trình (cơng cụ cài đặt) sử dụng

Trị chơi Tic Tac Toe được viết bằng: Ngôn ngữ : C#
IDE : Visual Studio Code

8


CHƯƠNG 3: CHƯƠNG TRÌNH CÀI ĐẶT BÀI TỐN
1. Code lệnh
using System;
using System.Collections.Generic;

using System.Linq;
using System.Text;

using System.Threading.Tasks;

namespace AI_tick_tac_toe


{

public class player
{
public string huPlayer = "O";

public string aiPlayer = "X";

9


public Listnew List<int>(){0, 1, 2},

new List<int>(){3, 4, 5},
new List<int>(){6, 7, 8},
new List<int>(){0, 3, 6},

new List<int>(){1, 4, 7},
new List<int>(){0, 4, 8},

new List<int>(){6, 4, 2},
new List<int>(){2, 5, 8},

};
}
}

//

using System;

10


using System.Collections.Generic;
using System.Linq;

using System.Text;
using System.Threading.Tasks;
using System.Windows;

using System.Windows.Controls;
using System.Windows.Data;

using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;

using System.Windows.Media.Imaging;
using System.Windows.Navigation;

using System.Windows.Shapes;

namespace AI_tick_tac_toe

11


{

/// <summary>

/// Interaction logic for MainWindow.xaml
/// </summary>
public partial class MainWindow : Window

{
List<Button> matrix = new List<Button>();

player Player = new player();
int index=0;
bool isOver = false;

public MainWindow()

{
InitializeComponent();
StartGame();

12


}
private void StartGame()

{
isOver = false;
matrix.Clear();

InitializeBoard();

AddToBoard();

}
private void AddToBoard()
{

board.Children.Clear();

for (int i = 0; i < 9; i++)

{
board.Children.Add(matrix[i]);

13


}

}
private void InitializeBoard()
{

for (int i = 0; i < 9; i++)
{

Button btn = new Button()
{
Name = "dfdf",

FontSize = 120,

Width = 140,

Height = 140,
Content = "",
Tag = i,

14


};
btn.Click += Btn_Click;

matrix.Add(btn);
}
}

private void Btn_Click(object sender, RoutedEventArgs e)

{
Button btn = sender as Button;
if (btn.Content.ToString() == "") // cho khoong click vao lan 2

{
int id = Int32.Parse(btn.Tag.ToString());

turn(id, Player.huPlayer);
if (!checkTie() && isOver == false) turn(bestSpot(), Player.aiPlayer);
}

15

}
public int bestMove = 1;

public int go = 1;

private int bestSpot()

{
minimax(Player.aiPlayer);

return go;
}

private int minimax(string player)
{
List<int> availSpots = emptyRoom();

16


if (checkWin(Player.huPlayer))
{ return -10;

}
else if (checkWin(Player.aiPlayer))
{

return 10;

}

else if (availSpots == null) return 0;

List<Move> moves = new List<Move>();

for (int i = 0; i < availSpots.Count; i++)

{
Move move = new Move();

17