Thuật toán Minimax

Mục Lục Thuật toán Minimax Thuật toán minimax Thuật toán minimax chứa đựng tất cả các khả năng của việc chuyển đổi các trạng thái từ 1 trạng thái được đưa ra và từ đó bao phủ lên các khoảng trống . Thuật toán này có ứng dụng trong trò chơi có khả năng chuyển đổi trạng thái từ 1 trạng thái thử nghiệm cho trước. Một ví dụ thông dụng là ta có thể bắt trước thuật toán minimax qua trò chơi Nim game Đây là 1 trò chơi giữa 2 người chơi.Trò chơi bắt đầu với 1 số lẻ các que.thông thường là 7 hoặc 9 .mỗi vị trí trên 1 dòng đơn được gọi là 1 cọc mốc .Mỗi người chơi sẽ lần lượt được đặt 1 cọc mốc để phá vỡ 2 mốc kia của đối phương trên 1 dòng.trò chơi sẽ kết thúc khi người kia ko đưa ra được bước đi thành công.Người nào ko đưa ra được bước đi thành cồng đầu tiên sẽ thua. Theo quy ước tiêu chuẩn chúng tôi đặt tên cho hai người chơi là MINIMIZER và MAXIMIZER NIM là 1 trò chơi phòng thủ vì vậy người chơi mở ở đây gọi là MINIMIZER Biểu đồ của của trò chơi NIM được biểu diễn như hình in fig. 4.12 (a) , phân ranh giới bước đi của MAXIMIZER và MINIMIZER thuật toán Minimax, được trình bày trong thời gian ngắn, theo quy ước sẽ được sử dụng. Sự thành công của MAXIMIZER được ký hiệu là 1,trong khi sự thành công của MINIMIZER bởi -1 và hòa là 0.Những giá trị này thì được gắn vào các bước đi của các người chơi.một câu hỏi thường phát sinh là người chơi làm sao biết được bước đi của họ là thành công hay thất bại cho tới khi trò chơi kết thúc.Điều này được thấy rõ trong thuật toán Minimax theo nguyên tắc : chỉ định 1 số từ {+1,0,-1} phụ thuộc vào các bước đi có thành công hay không của MAXIMIZER và MINIMIZER hay là hòa theo thứ tự.bây giờ ta sẽ truyền các giá trị đó phụ thuộc vào các bước đi của MAXIMIZER và MINIMIZER. Nếu nó là của Maximizer di chuyển sau đó giá trị của nó được giá trị tối đa sở hữu bởi offsprings của nó.  Trong trường hợp nó là của một MINIMIZER di chuyển thì giá trị của nó sẽ được tối thiểu của các giá trị sở hữu bởi offsprings của nó . Nếu các giá trị được truyền lên đến nút gốc của nguyên tắc trên, sau đó mỗi người chơi có thể chọn di chuyển tốt hơn đến lượt mình. Các tính toán quá trình trong một trò chơi Minimax được minh họa dưới đây fig. 4,12 (b). Hàm Minnimax 1.mở rộng toàn bộ các không gian trống sau các nút 2. gán các giá trị {+1,0,-1} tùy thuộc vào các bước đi của MAXIMIZER hay của MINIMIZER tương ứng 3. đối với mỗi node con tương ứng đó thì làm Begin Nếu đó là nút của MAXIMIZER , thì giá trị của nó sẽ là giá trị cực đại trong các giá trị ; Nếu đó là nút của MINIMIZER ,thì giá trị của nó sẽ là giá trị cực tiểu trong các giá trị End For; End. Các Alpha-beta Cutoff Thủ tục  Thuật toán Minimax đã được nói ở trên yêu cầu mở rộng tới toàn bộ khoảng không gian trống . Đây là 1 hạn chế nghiêm trọng , đặc biệt với vấn đề mở rộng khoảng trống . Để giải quyết khó khăn này một cách giải quyết là dung đánh giá heuristic tình trạng bước đi tiếp theo của người chơi để chọn một bước đi hiện tại cho cùng 1 người chơi.Chúng ta sẽ minh họa quá trình tính toán của các biện pháp heuristic của một nút dưới đây với sự nổi tiếng trò chơi TIC TAC TOE Xét 1 hàm heuristic e(n) [3], [5] tại nút n đánh giá sự khác biệt của các dòng có thể giành chiến thắng của mỗi người chơi e(n) =M(O)- O(n) trong đó M (n) = số dòng của tôi có thể giành chiến thắng và O (n) = số dòng giành chiến thắng của đối thủ. Ví dụ, trong fig. 4,13 M (n) = 6, O (n) = 5 và vì thế e (n) = 1.  Bây giờ, chúng tôi sẽ thảo luận về một loại mới của thuật toán, mà không yêu cầu mở rộng toàn bộ không gian exhaustively. Thuật toán này được gọi là alpha-beta thuật toán cắt. Trong thuật toán này, hai phụ lớp của chuyển động là xem xét để lựa chọn di chuyển hiện tại từ lựa chọn thay thế. Alpha và beta biểu hai cắt các cấp liên kết với các nút MAX và MIN. Giá trị của alpha MAX node không thể giảm, trong khi giá trị beta của các nút MIN có thể không tăng. Nhưng làm thế nào chúng ta có thể tính toán các giá trị alpha và beta?  Chúng là những giá trị sao lưu lên đến gốc như Minimax. Có một vài thú vị điểm đó có thể được khám phá ở giai đoạn này Trước khi quá trình tính toán MAX / MIN của các giá trị sao lưu của lớp con, thuật toán alpha-beta cắt ước lượng e (n) tại tất cả các nút rìa n. Bây giờ, các giá trị ước tính sau thuật toán Minimax. Bây giờ, để cắt tỉa các đường dẫn không cần thiết  bên dưới một nút, kiểm tra xem  giá trị beta của bất kỳ nút MIN bên dưới một nút MAX là nhỏ hơn hoặc bằng với giá trị alpha của nó. Nếu có, cắt tỉa con đường bên dưới nút MIN giá trị beta của bất kỳ nút MAX bên dưới một nút MIN là nhỏ hơn hoặc bằng với giá trị alpha của nó. Nếu có, cắt tỉa con đường bên dưới nút MAX Fig.4.14: Hai lớp di chuyển của Maximizer với e tính (n) tạirìa các nút: C, D, E; sao lưu các giá trị tại nút B và A vàthiết lập của αmax và βmin giá trị tại các nút A và B tương ứng Dựa trên các cuộc thảo luận ở trên, hiện nay chúng tôi trình bày các bước chính trong các α-βthuật toán tìm kiếm.i) Tạo một nút mới, nếu nó là di chuyển bắt đầu, mở rộng kháchiện cây theo độ sâu cách đầu tiên. Để thực hiện một quyết định vềlựa chọn của một di chuyển ở độ sâu d, cây nên được mở rộng ít nhấtlên đến độ sâu (d + 2).ii) Tính e (n) cho tất cả để lại (rìa) các nút n trong cây.iii) Tính α 'min (cho các nút tối đa) và β 'tối đa các giá trị (đối với các nút min) tạitổ tiên của các nút rìa bởi các nguyên tắc sau đây.Ước tính tối thiểu của các giá trị (e hoặc α) sở hữu doβ của trẻ em của một nút MINIMIZER N và gán nó 'tối đa giá trị.Tương tự như vậy, ước tính tối đa của các giá trị (e hoặc β) sở hữudo con của một nút Maximizer N và gán nó giá trị αmin . Fig. 4.15: Những cách nghĩ để có thể di chuyển thay thế F và cũng tự sinh ra ở lớp tiếp theo là G e(G)=-1, β max ở F =-1, , β max ở F nhỏ hơn so với α min ở A Như vậy ko có nhu cầu tìm kiếm dưới F, G có thể bớt không gian tìm kiếm Fig. 4.16: Nút G đã bị cắt tỉa , các nút C, D và E được mở rộng e(n ) được thiết lập ở n = H , I , J và K và giá trị của αmin được ước lượng tại các nút C, D, E.Bởi vì giá tri αmin ở C lớn hơn giá trị βmax ở B, giá tri αmin ở D bằng giá trị βmax ở B, ở đó ko cần tìm kiếm dưới nút C và D IV) Nếu các nút của MAXIMIZER có các giá trị αmin. Sau đó giá trị αmin = MAX(αmin). Một mặt khác nếu các nút của MINIMIZER có giá trị βmax và sau đó βmax = MAX(βmax) V) Nếu thiết lập giá trị βmax ở nút MINIMIZER tại N nhỏ hơn αmin của nút cha MAXIMIZER tại N’ thì sau đó ko cần tìm kiếm dưới nút N. Tương tự Nếu thiết lập giá trị αmin ở nút MAXIMIZER tại N nhỏ hơn αmin của nút cha MINIMIZER tại N’ thì sau đó ko cần tìm kiếm dưới nút N Những bước ở trên được thực hiện cho đến khi nào trò chơi kết thúc Trò chơi tíc tắc toe Giới thiệu trò chơi Trò chơi này được chơi bởi 2 đối thủ với 9 ô. Một trong 2 đối thủ sẽ đi trước đánh o hoặc (X) vào 1 ô bất kỳ trên bàn cờ , đối thủ còn lại chọn 1 trong 8 ô còn lại để đi .Hai đối thủ thay nhau đánh vào các ô trống cho đến khi có 1 đối thủ có 3 ô nằm trên 1 đường thẳng trước thì thắng. Nếu hết 9 ô cờ mà không có đối thủ nào có 3 ô nằm trên 1 đường thẳng thì ván cờ kết thúc với tỷ số hòa Mục tiêu trò chơi Đến lượt chơi mỗi người cố gắng để tạo ra 3 quân cờ nằm trên 1 đường thẳng để là người chiến thắng hoặc cố ngăn cản người kia tạo được 3 quân cờ trên một đường thẳng Hướng giải quyết Sử dụng thuật toán Minnimax – cơ chế cắt tỉa alpha beta để tìm nước đi tốt nhất có lợi cho từng người chơi Hai đối thủ trong 1 trò chơi được gọi là MIN và MAX .MAX là đại diện cho đối thủ quyết dành thắng lợi hay cố gắng tối ưu hóa ưu thế của mình. Ngược lại MIN là đối thủ cố gắng tối thiểu hóa điểm số của MAX . Ta giả thiết MIN cũng dùng thong tin như MAX Khi áp dụng thủ tục Minnimax ta đánh dấu luân phiên từng mức trong không gian tìm kiếm phù hợp với đối thủ có bước đi ở mức đó trong ví dụ trên MIN được quyền đi trước, từng nút lá được gán giá trị 0 hay 1 tùy theo đó là thắng cuộc với MIN hay MAX.Minimax sẽ truyền các giá trị này lên cao dần trên đồ thị qua các nút cha mẹ kế tiếp nhau theo luật sau: -Nếu trạng thái cha mẹ là nút MAX , gán cho nó giá trị tối đa của các con cháu của nó - Nếu trạng thái cha mẹ là nút MIN , gán cho nó giá trị tối thiểu của con cháu của nó Giá trị được gán cho từng trạng thái bằng cách đó sẽ chỉ rõ trạng thái tốt nhất mà đối thủ này có thể đạt được . Các giá trị này sẽ được dùng để lựa chọn các bước đi có thể có. Kết quả của việc áp dụng Minnimax vào đồ thị không gian trạng thái đối với trò chơi Nim được thể hiện như hình trên. Vì tất cả các nước đi đầu tiên có thể sảy ra cho MIN sẽ dần đến giá trị 1 nên đối thủ MAX luôn có thể bắt trò chơi giành thắng lợi cho mình bất kể nước đi đầu tiên của MIN như nào Thuật toán using System; using System.Collections.Generic; using System.Text; public enum GameState { InProgress, ComputerWins, HumanWins, Draw } class Board { #region Declare field and delegate public static readonly int Empty = 0; public static readonly int X = -1; public static readonly int O = 1; public GameState BoardState; //represents the state of the game public int iBoardSize; //Size of board in one dimension public int iEmptySquares; //Count of unplayed squares used to check for draw condition public int[,] aiBoard; //The board #endregion // //Create a new Board object from a size parameter // public Board(int iSize) { this.iBoardSize = iSize; this.iEmptySquares = iSize * iSize; this.aiBoard = new int[iSize, iSize]; this.BoardState = GameState.InProgress; } // //Create a new Board object by copying an existing one // public Board(Board board) { this.iEmptySquares = board.iEmptySquares; this.iBoardSize = board.iBoardSize; this.BoardState = board.BoardState; this.aiBoard = new int[iBoardSize, iBoardSize]; //Copy aiBoard int i, j; for (i = 0; i < this.iBoardSize; i++) { for (j = 0; j < this.iBoardSize; j++) { this.aiBoard[i, j] = board.aiBoard[i, j]; } } } // // Apply a move // public void MakeMove(int CurrentPlayer, Move move) { aiBoard[move.iCol, move.iRow] = CurrentPlayer; //Check for draw condition iEmptySquares--; if (iEmptySquares == 0) this.BoardState = GameState.Draw; } // // Checks the board for a winner and reassigns // this.BoardState as appropriate. // public void CheckBoard() { int i, j, iTotal; //Check the rows for (i = 0; i < iBoardSize; i++) { iTotal = 0; for(j = 0; j< iBoardSize; j++) { iTotal += aiBoard[i, j]; } if (iTotal == -iBoardSize) { this.BoardState = GameState.ComputerWins; return; } if (iTotal == iBoardSize) { this.BoardState = GameState.HumanWins; return; } } //Check the columns for (j = 0; j < iBoardSize; j++) { iTotal = 0; for (i = 0; i < iBoardSize; i++) { iTotal += aiBoard[i, j]; } if (iTotal == -iBoardSize) { this.BoardState = GameState.ComputerWins; return; } if (iTotal == iBoardSize) { this.BoardState = GameState.HumanWins; return; } } //Check Top-Left to Bottom-Right diagonal iTotal = 0; for (i = 0; i < iBoardSize; i++) { iTotal += aiBoard[i, i]; } if (iTotal == -iBoardSize) { this.BoardState = GameState.ComputerWins; return; } if (iTotal == iBoardSize) { this.BoardState = GameState.HumanWins; return; } //Check Top-Right to Bottom-Left diagonal iTotal = 0; for (i = iBoardSize - 1, j = 0; i >= 0 && j<iBoardSize; i--, j++) { iTotal += aiBoard[i, j]; } if (iTotal == -iBoardSize) { this.BoardState = GameState.ComputerWins; return; } if (iTotal == iBoardSize) { this.BoardState = GameState.HumanWins; return; } } } Giới thiệu chương trình Giao diện chính của chương trình Chức năng chính của chương trình Kết quả của trò chơi Tài liệu tham khảo Artificial Inteligence and Soft Computing - Amit Konar