Thuật toán Minimax

Question

Tôi có một câu hỏi đơn giản về thuật toán Minimax: ví dụ cho trò chơi tic-tac-toe, làm cách nào để xác định chức năng của tiện ích cho mỗi người chơi? Nó không tự động làm điều đó, phải không? Tôi phải mã hóa các giá trị trong game, nó không thể tự học được, đúng không?

Answer 1

Không, MiniMax không tìm hiểu. Nó là một phiên bản thông minh hơn của tìm kiếm cây brute-force.

Answer 2

Tic-Tac-Toe đủ nhỏ để chạy trò chơi đến cùng và chỉ định 1 cho chiến thắng, 0 cho hòa và -1 cho thua.

Nếu không, bạn phải cung cấp một hàm xác định giá trị của một vị trí theo kinh nghiệm. Trong cờ vua, ví dụ một yếu tố lớn là giá trị của vật liệu, nhưng cũng là người điều khiển trung tâm hoặc cách dễ dàng các mảnh có thể di chuyển.

Đối với việc học, bạn có thể thêm các yếu tố trọng số vào các khía cạnh khác nhau của vị trí và cố gắng tối ưu hóa các yếu tố đó bằng cách chơi trò chơi liên tục.

Answer 3

Làm cách nào để xác định chức năng tiện ích cho mỗi lần phát?

Cẩn thận ;-) Điều này article cho biết chức năng đánh giá thiếu sót một chút (một cho ví dụ hoặc không đủ "sâu" để nhìn vào cây có thể hoặc không nắm bắt được strengh tương đối của một số vị trí hội đồng quản trị) kết quả trong một thuật toán tổng thể yếu (một trong đó lỏng lẻo thường xuyên hơn).

không thể tự học chúng, phải không?

Không, không. Tuy nhiên, có nhiều cách để làm cho máy tính biết được sức mạnh tương đối của các vị trí bảng. Ví dụ bằng cách xem xét Donald Mitchie and his MENACE program bạn sẽ thấy cách một quá trình ngẫu nhiên có thể được sử dụng để tìm hiểu bảng mà không cần bất kỳ một kiến ​​thức nào trước đây là nhưng các quy tắc của trò chơi. Phần buồn cười là trong khi điều này có thể được thực hiện trong máy tính, một vài trăm hạt màu và hộp khớp là tất cả những gì cần thiết, nhờ kích thước tương đối nhỏ của không gian trò chơi, và cũng nhờ vào các đối xứng khác nhau.

Sau khi học một cách tuyệt vời để dạy máy tính cách chơi, chúng tôi có thể không muốn quay trở lại với MinMax khi áp dụng cho Tic-Tac-Toe. Sau khi tất cả MinMax là một cách tương đối đơn giản để cắt tỉa cây quyết định, hầu như không cần thiết với không gian trò chơi nhỏ của tic-tac-toe. Nhưng, nếu chúng ta phải ;-) [quay trở lại MinMax] ...

Chúng tôi có thể xem xét "hộp diêm" được kết hợp với lần phát tiếp theo (tức là không đi sâu) và sử dụng tỷ lệ phần trăm của các hạt được liên kết với mỗi ô vuông, là một yếu tố bổ sung. Sau đó chúng ta có thể đánh giá một cây truyền thống, nhưng chỉ đi, nói 2 hoặc 3 di chuyển sâu (độ sâu nhìn phía trước nông thường sẽ kết thúc thường là thua lỗ hoặc rút) và đánh giá từng bước tiếp theo trên cơ sở đơn giản -1 (mất), 0 (vẽ/không xác định), +1 (thắng). Bằng cách kết hợp tỷ lệ phần trăm hạt và đánh giá đơn giản (bằng cách nói thêm, chắc chắn không phải bằng phép nhân), chúng tôi có thể sử dụng hiệu quả MinMax theo cách tương tự như cách sử dụng trong trường hợp không thể đánh giá cây trò chơi kết thúc.

Điểm mấu chốt: Trong trường hợp của Tic-Tac-Toe, MinMax chỉ trở nên thú vị hơn (ví dụ như giúp chúng ta khám phá tính hiệu quả của một chức năng tiện ích cụ thể) khi chúng ta xóa bản chất xác định của trò chơi, liên kết với dễ dàng đánh giá cây đầy đủ. Một cách khác để làm cho trò chơi [toán học] thú vị là chơi với một đối thủ làm cho những sai lầm ...

Answer 4

Thông thường bạn sẽ thực hiện trực tiếp chức năng tiện ích. Trong trường hợp này thuật toán sẽ không tìm hiểu cách chơi trò chơi, thuật toán sẽ sử dụng thông tin mà bạn đã mã hóa rõ ràng trong quá trình triển khai.

Tuy nhiên, có thể sử dụng genetic programming (GP) hoặc một số kỹ thuật tương đương để tự động lấy được chức năng tiện ích. Trong trường hợp này, bạn sẽ không phải mã hóa bất kỳ chiến lược rõ ràng nào. Thay vào đó, sự tiến hóa sẽ khám phá ra cách chơi riêng của nó.

Bạn có thể kết hợp mã minimax và mã GP vào một chương trình thích ứng (có thể rất chậm) hoặc bạn có thể chạy GP trước, tìm một hàm tiện ích tốt và sau đó thêm hàm này vào mã minimax của bạn bạn sẽ có bất kỳ chức năng mã hóa bằng tay nào.