THUẬT TOÁN MINIMAX TRONG GAME CARO JAVA

  -  

Vừa qua mình có làm game dạng như caro với đã làm cho AI mang lại nó tất cả dùng thuật toán minimax thấy xuất xắc hay cần post lên share cho mọi fan cùng tham khảo. Bài viết này mình chỉ viết về các cái cơ bản của thuật toán rất có thể áp dụng cho hầu hết game đơn giản dễ dàng dạng này như caro, tictactoe..Phần khởi đầu sơ qua núm là xong. Và hiện giờ là ban đầu nào.

*
Như hình bên trên ta thấy là trạng thái lúc này của game sắp tới lượt tấn công của người chơi X đại diện thay mặt cho MAX. Ta tạm vẻ ngoài giá trị MAX thời gian game chiến hạ cho X = +10 cùng MIN lúc game thua thảm cho X = -10 và lúc trò chơi hòa = 0. Lúc này ở lượt 1, MAX hoàn toàn có thể đi được một trong những 3 nước như hình. Vậy làm sao để lựa chọn 1 trong 3 nước đó nước làm sao là rất tốt để đi. Bọn họ dựa vào quý hiếm của từng nước để chọn nước tốt nhất, như tại chỗ này 3 node đó thuộc lớp MAX nên chọn giá trị mập nhất. Chúng ta bắt đầu tìm quý giá của từng node đó. Ở lớp MAX trong lượt 1, thì ta có node 1,2,3 được viết số từ trái sáng nên như hình. Node 3 bọn họ đã là node lá (X win trò chơi ) và có mức giá trị là +10. Còn 2 node 1,2 thì chưa biết giá trị của nó tại lượt 1 nên họ dựa vào giá chỉ trị của các node bé để định quý giá và bởi giá trị nhỏ nhắn nhất của những node bé ở lớp MIN tại lượt 2.


Bạn đang xem: Thuật toán minimax trong game caro java


Xem thêm: Trò Chơi Kính Thực Tế Ảo Từ Giải Đố Tới Hành Động Kịch Tính, Game Hay Dành Cho Kính Thực Tế Ảo


Xem thêm: Trò Chơi Mạo Hiểm Tiếng Anh, Thể Thao Mạo Hiểm Bằng Tiếng Anh


Cứ liên tục tương tự vì vậy đến lúc gặp gỡ node lá thì từ node lá kia ta suy trái lại và ta tính được node 1 có giá trị là -10 cùng node 2 là 0. Vậy nước đi cực tốt ở đây là như node 3 có giá trị lớn nhất là +10.5. Áp dụng vào code

Đầu tiên chúng ta cần 1 hàm để tìm hiểu trạng thái game hiện tại đã thắng, thảm bại hay hòa.CheckStateGame(Move)Tiếp theo là yêu cầu tìm nước cực tốt cần đi.

function findBestMove(board): bestMove = NULLfor each move in board : if current move is better than bestMove bestMove = current movereturn bestMoveVà tiếp nối là hàm tính cực hiếm minimax của các nước đó. Function minimax(board, isMaximizingPlayer): if(CheckStateGame(curMove) == WIN_GAME) return MAX if(CheckStateGame(curMove) == LOSE_GAME) return MIN if( CheckStateGame(curMove) == DRAW_GAME) return DRAW_VALUE if isMaximizingPlayer : bestVal = -INFINITY for each move in board : value = minimax(board, false) bestVal = max( bestVal, value) return bestVal else : bestVal = +INFINITY for each move in board : value = minimax(board, true) bestVal = min( bestVal, value) return bestValVậy là bọn họ implement được thuật toán minimax.6. Thuật toán Minimax với độ sâu

*
Như nghỉ ngơi hình này ta bắt buộc tìm giá chỉ trị béo nhất của những node con. Mà ta tính giá tốt trị node 1,2,3 khớp ứng là -10, +10, +10. Vậy quý hiếm ở node 2,3 là cân nhau = +10. Bắt buộc ta đang trù trừ giữa 2 node 2,3.Từ đó ta nâng cấp thuật toán minimax với độ sâu depth:

function minimax(board, depth,isMaximizingPlayer): if(CheckStateGame(curMove) == WIN_GAME) return MAX - depth if(CheckStateGame(curMove) == LOSE_GAME) return MIN + depth if( CheckStateGame(curMove) == DRAW_GAME) return DRAW_VALUE if isMaximizingPlayer : bestVal = -INFINITY for each move in board : value = minimax(board, depth +1, false) bestVal = max( bestVal, value) return bestVal else : bestVal = +INFINITY for each move in board : value = minimax(board, depth + 1,true) bestVal = min( bestVal, value) return bestValÁp dụng tăng cấp trên thì ta sẽ sở hữu được giá trị new của node 1,2,3 khớp ứng là -9,+8,+10 => Max = +10 quý giá của node 3. Vậy node 3 là node nên tìm.7. Về tối ưu thuật toán minimaxĐánh giá chỉ thuật toán: trả sử số nhánh của cây game là a. Xét độ sâu depth b thì số nút cần được tính là a^b. Đây là số lượng khá lớn.Nên hiện ra thuật toán để buổi tối ưu thuật toán minimax là cắt tỉa Alpha Beta. (Sẽ được update vào các bài sau

*
).