Thuật toán tìm kiếm
Bạn sẽ phải xem xét các trò chơi máy tính cũng với chiến lược tương tự như trên. Lưu ý rằng Thuật toán tìm kiếm là thuật toán tìm ra chiến lược trong các trò chơi trên máy tính.
Làm thế nào nó hoạt động
Mục tiêu của các thuật toán tìm kiếm là tìm ra tập hợp các nước đi tối ưu để có thể đi đến đích cuối cùng và giành chiến thắng. Các thuật toán này sử dụng tập hợp các điều kiện chiến thắng, khác nhau đối với mỗi trò chơi, để tìm ra các nước đi tốt nhất.
Hình dung một trò chơi máy tính như cái cây. Chúng tôi biết rằng cây có các nút. Bắt đầu từ gốc, chúng ta có thể đi đến nút chiến thắng cuối cùng, nhưng với những nước đi tối ưu. Đó là công việc của thuật toán tìm kiếm. Mỗi nút trong cây như vậy đại diện cho một trạng thái trong tương lai. Các thuật toán tìm kiếm tìm kiếm thông qua cây này để đưa ra quyết định ở mỗi bước hoặc nút của trò chơi.
Tìm kiếm kết hợp
Nhược điểm chính của việc sử dụng các thuật toán tìm kiếm là chúng có bản chất toàn diện, đó là lý do tại sao chúng khám phá toàn bộ không gian tìm kiếm để tìm giải pháp dẫn đến lãng phí tài nguyên. Sẽ cồng kềnh hơn nếu các thuật toán này cần tìm kiếm toàn bộ không gian tìm kiếm để tìm giải pháp cuối cùng.
Để loại bỏ loại vấn đề như vậy, chúng ta có thể sử dụng tìm kiếm tổ hợp sử dụng kinh nghiệm để khám phá không gian tìm kiếm và giảm kích thước của nó bằng cách loại bỏ các bước di chuyển sai có thể xảy ra. Do đó, các thuật toán như vậy có thể tiết kiệm tài nguyên. Một số thuật toán sử dụng heuristic để tìm kiếm không gian và tiết kiệm tài nguyên được thảo luận ở đây –
Thuật toán tối thiểu
Đó là chiến lược được sử dụng bởi tìm kiếm tổ hợp sử dụng heuristic để tăng tốc chiến lược tìm kiếm. Khái niệm về chiến lược Minimax có thể được hiểu với ví dụ về trò chơi hai người chơi, trong đó mỗi người chơi cố gắng dự đoán nước đi tiếp theo của đối thủ và cố gắng giảm thiểu chức năng đó. Ngoài ra, để giành chiến thắng, người chơi luôn cố gắng phát huy tối đa chức năng của mình dựa trên tình hình hiện tại.
Heuristic đóng một vai trò quan trọng trong các loại chiến lược như Minimax. Mỗi nút của cây sẽ có một hàm heuristic liên kết với nó. Dựa trên kinh nghiệm đó, nó sẽ đưa ra quyết định di chuyển về phía nút có lợi nhất cho họ.
Cắt tỉa Alpha-Beta
Một vấn đề chính với thuật toán Minimax là nó có thể khám phá những phần không liên quan của cây, dẫn đến lãng phí tài nguyên. Do đó, phải có một chiến lược để quyết định phần nào của cây có liên quan và phần nào không liên quan và để lại phần không liên quan chưa được khám phá. Cắt tỉa Alpha-Beta là một trong những loại chiến lược như vậy.
Mục tiêu chính của thuật toán cắt tỉa Alpha-Beta là để tránh việc tìm kiếm những phần không có lời giải của cây. Khái niệm chính của cắt tỉa Alpha-Beta là sử dụng hai giới hạn có tên Alpha , giới hạn dưới tối đa và Beta , giới hạn trên tối thiểu. Hai tham số này là các giá trị hạn chế tập hợp các giải pháp khả thi. Nó so sánh giá trị của nút hiện tại với giá trị của các tham số alpha và beta, để nó có thể di chuyển đến phần của cây có lời giải và loại bỏ phần còn lại.
Thuật toán Negamax
Thuật toán này không khác với thuật toán Minimax, nhưng nó có cách triển khai thanh lịch hơn. Nhược điểm chính của việc sử dụng thuật toán Minimax là chúng ta cần xác định hai hàm heuristic khác nhau. Mối liên hệ giữa các heuristic này là, trạng thái của trò chơi càng tốt đối với một người chơi thì càng tệ đối với người chơi kia. Trong thuật toán Negamax, cùng một công việc của hai hàm heuristic được thực hiện với sự trợ giúp của một hàm heuristic duy nhất.
Xây dựng Bot để chơi trò chơi
Để tạo bot chơi trò chơi hai người chơi trong AI, chúng ta cần cài đặt thư viện easyAI . Nó là một khung trí tuệ nhân tạo cung cấp tất cả các chức năng để xây dựng trò chơi hai người chơi. Bạn có thể tải xuống với sự trợ giúp của lệnh sau –
pip install easyAI
Một Bot để chơi Đồng xu cuối cùng
Trong trò chơi này, sẽ có một đống tiền xu. Mỗi người chơi phải lấy một số xu từ đống đó. Mục tiêu của trò chơi là tránh lấy đồng xu cuối cùng trong đống. Chúng tôi sẽ sử dụng lớp LastCoinStanding kế thừa từ lớp TwoPlayersGame của thư viện easyAI . Đoạn mã sau hiển thị mã Python cho trò chơi này – Nhập các gói cần thiết như được hiển thị
from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player
from easyAI.AI import TTBây giờ, kế thừa lớp từ lớp TwoPlayerGame để xử lý mọi hoạt động của trò chơi
class LastCoin_game(TwoPlayersGame):
def __init__(self, players):
Bây giờ, xác định người chơi và người chơi sẽ bắt đầu trò chơi
self.players = players
self.nplayer = 1
Bây giờ, hãy xác định số xu trong trò chơi, ở đây chúng tôi đang sử dụng 15 xu cho trò chơi.
self.num_coins = 15
Xác định số xu tối đa mà người chơi có thể nhận được trong một nước đi.
self.max_coins = 4
Bây giờ có một số điều cần xác định như được hiển thị trong đoạn mã sau. Xác định các bước di chuyển có thể.
def possible_moves(self):
return [str(a) for a in range(1, self.max_coins + 1)]
Xác định việc loại bỏ các đồng tiền
def make_move(self, move):
self.num_coins -= int(move)
Xác định ai đã lấy đồng xu cuối cùng
def win_game(self):
return self.num_coins <= 0
Xác định thời điểm dừng trò chơi, đó là khi ai đó thắng
def is_over(self):
return self.win()
Nêu cách tính điểm.
def score(self):
return 100 if self.win_game() else 0
Xác định số xu còn lại trong đống
def show(self):
print(self.num_coins, 'coins left in the pile')
if __name__ == "__main__":
tt = TT()
LastCoin_game.ttentry = lambda self: self.num_coins
Giải trò chơi bằng khối mã sau
r, d, m = id_solve(LastCoin_game,
range(2, 20), win_score=100, tt=tt)
print(r, d, m)
Quyết định ai sẽ bắt đầu trò chơi
game = LastCoin_game([AI_Player(tt), Human_Player()])
game.play()
Bạn có thể tìm thấy đầu ra sau đây và cách chơi đơn giản của trò chơi này
d:2, a:0, m:1
d:3, a:0, m:1
d:4, a:0, m:1
d:5, a:0, m:1
d:6, a:100, m:4
1 6 4
15 coins left in the pile
Move #1: player 1 plays 4 :
11 coins left in the pile
Player 2 what do you play ? 2
Move #2: player 2 plays 2 :
9 coins left in the pile
Move #3: player 1 plays 3 :
6 coins left in the pile
Player 2 what do you play ? 1
Move #4: player 2 plays 1 :
5 coins left in the pile
Move #5: player 1 plays 4 :
1 coins left in the pile
Player 2 what do you play ? 1
Move #6: player 2 plays 1 :
0 coins left in the pile
Bot để chơi Tic Tac Toe
Tic-Tac-Toe rất quen thuộc và là một trong những trò chơi phổ biến nhất. Hãy để chúng tôi tạo trò chơi này bằng cách sử dụng thư viện easyAI trong Python. Đoạn mã sau là mã Python của trò chơi này – Nhập các gói như được hiển thị
from easyAI import TwoPlayersGame, AI_Player, Negamax
from easyAI.Player import Human_Player
Kế thừa lớp từ lớp TwoPlayerGame để xử lý mọi hoạt động của trò chơi −
class TicTacToe_game(TwoPlayersGame):
def __init__(self, players):
Bây giờ, hãy xác định người chơi và người chơi sẽ bắt đầu trò chơi
self.players = players
self.nplayer = 1
Xác định loại bảng –
self.board = [0] * 9
Bây giờ có một số điều cần xác định như sau –
Xác định các bước di chuyển có thể
def possible_moves(self):
return [x + 1 for x, y in enumerate(self.board) if y == 0]
Xác định nước đi của một người chơi –
def make_move(self, move):
self.board[int(move) - 1] = self.nplayer
Để tăng cường AI, hãy xác định thời điểm người chơi di chuyển –
def umake_move(self, move):
self.board[int(move) - 1] = 0Xác định điều kiện thua mà đối thủ có ba hàng
def condition_for_lose(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[z-1] == self.nopponent)
for z in combination]) for combination in possible_combinations])
Xác định kiểm tra để kết thúc trò chơi
def is_over(self):
return (self.possible_moves() == []) or self.condition_for_lose()
Hiển thị vị trí hiện tại của người chơi trong trò chơi
def show(self):
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.
def scoring(self):
return -100 if self.condition_for_lose() else 0
Xác định phương thức chính để xác định thuật toán và bắt đầu trò chơi
if __name__ == "__main__":
algo = Negamax(7)
TicTacToe_game([Human_Player(), AI_Player(algo)]).play()
Bạn có thể thấy đầu ra sau đây và cách chơi đơn giản của trò chơi này
. . .
. . .
. . .
Player 1 what do you play ? 1
Move #1: player 1 plays 1 :
O . .
. . .
. . .
Move #2: player 2 plays 5 :
O . .
. X .
121
. . .
Player 1 what do you play ? 3
Move #3: player 1 plays 3 :
O . O
. X .
. . .
Move #4: player 2 plays 2 :
O X O
. X .
. . .
Player 1 what do you play ? 4
Move #5: player 1 plays 4 :
O X O
O X .
. . .
Move #6: player 2 plays 8 :
O X O
O X .
. X .
Xem Thêm : AI với Python – Mạng lưới thần kinh