Thuật Toán Minimax Trong Game Caro Java

Vừa qua mình có làm game dạng như caro và đã làm AI cho nó có dùng thuật toán minimax thấy hay hay nên post lên chia sẻ cho mọi người cùng tham khảo. Bài viết này mình chỉ viết về những cái cơ bản của thuật toán có thể áp dụng cho những game đơn giản dạng này như caro, tictactoe..Phần mở đầu sơ qua thế là xong. Và bây giờ là bắt đầu nào.

Như hình trên ta thấy là trạng thái hiện tại của game đang đến lượt đánh của người chơi X đại diện cho MAX. Ta tạm quy định giá trị MAX lúc game thắng cho X = +10 và MIN lúc game thua cho X = -10 và lúc game hòa = 0. Lúc này ở lượt 1, MAX có thể đi được 1 trong 3 nước như hình. Vậy làm sao để chọn 1 trong 3 nước đó nước nào là tốt nhất để đi. Chúng ta dựa vào giá trị của từng nước để chọn nước tốt nhất, như ở đây 3 node đó thuộc lớp MAX nên chọn giá trị lớn nhất. Chúng ta bắt đầu tìm giá trị của từng node đó. Ở lớp MAX trong lượt 1, thì ta có node 1,2,3 được đánh số từ trái sáng phải như hình. Node 3 chúng ta đã là node lá (X win game ) và 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 chúng ta dựa vào giá trị của các node con để định giá trị và bằng giá trị bé nhất của các node con ở 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ứ tiếp tục tương tự như vậy đến lúc gặp node lá thì từ node lá đó ta suy ngược lại và ta tính được node 1 có giá trị là -10 và node 2 là 0. Vậy nước đi tốt nhấ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 để biết trạng thái game hiện tại đã thắng, thua hay hòa.CheckStateGame(Move)Tiếp theo là cần tìm nước tốt nhấ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 là hàm tính giá trị 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à chúng ta implement được thuật toán minimax.6. Thuật toán Minimax với độ sâu

Như ở hình này ta cần tìm giá trị lớn nhất của các node con. Mà ta tính được giá trị node 1,2,3 tương ứng là -10, +10, +10. Vậy giá trị ở node 2,3 là bằng nhau = +10. Nên ta đang phân vân 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 nâng cấp trên thì ta sẽ có giá trị mới của node 1,2,3 tương ứng là -9,+8,+10 => Max = +10 giá trị của node 3. Vậy node 3 là node cần tìm.7. Tối ưu thuật toán minimaxĐánh giá thuật toán: Giả sử số nhánh của cây game là a. Xét độ sâu depth b thì số nút cần phải tính là a^b. Đây là con số khá lớn.Nên sinh ra thuật toán để 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

).