Phần 18: Gaming – Phần 1 – Lập trình AI bằng Python
Trò chơi được chơi cùng 1 chiến lược. Từng người chơi hay đội sẽ đưa ra chiến lược trước khi bắt đầu trò chơi và họ phải thay đổi hay xây dựng chiến lược mới tùy vào (các) tình huống hiện giờ trong game.
Table of Contents
1. Thuật toán Search :
Bạn phải xem xét trò chơi máy tính cũng với chiến lược giống nhau như ở trên. Chú ý rằng Thuật toán tìm kiếm là thuật toán tìm ra chiến lược trong game máy tính.
Tổng quát :
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 quốc gia đi tối ưu để chúng có thể tới đích cuối cùng và giành được chiến thắng. Các thuật toán này sử dụng tập hợp những điều kiện chiến thắng, khác nhau cho mọi trò chơi, nhằm tìm ra nước đi tốt nhất.
Hình dung 1 trò chơi máy tính như 1 cái cây. Chúng ta biết rằng cây có những nút. Khởi đầu từ gốc, chúng ta sẽ có thể đi tới nút chiến thắng cuối cùng, nhưng đối với những nước đi tối ưu. Đó là công việc của các thuật toán tìm kiếm. Mỗi nút trong cây như thế đại diện cho 1 trạng thái trong tương lai. Các thuật toán tìm kiếm tìm kiếm qua cây này để ra quyết định ở mỗi bước hay nút của game.
2. Combinational Search
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 là toàn diện, đó là nguyên nhân vì sao chúng khám phá tất cả không gian tìm kiếm nhằm tìm ra biện pháp dẫn tới lãng phí tài nguyên. Sẽ cồng kềnh hơn nếu như các thuật toán này cần tìm kiếm tất cả không gian tìm kiếm nhằm tìm ra biện pháp cuối cùng.
Để xóa bỏ loại vấn đề như thế, chúng ta sẽ có thể sử dụng tìm kiếm tổ hợp sử dụng cách khám phá không gian tìm kiếm và giảm kích thước của nó bằng cách xóa bỏ các chuyển động sai có thể xảy ra. Do đó, các thuật toán như thế có thể tiết kiệm tài nguyên. Những thuật toán sử dụng heuristic để tìm không gian và tiết kiệm tài nguyên sẽ được trình bày dưới đây
3. Thuật toán Minimax
Đây chính là chiến lược được dùng do tìm kiếm tổ hợp sử dụng cách heuristic để tăng tốc chiến lược tìm kiếm. Khái niệm chiến lược Minimax có thể được hiểu với ví dụ về 2 trò chơi game thủ, trong đó từng người chơi nỗ lực dự đoán động thái tiếp theo của đối thủ và nỗ lực giảm thiểu tính năng đó. Ngoài ra, để giành được chiến thắng, game thủ luôn nỗ lực phát huy tối đa tính năng của mình dựa vào tình hình hiện giờ.
Heuristic đóng 1 vai trò quan trọng trong những loại chiến lược như Minimax. Mỗi nút của cây sẽ có 1 hàm heuristic được liên kết với nó. Dựa vào kinh nghiệm đó, mọi người sẽ ra quyết định di chuyển về phía nút có lợi nhất cho họ.
4. Alpha-Beta Pruning
1 vấn đề lớn với thuật toán Minimax là nó có thể khám phá các phần không liên quan của cây, dẫn tới lãng phí tài nguyên. Do đó phải có 1 chiến lược để quyết định phần nào của cây có liên quan và phần nào hay không liên quan và để phần không liên quan chưa được khám phá. Cắt tỉa Alpha-Beta là 1 trong các loại chiến lược như thế.
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 các phần của cây mà không có bất kỳ biện pháp nào. Khái niệm chính của việc cắt tỉa Alpha-Beta là sử dụng 2 giới hạn có tên là 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à những giá trị hạn chế tập hợp các biện pháp khả thi. Nó so sánh giá trị của nút hiện giờ với giá trị của các tham số alpha và beta, để nó có thể di chuyển tới phần của cây có lời giải và xóa bỏ phần còn lại.
5. 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à ta cần xác định 2 hàm heuristic khác nhau. Mối liên hệ giữa những khám phá này là ở chỗ, trạng thái của game càng tốt cho 1 game thủ, thì game thủ kia càng tệ hơn. Trong thuật toán Negamax, công việc giống nhau của 2 hàm heuristic được bắt đầu với sự giúp đỡ của 1 hàm heuristic.
6. Xây dựng bot để chơi recreation :
Để xây dựng các bot để chơi 2 trò chơi game thủ trong AI, ta cần cài đặt thư viện easyAI. Nó là 1 khung trí tuệ nhân tạo cung cấp toàn bộ những chức năng để xây dựng trò chơi 2 game thủ. Bạn sẽ có thể download như dưới đây:
pip set up easyAITrong game này, sẽ có 1 đống tiền xu. Từng người chơi phải lấy những xu từ đống đó. Mục tiêu của game là tránh lấy đồng xu cuối cùng trong đống. Tôi sẽ sử dụng lớp LastCoinStanding được kế thừa từ lớp TwoPlayersGame của thư viện easyAI :
from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player
from easyAI.AI import TTHiện tại, kế thừa lớp từ lớp TwoPlayerRecreation để xử lý toàn bộ những hoạt động của game –
class LastCoin_game(TwoPlayersGame):
def __init__(self, gamers):Xác định game thủ và game thủ sẽ bắt đầu trò chơi.
self.gamers = gamers
self.nplayer = 1Xác định số lượng xu trong game, tại đây chúng tôi đang dùng 15 đồng xu cho trò chơi.
self.num_coins = 15Xác định số xu tối đa mà game thủ có thể được nhận trong 1 nước đi.
self.max_coins = 4có những điều nhất định cần xác định như được hiển thị trong đoạn mã sau. Xác định những bước di chuyển có thể.
def possible_moves(self):
return (*1*)Xác định việc xóa bỏ các đồng tiền
def make_move(self, transfer):
self.num_coins -= int(transfer)Xác định ai đã lấy đồng xu cuối cùng.
def win_game(self):
return self.num_coins <= 0Xác định thời điểm dừng trò chơi, đó là khi ai đó thắng.
def is_over(self):
return self.win()Xác định cách tính điểm.
def rating(self):
return 100 if self.win_game() else 0Xác định số xu còn lại trong đống.
def present(self):
print(self.num_coins, 'cash left within the pile')
if __name__ == "__main__":
tt = TT()
LastCoin_game.ttentry = lambda self: self.num_coinsGiải quyết trò chơi cùng đoạn mã sau:
r, d, m = id_solve(LastCoin_game,
vary(2, 20), win_score=100, tt=tt)
print(r, d, m)Quyết định ai sẽ bắt đầu trò chơi
recreation = LastCoin_game([AI_Player(tt), Human_Player()])
recreation.play()Bạn sẽ có thể tìm thấy kết quả sau và lối chơi đơn giản của game 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 cash left within the pile
Move #1: participant 1 performs 4 :
11 cash left within the pile
Player 2 what do you play ? 2
Move #2: participant 2 performs 2 :
9 cash left within the pile
Move #3: participant 1 performs 3 :
6 cash left within the pile
Player 2 what do you play ? 1
Move #4: participant 2 performs 1 :
5 cash left within the pile
Move #5: participant 1 performs 4 :
1 cash left within the pile
Player 2 what do you play ? 1
Move #6: participant 2 performs 1 :
0 cash left within the pile