9
Xây dựng game cùng với AI
Trong chương này chúng ta học cách xây dựng một game cùng với Artificial Intelligence. Chúng ta sẽ học cách sử dụng thuật toán tìm kiếm để đưa ra các chiến lược hiệu quả để thắng trò chơi. Chúng ta sẽ sử dụng những thuật toán đó để xây dựng một con bot cho những game khác nhau.
Nội dung chính trong chương này:
Sử dụng thuật toán tìm kiếm trong Games
Thuật toán tìm kiếm được sử dụng trong game để tìm ra một chiến lược. Thuật toán sẽ tìm kiếm tất cả các khả năng và chọn ra hướng đi tốt nhất. Có những tham số khác nhau như – tốc độ, độ chính xác, độ phức tạp, và những thứ tương tự vậy. Những thuật toán sẽ xem xét tất cả các hành động có khả năng trong cùng một thời điểm và sau đó sẽ đánh giá các khả năng di chuyển dựa trên những lựa chọn. Mục đích của tất cả những thuật toán này là tìm những bộ phương pháp tối ưu để di chuyển sẽ giúp nhân vật đến được trạng thái cuối cùng. Mỗi game khác nhau đều có một điều kiện để chiến thắng khác nhau. Những thuật toán sử dụng những điều kiện này để tìm ra các bước di chuyển chính xác nhất.
Những mô tả bên trên là lý tưởng nếu không có người chơi đối đầu. Mọi thứ không đơn giản nếu trò chơi có nhiều người chư. Hãy thử xem xét một trò chơi có 2 người chơi. Vỡi mỗi lần di chuyển bởi một người chơi, đối thủ sẽ tạo một hướng đi đối nghich để chống lại người kia đến được đích. Vì thế khi một thuật toán tìm kiếm tìm được đường đi tốt nhất cho tình trạng hiện tại thì sau bước đi đó lại không còn đúng nữa bởi vì đối thủ đã chặn đứng nó. Về cơ bản nghĩa là thuật toán tìm kiếm cần phải làm việc liên tục sau mỗi bước đi.
Hãy thảo luận về về cách một chiếc máy tính nhìn nhận mỗi game thế nào. Chúng ta có thể nghĩ mỗi game là một cây tìm kiếm. Tại mỗi node trên cái cây là một trạng thái gặp phải trong tương lai. Ví dụ bạn đang chơi game Tic-Tac-Toe, bạn có thể xây dựng cái cây này dựa trên tất cả các bước đi có thể. Chúng ta bắt đầu từ gốc của cây, đây là điểm bắt đầu của Game. Tại điểm này chúng ta có một vài điểm con là các bước đi có thể. Những ddiemr con này sau mỗi lượt lại có thêm vài điểm con là những trạng thái của game sau khi đã có vài bước di chuyển tiếp theo. Những điểm cuối cùng của cây đại diện cho kết quả cuối cùng của game sau khi đã thực hiện các bước di chuyển. Game có thể kết thúc với kết quả hòa hoặc một người chơi nào đó chiến thắng. Những thuật toán tìm kiếm thông qua cái cây này để quyết định mỗi bước đi của game.
Tổ hợp tìm kiếm (Combinatorial Search)
Những thuật toán tìm kiếm xuất hiện để giải quyết vấn đề về thêm sự thông minh cho game, Nhưng nó có một hạn chế. Những thuật toán sử dụng một dạng tìm kiếm được gọi là tìm kiếm tổng quát. Nó cũng được biết đến như là tìm kiếm bắt buộc (brute force search). Cơ bản là nó sẽ khám phá toàn bộ không gian tìm kiếm và kiểm tra tất cả khả năng có thể. Nghĩa là trong trường hợp tồi tệ nhất chúng ta phải đi lòng vòng khắp nơi trước khi chúng ta tìm được hướng đi đúng.
Trong những game phức tạp, chúng ta không thể bỏ mặc nó muốn tìm gì thì tìm vì số lượng hướng đi nó tìm ra sẽ là ác mộng. Để giải quyết ván đề này chúng ta phải dùng tổ hợp tìm kiếm (combinatorial search) để giairquyeets vấn đề. Đây là một lĩnh vực nghiên cứu nơi các thuật toán tìm kiếm khám phá tất cả các không gian giải pháp sử dụng phương pháp phỏng đoán (heuristic) hoặc đơn giản là giảm kích cỡ không gian tìm kiếm. Nó rất hữu dụng trong games như Chess or go. Tổ hợp tìm kiếm làm việc hiệu quả bằng cách sử dụng các chiến lược cắt tỉa cây tìm kiếm. Những chiến lược này giúp nó tránh thử nghiệm tất cả các khả năng có thể bằng cách loại bỏ những nhánh chắc chắn sai, nó giúp tiết kiệm thời gian và công sức.
Thuật toán Minimax
Giờ chúng ta thảo luận tóm tắt về tổ hợp tìm kiếm, Hãy nói về hàm lượng giá (heuristic)được sử dụng bởi thuật toán tổ hợp tìm kiếm. Những hàm lượng giá (heuristic) được sử dụng để tăng tông những chiến lược tìm kiếm và thuật toán Minimax là một trong những chiến lược được dùng bởi tổ hợp tìm kiếm. Khi 2 người chơi đối đầu với nhau trong một game, họ sẽ ngăn cản đối thủ đến được đích trước. Vì thế mỗi bên cần dự đoán xem đối thủ sẽ làm gì để thắng game. Dựa trên những điều này Minimax cố gắng giảm thiểu (minimize) khả năng đối thủ đạt được khả năng tối đa(maximize). Hai đối thủ trong trò này được gọi là Min và Max đi theo lượt. Max thể hiện là người quyeests dành thắng lợi và cố gắng tối đa hóa ưu thế của mình, Min là người cố gắng làm giảm điểm số của Max và cố làm cho điểm số của mình theo chiều âm.
Như chúng ta đã biết tìm kiếm tất cả khả năng(burte forcing the solutions) không phải là một lựa chọn tối ưu. Máy tính không thể thử tất cả các trạng thái có thể và đưa ra bước đi tốt nhất để thắng game. Myas tính chỉ có thể tối ưu những bước ddi dựa trên trạng thái cụ thể của trò chơi dựa trên một phỏng đoán (heuristic). Máy tính sẽ xây dựng một cây và bắt đầu từ gốc(Max) và nhánh tiếp theo sẽ là Min. Nó đánh giá bước đi nào sẽ có lợi cho đối thủ của nó. Cơ bản nó biết bước đi nào đối thủ sẽ đi dựa vào việc bước đi đó sẽ tốt nhất cho họ, và do đó nó sẽ ít có lợi hơn. Kết quả này là điểm cuối cùng của cây và máy tính sẽ dùng vị trí này để tính ngược lại.
Giải thuật cắt tỉa Alpha-Beta
Giải thuật tìm kiếm Minimax là một chiến lược hiệu quả. Nhưng nó vẫn tìm kiếm tất cả các phần của cây và sẽ có những trường hợp không liên quan gặp phải. Hãy xem xét một cái cây nơi chúng ta tìm kiếm các giải pháp. Mỗi lần chúng ta tìm được một chỉ số tại một node trên cây và tại node này sẽ cho chúng ta biết giải pháp sẽ không tồn tại ở node con của nó và chúng ta không cần phải xem xét node con. Nhưng giải thuật Minimax thì vẫn tìm kiếm giải pháp ở node con. Vì thế nên chúng ta cần trách tìm kiếm tại các phần của cây mà không cần thiết tìm kiếm. Quá trình xử lý này được gọi là cắt tỉa (pruning) và cắt tỉa Alpha-Beta là một dạng chiến lược tránh tìm kiếm những phần của cây không chứa giải pháp.
Tham số Alpha và Beta trong giải thuật cắt tỉa alpha-beta là hai giới hạn được sử dụng trong quá trình tính toán. Những tham số này là những giá trị sẽ từ chối những giải pháp không cần thiết. Nó dựa trên những phần của cây đã được khám phá. Alpha là giới hạn dưới tối đa (< maximum) của số lượng các giải pháp có thể và Beta là giới hạn trên tối thiểu (> min) của các số lượng giải pháp cố thể.
Như chúng ta đã nói ở trên mỗi node có thể chứa một giá trị dựa trên trạng thái hiện tại của game. Khi thuật toán xem xét một node mới tiềm năng của giải pháp, nó có thể là khả thi nếu giái trị của node đó nằm trong vùng an toàn beta<node<alpha. Đó là cách làm việc của cắt tỉa.
Thuật toán Negamax
Thuật toán Negamax là một biến thể của giải thuật Minimax, nó thường được dùng trong thực tế. Một game 2 người chơi thường là một trò có tổng bằng không, nghĩa là lợi ích của người này là thiệt hại của người kia và ngược lại. Negamax sử dụng điều này và mở rộng một cách chuyên sâu để đưa ra một chiến lược tăng cô hội chiến thắng game.
Về mặt game, giá trị của một vị trí nhất định cho người chơi thứ 1 là sự phủ định (negation) của người chơi thứ 2. Mỗi người chơi tìm kiếm bước di chuyển sẽ làm đối thủ mất nhiều điểm nhất. Giá trị cuối cùng từ những bước đi phải làm sao cho đối thủ có giá trị nhỏ nhất. Đây là các nó có tính ưu việt hơn thuật toán Minimax về sự đơn giản. Minimax yêu cầu người chơi đầu tiên chọn một bước đi có giá trị lớn nhất(maximum), và người chơi thứ hai phải chọn bước đi với giá trị nhỏ nhất (minimum). Thuật toán cắt tỉa Alpha-Beta cũng sử dụng giải pháp này.
Xây dựng một con bot để chơi game Last Coin Stand
Đây là một game bắt đầu với 1 đống coin và mỗi người chơi sẽ lấy một số coin từ đống này. Có giá trị giới hạn thấp nhất và cao nhất số lượn coin mà mỗi người lấy từ đống coin. Người lấy những đồng coin cuối cùng trong đống coin đó là người thua. Đây là một biến thể của game Game of Bones trong thư viện easyAI.
Để cài thư viện easyAI các bạn xem lại bài trước về cách install thư viện cho Python với địa chỉ github của easyAI là : https://github.com/Zulko/easyAI
Tạo file Python sau khi đã install easyAI
from easyAI import TwoPlayersGame,id_solve,Human_Player,AI_Player
from easyAI.AI import TT
#Tạo một class ddeer quản lý các phép toán trong game. Chúng sẽ thừa kế từ class TwoPlayerGame trong thư viện eassyAI. Chúng có 2 tham số được định nghĩa
# Tham số thứ 1 là player chúng ta sẽ nói về giá trị của object player sau
class LastCoinStand(TwoPlayersGame):
def __init__(self,players):
#Tạo tham số player. đây là tham số bắt buộc
self.players=players
# Để định nghĩa ai là người bắt đầu trò chơi thì số người chơi bắt đầu từ 1. nên người bắt đầu trò chơi sẽ là 1
self.nplayer=1
# tạo số lượng coin để chơi. Bạn có thể chọn tùy ý ở đây tôi chọn 27
self.num_coin=27
# Tạo số coin lớn nhất có thể lấy đi trong mỗi bước đi. có thể chọn tùy ý và tôi chọn là 4
self.max_coin=13
# tạo số nước đi có thể. trong trường hợp này người chơi có thể lấy đi 1,2,3,4 coin trong mỗi nước đi
def possible_moves(self):
return [str(x) for x in range(1,self.max_coin+1)]
# Tạo một hàm để loại bỏ số coin đã được lấy và tính số lượng coin còn lại trong đống coin
def make_move(self,move):
self.num_coin-=int(move)
# Kiểm tra nếu có người nào đó thắng game bằng cách kiểm tra số lượng coin còn lại
def win(self):
return self.num_coin<=0
# Dừng game nếu có ai đã thắng
def is_over(self):
return self.win()
def scoring(self):
return 100 if self.win() else 0
# Tạo hàm để xem trạng thái hiện tại của đống coin:
def show(self):
print('Số lượng coin còn lại là: ',self.num_coin)
#Tạo hàm main và khởi tạo bảng chuyển vị TT (transposition table). TT được sử dụng trong game để lưu trữ vị trí và bước đi để tăng tốc cho thuật toán
if __name__=="__main__":
tt=TT()
#Tạo hàm ttentry để lấy số lượng coin. Đây là một hàm tùy chọn được sử dụng để tạo chuỗi diễn tả tình trạng game
LastCoinStand.ttentry=lambda self:self.num_coin
# Giải quyết vấn đề của game này sử dụng AI. hàm id_solve được sử dụng để giải quyết game đã cho bằng cách lặp sâu (iterative deepening). Về cơ bản thì nó xác định ai là người có thể thắng game sử dụng tất cả các trường hợp
# Nó tìm kiếm các câu trả lời giống như là: player 1 có thể thắng bằng cách chơi hoàn hảo không ? Máy tính sẽ luôn thua trước đối thủ ?
# Hàm id_solver khám phá tất cả những lựa chọn khác nhau trong game sử dụng thuật toán Negamax vài lần. Nó luôn luôn bắt đầu tại điểm khởi tạo game và đào sâu liên tục. Nó sẽ làm điều đó cho tới khi điểm số của một người thắng hoặc thua
# Tham số thứ 2 là một list độ sâu mà nó sẽ đào. Trong trường hợp này tôi chọn giá trị từ 2->20
result,depth,move=id_solve(LastCoinStand,range(2,20),win_score=100,scoring=None,tt=tt)
#print(result,depth,move)
# Bắt đầu game
game=LastCoinStand([AI_Player(tt),Human_Player()])
game.play()
Trong trò chơi này người đi trước luôn thắng nên bạn có thay đổi tham số num_coin và max_coin thế nào thì người lấy đồng xu cuối cùng vẫn là bạn:
d:2, a:0, m:1
d:3, a:0, m:1
d:4, a:100, m:12
Số lượng coin còn lại là: 27
Move #1: player 1 plays 12 :
Số lượng coin còn lại là: 15
Player 2 what do you play ? 1
Move #2: player 2 plays 1 :
Số lượng coin còn lại là: 14
Move #3: player 1 plays 13 :
Số lượng coin còn lại là: 1
Player 2 what do you play ? 1
Move #4: player 2 plays 1 :
Số lượng coin còn lại là: 0
Process finished with exit code 0
Đây là game interactive trong terminal nên bạn phải nhập số lượng coin mình muốn lấy sau mỗi lần chơi.
Xây dựng bot để chơi Tic-Tac-Toe (cờ caro)
Tic-Tac-Toe hay chơi cờ caro là một game nổi tiếng từ thới naponeon còn chưa đẻ. Giờ thì chúng ta thử xây dựng một con bot chơi Tic-Tac-Toe dựa trên thư viện easyAI.
from easyAI import TwoPlayersGame,AI_Player,Negamax,SSS
from easyAI.Player import Human_Player
# Tạo class chứa các method thừa kế class TwoPlayerGame và chọn người bắt đầu.
class GameController(TwoPlayersGame):
def __init__(self,players):
self.players=players
self.nplayer=1
# Chúng ta sử dụng một bảng game 3x3 từ một hàng 9
self.board=[0]*9
# Tạo hàm để tính toán tất cả các bước đi có thể:
def possible_moves(self):
return [a+1 for a,b in enumerate(self.board) if b==0]
# Tạo bảng để update lại bảng sau mỗi bước đi
def make_move(self,move):
self.board[int(move)-1]=self.nplayer
# Tạo hàm để xem nếu người nào thua. Chúng ta sẽ kiểm tra xem ai có 3 hàng trước
def loss_condition(self):
possible_combinations=[[1,2,3], [4,5,6], [7,8,9],
[1,4,7], [2,5,8], [3,6,9],
[1,5,9], [3,5,7]]
return any([all([(self.board[i - 1] == self.nopponent) for i in combination]) for combination in possible_combinations])
# Kiểm tra xem game kết thúc chưa sử dụng hàm loss_condition
def is_over(self):
return (self.possible_moves()==[]) or self.loss_condition()
#Tạo hàm để hiển thị quá trình xử lý
def show(self):
print(self.board)
print('\n' + '\n'.join([' '.join([['. ', 'O', 'X'][self.board[3 * j + i]] for i in range(3)]) for j in range(3)]))
#Tính điểm sử dụng hàm loss_condition
def scoring(self):
return -100 if self.loss_condition() else 0
# Bắt đầu với hàm main và sử dụng thuật toán để giải quyết vấn đề.
if __name__=="__main__":
# Thuật toán sử dụng ở đây là Negamax. Chúng ta có thể chỉ định số bước mà thuật toán có thể nghĩ ở đây tôi sử dụng 5
algorithm=Negamax(5)
# hoặc thêm thuật toán nữa để cho 2 con AI đối đầu với nhau xem nếu thông minh hơn thì có chiến thắng ?
# SSS là một thuật toán tìm kiếm không gian trạng thái trên cây với tất cả những nhánh đầu tiên tốt nhất.
algorithm2=SSS(5)
# bắt đầu game
game=GameController([AI_Player(algorithm2),AI_Player(algorithm)])
game.play()
if game.loss_condition():
print("Người thắng: ",game.nopponent)
else:
print("Kết quả: Hòa")
. . .
. . .
. . .
Player 1 what do you play ? 5
Move #1: player 1 plays 5 :
. . .
. O .
. . .
Move #2: player 2 plays 1 :
X . .
. O .
. . .
Player 1 what do you play ? 3
Move #3: player 1 plays 3 :
X . O
. O .
. . .
Move #4: player 2 plays 7 :
X . O
. O .
X . .
Player 1 what do you play ? 4
Move #5: player 1 plays 4 :
X . O
O O .
X . .
Move #6: player 2 plays 6 :
X . O
O O X
X . .
Player 1 what do you play ? 2
Move #7: player 1 plays 2 :
X O O
O O X
X . .
Move #8: player 2 plays 8 :
X O O
O O X
X X .
Player 1 what do you play ? 9
Move #9: player 1 plays 9 :
X O O
O O X
X X O
Xây dựng 2 bot chơi game Connect Four
Connect Four là game 2 người chơi được bán dưới thương hiệu Milton Bradley. về code tương tự như bài trên nên sẽ không giải thích lại nhiều. Luật chơi là thả từng đĩa chồng lên nhau ai có 4 kết nối theo hàng dọc ngang hoặc chéo trước thì thắng kiểu caro. Luật chơi ở đây có thể tìm hiểu thêm trên youtube hoặc wiki với từ khóa connect Four
import numpy as np
from easyAI import TwoPlayersGame, AI_Player, \
Negamax, SSS
class GameController(TwoPlayersGame):
def __init__(self, players, board = None):
# Tạo players
self.players = players
# Tạo board
self.board = board if (board != None) else (
np.array([[0 for i in range(7)] for j in range(6)]))
# Thằng nào đi trước tính từ 1 không phải từ 0 như array
self.nplayer = 1
# Tạo bảng vị trí
self.pos_dir = np.array([[[i, 0], [0, 1]] for i in range(6)] +
[[[0, i], [1, 0]] for i in range(7)] +
[[[i, 0], [1, 1]] for i in range(1, 3)] +
[[[0, i], [1, 1]] for i in range(4)] +
[[[i, 6], [1, -1]] for i in range(1, 3)] +
[[[0, i], [1, -1]] for i in range(3, 7)])
# Những nước đi có thể
def possible_moves(self):
return [i for i in range(7) if (self.board[:, i].min() == 0)]
# tạo nước đi
def make_move(self, column):
line = np.argmin(self.board[:, column] != 0)
self.board[line, column] = self.nplayer
# Biểu diễn trạng thái hiện tại
def show(self):
print('\n' + '\n'.join(
['0 1 2 3 4 5 6', 13 * '-'] +
[' '.join([['.', 'O', 'X'][self.board[5 - j][i]]
for i in range(7)]) for j in range(6)]))
# điều kiện thắng thua
def loss_condition(self):
for pos, direction in self.pos_dir:
streak = 0
while (0 <= pos[0] <= 5) and (0 <= pos[1] <= 6):
if self.board[pos[0], pos[1]] == self.nopponent:
streak += 1
if streak == 4:
return True
else:
streak = 0
pos = pos + direction
return False
# Kiểm tra game hết chưa
def is_over(self):
return (self.board.min() > 0) or self.loss_condition()
# Tính điểm
def scoring(self):
return -100 if self.loss_condition() else 0
if __name__ == '__main__':
# Tạo thuật toán Negamax cho thằng đầu tiên để tham số depth là 5 cho nó ngu ngu tí
algo_neg = Negamax(5)
# Tạo thuật toán SSS cho thằng thứ 2 nếu để depth càng cao thì thường kết quả sẽ là hòa và nó tính toán khá lâu.
algo_sss = SSS(5)
# Start the game
game = GameController([AI_Player(algo_neg), AI_Player(algo_sss)])
game.play()
# In kết quả
if game.loss_condition():
print('\nNgười thắng: ', game.nopponent)
else:
print("\nKết quả Hòa")
0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Move #2: player 2 plays 0 :
0 1 2 3 4 5 6
-------------
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
X . . . . . .
O . . . . . .
Move #36: player 2 plays 6 :
0 1 2 3 4 5 6
-------------
X X O O X . .
O O X X O . .
X X O O X X .
O O X X O O .
X X O X X X X
O O O X O O O
Người thắng: 2
Xây dựng 2 con bots chơi game Hexapawn
Hexapawn là một game 2 người chơi trên một bàn cờ có kích cỡ là NxM. Chúng ta có mỗi con tốt (pawns, hoặc còn gọi là con chốt) với số lượng là N ở mỗi bên của bàn cờ. Và chiến thắng khi khi tiến hết được 1 tốt sang phía đối thủ hoặc đối thủ không thể di chuyển. Luật chơi ở mỗi bước đi thì cũng giống như nước đi của con tốt ở bàn cờ tướng, đi thẳng – ăn chéo.
from easyAI import TwoPlayersGame,AI_Player,Human_Player,Negamax
# tạo class để control game. Bắt đầu bằng cách định nghĩa số lượng tốt ở mỗi bên và độ dài rộng của bàn cờ. Tạo một list tuples chứa vị trí
class GameController(TwoPlayersGame):
def __init__(self,players,size=(4,4)):
self.size=size
num_pawns,len_board=size
p = [[(i, j) for j in range(len_board)] for i in [0, num_pawns - 1]]
print(p,num_pawns,len_board)
#Tạo hướng đi, đích đến và gắn những con chốt cho mỗi player"
for i, d, goal, pawn in [(0, 1, num_pawns - 1, p[0]), (1, -1, 0, p[1])]:
print(i)
print('d=',d)
print(goal)
print(pawn)
players[i].direction=d
players[i].goal_line=goal
players[i].pawns=pawn
self.players=players
self.nplayer=1
# Tạo bảng chữ cái để dễ xác định vị trí quân cờ (giống bàn cờ vua A1-A2...
self.alphabets='ABCDEFGHIJ'
# tạo 2 hàm lambda để chuyển đổi string <-> tuples
self.to_tuples = lambda s: (self.alphabets.index(s[0]), int(s[1:]) - 1)
self.to_string = lambda move: ' '.join([self.alphabets[move[i][0]] + str(move[i][1] + 1) for i in (0, 1)])
def possible_moves(self):
# Tạo hàm move để tính những bước đi có thể:
moves=[]
# Vị trí quân tốt của đối thủ
opponent_pawns=self.opponent.pawns
d=self.player.direction
# Khi không nhìn thấy quân tốt của đối thủ ở một vị trí thì có nghĩa đó là nơi có thể đi:
for i,j in self.player.pawns:
if(i+d,j) not in opponent_pawns:
moves.append(((i,j),(i+d,j)))
if(i+d,j+1) in opponent_pawns:
moves.append(((i,j),(i+d,j+1)))
if(i+d,j-1) in opponent_pawns:
moves.append(((i,j),(i+d,j-1)))
return list(map(self.to_string,[(i,j) for i,j in moves]))
def make_move(self,move):
move=list(map(self.to_tuples,move.split(' ')))
ind=self.player.pawns.index(move[0])
self.player.pawns[ind]=move[1]
# Loại bỏ tốt của đối thủ khi thấy nó trên đường đi:
if move[1] in self.opponent.pawns:
self.opponent.pawns.remove(move[1])
def loss_condition(self):
return (any([i==self.opponent.goal_line for i,j in self.opponent.pawns])) or(self.possible_moves()==[])
def is_over(self):
return self.loss_condition()
def show(self):
f=lambda x:'x' if x in self.players[0].pawns else('o' if x in self.players[1].pawns else '.')
print('\n'.join([" ".join([f((i,j))
for j in range(self.size[1])])
for i in range(self.size[0])]))
# Hàm khởi tạo
if __name__=="__main__":
scoring=lambda game:-100 if game.loss_condition() else 0
algorithm = Negamax(12,scoring)
game=GameController([Human_Player(),AI_Player(algorithm)])
game.play()
symbol="XO"
print("Kết quả: ",symbol[game.nopponent-1], " Thắng sau",game.nmove,"bước")
# Có thể thay Human_Player thành AI_Player với thuật toán bạn tùy chọn như SSS hoặc Negamax
Mấy game kiểu này thường người đi trước sẽ thắng
[[(0, 0), (0, 1), (0, 2), (0, 3)], [(3, 0), (3, 1), (3, 2), (3, 3)]] 4 4
0
d= 1
3
[(0, 0), (0, 1), (0, 2), (0, 3)]
1
d= -1
0
[(3, 0), (3, 1), (3, 2), (3, 3)]
x x x x
. . . .
. . . .
o o o o
Player 1 what do you play ? A1 B1
Move #1: player 1 plays A1 B1 :
. x x x
x . . .
. . . .
o o o o
Move #2: player 2 plays D1 C1 :
. x x x
x . . .
o . . .
. o o o
Player 1 what do you play ? A2 B2
Move #3: player 1 plays A2 B2 :
. . x x
x x . .
o . . .
. o o o
Move #4: player 2 plays D2 C2 :
. . x x
x x . .
o o . .
. . o o
Player 1 what do you play ? B2 C1
Move #5: player 1 plays B2 C1 :
. . x x
x . . .
x o . .
. . o o
Move #6: player 2 plays C2 B1 :
. . x x
o . . .
x . . .
. . o o
Player 1 what do you play ? C1 D1
Move #7: player 1 plays C1 D1 :
. . x x
o . . .
. . . .
x . o o
Kết quả: X Thắng sau 8 bước
Tổng kết:
Trong chương này chúng ta đã thảo luận về cách xây dựng một game với AI, và cách sử dụng các thuật toán tìm kiếm để áp dụng vào các chiến lược của game để chiến thắng. Về các thuật toán như Minimax, Negamax, cắt tỉa Alpha-Beta…
Ở chương tiếp theo chúng ta sẽ thảo luận về quá trình xử lý ngôn ngữ tự nhiên và sử dụng nó để phân tích dữ liệu text bằng cách mô hình và phân loại nó.