Luận văn Giải thuật tìm kiếm Minimax và ứng dụng trong các trò chơi có tổng bằng không

ến lược hiện tại của mình khi các đối thủ khác không thay đổi, tập hợp các chiến lược đó và phần thu nhận tương ứng tạo nên cân bằng Nash. Nói cách khác, cân bằng Nash đạt được nếu như thay đổi một cách đơn phương của bất cứ ai trong số các đối thủ cũng sẽ làm cho chính người đó thu lợi ít hơn mức có được với chiến lược hiện tại. Khái niệm này áp dụng cho những trò chơi gồm từ hai đối thủ trở lên và Nash đã chỉ ra rằng tất cả các khái niệm khác nhau về giải pháp trong các trò chơi được đưa ra trước đó đều có cân bằng Nash. Vì mối quan hệ giữa giá trị cực đại và giá trị cực tiểu đã được thiết lập, chúng ta có thể định nghĩa một giá trị cân bằng của trò chơi. Một cặp chiến lược (p’,q’) được gọi là cân bằng nếu p’ tương xứng tốt với q’ và ngược lại q’ tương xứng tốt với p’ , nghĩa là: M( p,q’) M( p’,q’) M( p’,q). Định lý Minimax Định lý: Với trò chơi có tổng bằng không và có hai người chơi, một trong 3 điều kiện sau đây sẽ dẫn đến 2 điều kiện còn lại. Tồn tại một cặp cân bằng. Tồn tại một số thực v, một chiến lược hỗn hợp p* và một chiến lược hỗn hợp q* sao cho: (a) với j= 1, 2,…, n (b) với i= 1, 2,…, m Điều kiện (3a) nói rằng tổn thất trung bình cho người chơi 2 dùng chiến lược thuần túy bất kỳ nào không nhỏ hơn v. Tương tự điều kiện (3b) nói tổn thất trung bình của người chơi 1 dùng chiến thuật thuần túy bất kỳ thì không lớn hơn v. Trong định lý Minimax, von Neumann (1928) chứng minh sự tồn tại tổng quát của các nghiệm Minimax trong các chiến lược ngẫu nhiên hóa cho các trò chơi hữu hạn bước, hai người chơi và tổng bằng không. Với các trò chơi này, định lý Minimax tương đương về mặt lô-gíc với sự tồn tại của cân bằng Nash. Định lý Minimax còn được phát biểu như sau: Với mọi trò chơi có tổng bằng không với hai người chơi thì luôn tồn tại một chiến lược cân bằng. Phần chứng minh định lý này có thể xem trong tài liệu tham khảo số [10]. Từ đặc điểm của trò chơi có tổng bằng không với hai người chơi (Zero-sum-game) và từ định lý Minimax nên thuật toán Minimax thích hợp với loại trò chơi này. Và đảm bảo khi thuật toán ứng dụng cho các trò chơi này sẽ chắc chắn có lời giải. 2.2 Giải thuật Minimax Xét một trò chơi đối kháng trong đó hai người thay phiên nhau đi nước của mình như cờ vua, cờ tướng, cờ carô,... Trò chơi có một trạng thái bắt đầu và mỗi nước đi sẽ biến đổi trạng thái hiện hành thành một trạng thái mới. Trò chơi sẽ kết thúc theo một quy định nào đó, theo đó thì cuộc chơi sẽ dẫn đến một trạng thái phản ánh có một người thắng cuộc hoặc một trạng thái mà cả hai đấu thủ không thể phát triển được nước đi của mình, ta gọi nó là trạng thái hòa cờ. Ta tìm cách phân tích xem từ một trạng thái nào đó sẽ dẫn đến đấu thủ nào sẽ thắng với điều kiện cả hai đấu thủ đều có trình độ như nhau. 2.2.1 Ý tưởng Hai đối thủ trong một trò chơi được gọi là MIN và MAX. MAX đại diện cho đối thủ quyết giành thắng lợi hay cố gắng tối đa 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 cùng những thông tin như MAX. Một trò chơi như vậy có thể được biểu diễn bởi một cây trò chơi. Mỗi một nút của cây biểu diễn cho một trạng thái. Nút gốc biểu diễn cho trạng thái bắt đầu của cuộc chơi. Mỗi nút lá biểu diễn cho một trạng thái kết thúc của trò chơi (trạng thái thắng, thua hoặc hòa). Nếu trạng thái x được biểu diễn bởi nút n thì các con của n biểu diễn cho tất cả các trạng thái kết quả của các nước đi có thể xuất phát từ trạng thái x. Do hai đấu thủ luân phiên nhau đi nước của mình nên các mức (lớp) trên cây trò chơi cũng luân phiên nhau là MAX và MIN. Cây trò chơi vì thế còn có tên là cây MIN-MAX. Trên cây trò chơi các nút ứng với trạng thái mà từ đó người chơi MAX chọn nước đi sẽ thuộc lớp MAX, các nút ứng với trạng thái mà từ đó người chơi MIN chọn nước đi sẽ thuộc lớp MIN. Chiến lược minimax thể hiện qua quy tắc định trị cho các nút trên cây trò chơi như sau: - Nếu nút là nút lá gán cho nút đó một giá trị để phản ánh trạng thái thắng thua hay hòa của các đấu thủ. - Sử dụng giá trị của các nút lá để xác định giá trị của các nút ở các mức trên trong cây trò chơi theo quy tắc: + Nút thuộc lớp MAX thì gán cho nó giá trị lớn nhất của các nút con của nút đó. + Nút thuộc lớp MIN thì gán cho nó giá trị nhỏ nhất của các nút con của nút đó. Giá trị được gán cho từng trạng thái theo quy tắc trên chỉ rõ giá trị của trạng thái tốt nhất mà mỗi đối thủ có thể hy vọng đạt được. Người chơi sẽ sử dụng các giá trị này để lựa chọn các nước đi cho mình. Đối với người chơi MAX khi đến lượt đi, người chơi này sẽ chọn nước đi ứng với trạng thái có giá trị cao nhất trong các trạng thái con, còn với người chơi MIN khi đến lượt sẽ chọn nước đi ứng với trạng thái có giá trị nhỏ nhất trong các trạng thái con. Ví dụ 1: Xét trò chơi carô có 9 ô (Tic tac toe). Hai người MAX và MIN thay phiên nhau đi X hoặc O (MAX đi X, MIN đi O). Người nào đi được 3 ô thẳng hàng (ngang, dọc, xiên) thì thắng cuộc. Nếu đã hết ô đi mà chưa phân thắng bại thì hai đấu thủ hòa nhau. Một phần của trò chơi này được biểu diễn bởi cây sau: MAX đi X 1 X X X O O O MAX đi X X X X O O X O X X X X O O O X X X X O O O 1 -1 0 MIN đi O 0 X X X X O O O O X X O X O O X O X O X X O O X O X O X X X O O O 1 0 -1 MAX đi X 0 0 1 MIN đi O X O X X X O O X O X O X X X O O X O X X X O X O O X O Hình 2.1. Một phần cây trò chơi trong trò chơi tic-tac-toe. 1 nếu tại đó người đi X đã thắng -1 nếu tại đó người đi X đã thua 0 nếu hai đấu thủ đã hòa nhau Trong cây trò chơi trên, các nút lá được tô nền và viền khung đôi để dễ phân biệt với các nút khác. Ta có thể gán cho mỗi nút lá một giá trị để phản ánh trạng thái thắng thua hay hòa của các đấu thủ. Chẳng hạn ta gán cho nút lá các giá trị như sau: Như vậy từ một trạng thái bất kỳ, đến lượt mình, người đi X sẽ chọn cho mình một nước đi sao cho dẫn đến trạng thái có giá trị lớn nhất (trong trường hợp này là 1). Ta nói X chọn nước đi MAX, nút mà từ đó X chọn nước đi của mình được gọi là nút MAX. Người đi O đến lượt mình sẽ chọn một nước đi sao cho dẫn đến trạng thái có giá trị nhỏ nhất (trong trường hợp này là -1, khi đó X sẽ thua và do đó O sẽ thắng). Ta nói O chọn nước đi MIN, nút mà từ đó O chọn nước đi của mình được gọi là nút MIN. Áp dụng chiến lược Minimax cho một nhánh trong cây trò chơi của trò chơi Tic-tac-toe ta có giá trị (phía trên mỗi nút) của các nút được thể hiện trong hình 2.1. 7 1 6-1 1 5-2 1 4-3 1 5-1-1 0 4-2-1 1 3-2-2 0 3-3-1 1 4-1-1-1 0 3-2-1-1 1 2-2-2-1 0 3-1-1-1-1 0 2-2-1-1-1 1 2-1-1-1-1-1 0 MAX MIN MAX MAX MIN MIN Ví dụ 2: Xét trò chơi Nim. Để chơi Nim, một số token (vật biểu hiện như đồng xu, lá bài, mảnh gỗ…) được đặt trên bàn giữa hai đối thủ. Ở mỗi nước đi, người chơi phải chia đống token thành hai đống nhỏ có số lượng khác nhau. Người chơi nào đến lượt mà không chia được là thua cuộc. Ứng với một token vừa phải, không gian trạng thái này có thể triển khai đến cùng. Hình sau biểu diễn không gian trạng thái của trò chơi có 7 token: Hình 2.2: Không gian trạng thái của trò chơi Nim. Khi chơi các trò chơi khó có thể triển khai hết không gian trạng thái, khó khăn chủ yếu là phải tính toán phản ứng của đối thủ. Một cách xử lý đơn giản nhất là giả sử đối thủ của chúng ta cũng sử dụng kiến thức về không gian trạng thái giống như chúng ta và áp dụng kiến thức đó kiên định để thắng cuộc. Mặc dù giả thiết này có những hạn chế của nó nhưng nó cũng cho chúng ta một cơ sở hợp lý để dự đoán hành vi của đối thủ. Giải thuật Minimax sẽ tìm kiếm không gian của trò chơi này theo giả thiết đó. Áp dụng chiến lược Minimax, chúng 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ó nướ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ị 1 hay 0 tùy theo kết quả đó là thắng cuộc đối với MAX hay MIN. Kết quả của việc áp dụng Minimax 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ể xảy ra cho MIN sẽ dẫn đến các nút có 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 là như thế nào (đường đi thắng lợi của MAX được cho theo mũi tên đậm). 2.2.2 Áp dụng giải thuật Minimax đến độ sâu lớp cố định Khi áp dụng Minimax cho các trò chơi phức tạp, hiếm khi có khả năng mở rộng đồ thị không gian trạng thái đến các nút lá. Thay vào đó không gian trạng thái này chỉ có thể được triển khai đến một số mức xác định phụ thuộc tiềm năng về thời gian và bộ nhớ chẳng hạn. Chiến lược này được gọi là tính trước n nước đi (n –move lookahead). Vì giá trị các nút trong đồ thị con này không phải là trạng thái kết thúc của trò chơi nên chúng không phản ánh giá trị thắng cuộc hay thua cuộc. Chúng chỉ có thể được gán một giá trị phù hợp với một hàm đánh giá heuristic nào đó. Giá trị được truyền ngược về nút gốc không cung cấp thông tin thắng cuộc hay thua cuộc mà chỉ là giá trị heuristic của trạng thái tốt nhất có thể tiếp cận sau n nước đi kể từ nút xuất phát. Việc tính trước này sẽ làm tăng hiệu quả của heuristic vì nó được áp dụng vào một phạm vi lớn hơn trong không gian trạng thái. Minimax sẽ hợp nhất tất cả các giá trị của các nút con cháu của một trạng thái thành một giá trị duy nhất cho trạng thái đó. Trong các cây trò chơi được tìm kiếm bằng mức hay lớp (ply), MAX và MIN luân phiên nhau chọn các nước đi. Mỗi nước đi của một đối thủ sẽ xác định một lớp mới trên cây. Các chương trình trò chơi nói chung đều dự tính trước một độ sâu lớp cố định (thường được xác định bằng các giới hạn về không gian hoặc thời gian của máy tính). Các trạng thái trên mức đó được đánh giá theo các heuristic và các giá trị này sẽ được truyền ngược lên bằng thủ tục Minimax, sau đó thuật toán tìm kiếm sẽ dùng các giá trị vừa nhận được để chọn lựa một nước trong số các nước đi kế tiếp. Bằng cách tối đa hóa cho các cha mẹ MAX và tối thiểu hóa cho các cha mẹ MIN, những giá trị này đi lùi theo đồ thị đến con của trạng thái hiện hành. Sau đó trạng thái hiện hành dùng chúng để tiến hành lựa chọn trong các con của nó [8]. MIN MAX 2 3 3 3 9 0 0 7 2 2 6 3 9 5 7 0 4 2 1 5 6 MAX MIN Hình 2.3: Minimax đối với không gian trạng thái giả 6-5=1 6 - 4= 2 X O 6-6= 0 6-6= 0 4-6= -2 5-6= -1 5-6= -1 X O X X O X 1 1 5 - 4= 1 X O X O X O X O X O X O X O X X O X O 5-5=0 6-5= 1 5-5=0 4-5= -1 -2 -1 Nút MAX Nước đi của MAX Hình 2.4: Minimax hai lớp được áp dụng vào nước đi mở đầu trò chơi Tic-tac-toe. Ở đây sử dụng một heuristic phức tạp hơn, nó cố đo mức độ tranh chấp trong trò chơi. Heuristic chọn một trạng thái cần đo, tính tất cả các đường thắng mở ra cho MAX, rồi trừ đi tổng số các đường thắng mở ra cho MIN. Giải thuật tìm kiếm sẽ cố gắng tối đa hóa sự chênh lệch (hiệu số) đó. Nếu có một trạng thái bắt buộc thắng cuộc cho MAX, nó sẽ được đánh giá là + ∞, còn với trạng thái bắt buộc thắng cuộc cho MIN thì được đánh giá là - ∞. 2.2.3 Thủ tục Minimax Giả sử chúng ta có một bộ phân tích thế cờ có thể áp dụng tất cả các luật, các phương pháp đánh cờ khác nhau vào từng thế cờ và chuyển đổi chúng thành một con số đại diện (cho điểm thế cờ). Mặt khác, ta giả sử con số đó là dương khi áp dụng cho thế cờ của một đấu thủ (được gọi là người chơi cực đại – người chơi MAX), và là âm khi áp dụng cho đấu thủ bên kia (được gọi là người chơi cực tiểu – người chơi MIN). Quá trình tính toán cho điểm thế cờ được gọi là lượng giá tĩnh (static evaluation). Hàm thực hiện việc tính toán được gọi là một bộ lượng giá tĩnh và giá trị nhận được gọi là điểm lượng giá tĩnh. Cả hai đấu thủ đều cố gắng đi như thế nào đó để đạt được điểm tuyệt đối lớn nhất. Người chơi cực đại (MAX) sẽ tìm những nước đi dẫn đến điểm của mình trở nên lớn hơn (hay cao nhất có thể được) hay điểm của đối thủ bớt âm hơn (nhỏ hơn về giá trị tuyệt đối). Còn đấu thủ của anh ta, người chơi cực tiểu (MIN), lại ra sức phản kháng lại, để dẫn tới điểm âm của anh ta âm hơn hay điểm dương của đối thủ nhỏ đi (Hình 2.3). Độ sâu xem xét Đường tìm kiếm- chuỗi nước đi dẫn đến thế cờ tốt nhất có thể đạt được … Các bàn cờ trung gian, phải biến đổi qua chúng trong quá trình đạt đến các bàn cờ đích, không cần so sánh chúng. Nước chọn đi Các bàn cờ đích, ta phải so sánh chúng với nhau để cân nhắc hơn thiệt do nước đi mang lại. Hình 2.5:Minh họa chiến lược chơi cờ của người lẫn máy. Các nút trắng là các thế cờ trung gian phải trải qua để đến được các thế cờ đích. Không cần phải xét đến độ tốt xấu của các thế cờ trung gian. Các nút đen là các thế cờ đích và phải xem xét độ tốt xấu để so sánh chúng với nhau. Từ đó sẽ tìm ra đường đi để đến thế cờ tốt nhất có thể được (chú ý không là thế cờ tốt nhất trong số đó do phải xem xét cả cách đi chống trả của đối phương). Từ ý tưởng ta có thể suy ra các bước của thuật toán Minimax như sau: - Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm tức nút lá), tính giá trị tĩnh của thế cờ hiện tại ứng với người chơi ở đó. Ghi nhớ kết quả - Nếu như mức đang xét là của người chơi cực tiểu (nút MIN), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả nhỏ nhất. - Nếu như mức đang xét là của người chơi cực đại (nút MAX), áp dụng thủ tục Minimax này cho các con của nó. Ghi nhớ kết quả lớn nhất. Từ ý tưởng phân tích trên ta có thể xây dựng thủ tục Minimax như sau: Hàm Minimax nhận vào một thế cờ pos và trả về giá trị của thế cờ đó. Nếu thế cờ pos tương ứng với nút lá trong cây trò chơi thì trả về giá trị đã được gán cho nút lá. Ngược lại ta cho pos một giá trị tạm value là -∞ hoặc ∞ tùy thuộc pos là nút MAX hay MIN và xét các thế cờ con của pos. Sau khi một con của pos có giá trị V thì đặt lại value= max(value, V) nếu n là nút MAX và value= min(value,V) nếu n là nút MIN. Khi tất cả các con của n đã được xét thì giá trị tạm value của pos trở thành giá trị của nó. (INFINITY thể hiện cho giá trị vô cùng) [15]. Ta có giả mã cho giải thuật Minimax như sau: function Minimax(pos): integer; value, best : integer; begin if pos là nút lá then return eval(pos) else begin {Khởi tạo giá trị tạm cho best } if pos là nút MAX then best:= -INFINITY else best := INFINITY; {hàm genPos sinh ra mọi nước đi từ thế cờ pos} genPos(pos); {Xét tất cả các con của pos, mỗi lần xác định được giá trị của một nút con, ta phải đặt lại giá trị tạm value. Khi đã xét hết tất cả các con thì value là giá trị của n} while (còn lấy được một nước đi m) do begin pos := Tính thế cờ mới nhờ đi m; value = Minimax(pos); if pos là nút MAX then if (value > best) then best := value; if pos là nút MIN then if (value < best) then best := value; end; Minimax := best; end; end; Xem xét đoạn chương trình trên ta thấy: - Có hai hàm mới là hàm eval(pos) và hàm genPos(pos). Hàm eval(pos) thực hiện việc tính giá trị (lượng giá) của thế cờ pos. Hàm genPos(pos) sinh ra tất cả các nước đi có thể từ thế cờ pos hiện tại. Việc xây dựng hai hàm này sẽ phụ thuộc vào từng trò chơi cụ thể. Hàm đánh giá Eval ứng với mỗi trạng thái (thế cờ) pos của trò chơi với một giá trị số Eval(pos). Giá trị này là sự đánh giá độ lợi thế của trạng thái pos. Trạng thái pos càng thuận lợi cho MAX thì Eval(pos) là số dương càng lớn, pos càng thuật lợi cho MIN thì eval(pos) là số âm càng nhỏ, Eval(pos) 0 đối với trạng thái không lợi thế cho ai cả. Chất lượng của chương trình chơi cờ phụ thuộc rất nhiều vào hàm đánh giá. Nếu hàm đánh giá cho ta sự đánh giá không chính xác về các trạng thái, nó có thể hướng ta đi tới trạng thái được xem là tốt, nhưng thực tế lại rất lợi cho ta. Thiết kế một hàm đánh tốt là một việc khó. Đòi hỏi ta phải quan tâm đến nhiều nhân tố. Ở đây có sự mâu thuẫn giữa độ chính xác của hàm đánh giá và thời gian tính của nó. Hàm đánh giá chính xác sẽ đòi hỏi rất nhiều thời gian tính toán, mà người chơi lại bị giới hạn bởi thời gian phải đưa ra nước đi. Trong chương 3 ta sẽ xem xét chi tiết hàm Eval và hàm GenPos. Như chúng ta đã biết, không phải lúc nào cũng đến được tận các nút lá. Đặc biệt trong các trò chơi cờ, bị giới hạn thời gian suy nghĩ của mỗi đối thủ đồng thời số nút và độ sâu của cây trò chơi là rất lớn. Chúng ta khó có thể thực hiện tìm kiếm đến độ sâu của các nút lá. Vì vậy, chúng ta chỉ thực hiện tìm đến một độ sâu depth cố định nào đó. Độ sâu depth càng lớn, hàm tìm kiếm càng gần giá trị tối ưu, cũng có nghĩa là “trình độ suy nghĩ” của máy càng cao! Như vậy, hàm Minimax bây giờ sẽ có lời gọi: Minimax(pos, depth) trong đó depth là độ sâu tìm kiếm. Thông thường, để cho tiện (và cũng rất gần thực tế) ta coi cả hai người chơi có cùng cách đánh giá về một thế cờ. Có điều thế cờ này là tốt với một người thì phải được đánh giá là tồi với người kia và ngược lại. Trong máy tính cách thể hiện tốt nhất là ta cho điểm một thế cờ có thêm dấu âm dương: dấu dương dành cho người chơi cực đại và dấu âm cho người chơi cực tiểu. Với người chơi cực đại sẽ mong muốn điểm này càng dương càng tốt, còn người chơi cực tiểu lại mong muốn điểm này càng âm càng tốt. Do đó để dễ xử lí ta sẽ tuỳ theo mức người chơi mà đổi dấu giá trị đánh giá thế cờ pos. Chú ý rằng, thay đổi độ sâu là chuyển sang đối phương nên phải đổi dấu. Chương trình thực hiện đổi dấu như sau: value:= -Minimax (pos, depth-1); {Tính điểm của pos} Do dùng cùng hàm lượng giá nên khi đến lượt, người chơi cực đại và cực tiểu có cùng cái nhìn như nhau về một thế cờ. Điều này dẫn đến có thể dùng cùng cách chọn nước đi tốt nhất cho họ. Vậy ta phát triển hàm Minimax thành dạng sau [15]: function Minimax (pos, depth): integer; begin if (depth = 0) or (pos là nút lá) then Minimax := Eval (pos) { Tính giá trị thế cờ pos } else begin best := -INFINITY; genPos(pos); { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin pos := Tính thế cờ mới nhờ đi m; value := -Minimax (pos, depth - 1); if value > best then best := value; end; Minimax := best; end; end; - Trong cài đặt, bàn cờ được biểu diễn bằng các biến toàn cục. Do đó thay cho truyền tham số là một bàn cờ mới pos vào thủ thục Minimax thì người ta biến đổi luôn biến toàn cục này nhờ thực hiện nước đi "thử" (nước đi dẫn đến bàn cờ mới pos). Sau khi Minimax thực hiện việc tính toán dựa vào bàn cờ lưu ở biến toàn cục thì thuật toán sẽ dùng một số thủ tục để loại bỏ nước đi này. Như vậy Minimax bỏ các tham số pos như sau: function Minimax(depth): integer; begin if (depth = 0) or (pos là nút lá) then Minimax := Eval { Tính giá trị thế cờ pos } else begin best := -INFINITY;  genPos; { Sinh ra mọi nước đi từ thế cờ pos } while còn lấy được một nước đi m do begin thực hiện nước đi m; value := -Minimax (depth - 1); bỏ thực hiện nước đi m; if value > best then best := value; end;  Minimax := best; end; end; 2.2.4 Đánh giá Thuật toán Minimax thăm toàn bộ cây trò chơi bằng việc dùng chiến lược tìm kiếm theo chiều sâu. Nên độ phức tạp của thuật toán này tương ứng trực tiếp với kích thước không gian tìm kiếm bd, trong đó b là hệ số phân nhánh của cây hay chính là nước đi hợp pháp tại mỗi điểm, d là độ sâu tối đa của cây. Thuật toán sẽ thăm tất cả các nút không chỉ là các nút lá vì vậy số lượng các nút được thăm sẽ là b(bd-1)/(b-1). Nhưng hàm lượng giá sẽ là phương thức chi phối hầu hết thời gian và chỉ làm việc trên các nút lá, vì vậy việc thăm các nút không phải các nút lá có thể bỏ qua [8]. Do đó độ phức tạp thời gian là O(bd). Bản chất của thuật toán là tìm kiếm theo chiều sâu, vì vậy việc đòi hỏi không gian bộ nhớ của nó chỉ tuyến tính với d và b. Vì thế độ phức tạp không gian là O(bd) [8][13]. Nếu hệ số nhánh trung bình của cây là b = 40, và tìm kiếm đến độ sâu d = 4 (các con số thường gặp trong trò chơi cờ) thì số nút phải lượng giá là 404 = 2560000 (trên 2 triệu rưỡi nút). Còn với b = 40, d = 5 thì số nút phải lượng giá sẽ tăng 40 lần nữa thành 405 = 102400000 (trên 102 triệu nút), đây là con số tương đối lớn. Có thể tiết kiệm được nhiều thời gian bằng việc dùng các thuật toán tìm kiếm thông minh hơn như thuật toán Alpha-beta, thuật toán này không thăm tất cả các nút lá mà vẫn cho kết quả đúng với thuật toán Minimax [9]. Trong phần tiếp theo ta sẽ xét thuật toán cải tiến này. 2.3 Giải thuật cải tiến Alpha-beta Thuật toán Minimax yêu cầu phải có sự phân tích qua hai bước đối với không gian tìm kiếm: bước đầu truyền xuống đến độ sâu của lớp áp dụng heuristic và bước sau để truyền ngược các giá trị trên cây. Minimax lần theo tất cả các nhánh trong không gian bao gồm cả những nhánh mà một thuật toán thông minh hơn có thể bỏ qua hay tỉa bớt. Các nhà nghiên cứu trong lĩnh vực chơi game đã xây dựng một kỹ thuật tìm kiếm gọi là cắt tỉa Alpha-beta nhằm nâng cao hiệu quả tìm kiếm trong các bài toán trò chơi hai đối thủ [9]. Bộ đánh giá tĩnh trong thủ tục Minimax cần được thực hiện đối với tất cả các nút tại mức cuối của cây trò chơi (nút lá). Ta có thể giảm bớt số tính toán tốn kém này bằng cách giảm số nhánh cây cần tạo ra và số các đánh giá tĩnh cần tính ra. Do vậy một giải pháp như đã dùng trong thủ tục nhánh và biên là không tiếp tục đi theo các đường không tốt. Mức cực đại Mức cực tiểu Mức cực đại 2 7 Mức cực đại Mức cực tiểu Mức cực đại 2 7 =2 =2 2 1 1 Mức cực đại Mức cực tiểu Mức cực đại 2 7 =2 2 Thuật toán Alpha-beta là một cải tiến của thuật toán Minimax nhằm tỉa bớt nhánh của cây trò chơi, làm giảm số lượng nút phải sinh và lượng giá, do đó có thể tăng độ sâu của cây tìm kiếm [9]. Giả sử hình sau là một thế cờ mà hai nút đầu tiên đã được lượng giá. Nếu thực hiện thủ tục Minimax đối với các nút đó sẽ cho thấy người chơi cực đại đã được đảm bảo nếu đi nước bên trái sẽ được ít nhất là 2 điểm dù là các lượng giá của các nút khác cho kết quả như thế nào đi nữa. Hình 2.6: Thuật toán Alpha-beta cắt tỉa nhánh Bây giờ, ta lại giả sử nút tiếp theo được lượng giá và cho kết quả là 1. Nếu đi vào nhánh này thì đối phương sẽ đảm bảo làm điểm của người chơi cực đại không thể vượt quá được giá trị 1 dù là các lượng giá của các nút khác cho kết quả như thế nào đi nữa. Do đó đến đây, nước đi tốt nhất là chọn nước đi bên trái với đảm bảo là ít nhất đạt được 2 điểm. Và do đó, hoàn toàn không cần thiết phải lượng giá nút còn lại. 2.3.1 Ý tưởng Ý tưởng của tìm kiếm Alpha-beta rất đơn giản: Thay vì nếu như tìm kiếm toàn bộ không gian đến một độ sâu lớp cố định, tìm kiếm Alpha-beta thực hiện theo kiểu tìm kiếm sâu. Có hai giá trị, gọi là alpha và beta được tạo ra trong quá trình tìm kiếm: - Giá trị alpha liên quan với các nút MAX và có khuynh hướng không bao giờ giảm. - Ngược lại giá trị beta liên quan đến các nút MIN và có khuynh hướng không bao giờ tăng. Giả sử có giá trị alpha của một nút MAX là 6, MAX không cần phải xem xét giá trị truyền ngược nào nhỏ hơn hoặc bằng 6 có liên quan với một nút MIN nào đó bên dưới. Giá trị alpha là giá trị thấp nhất mà MAX có thể nhận được sau khi cho rằng MIN cũng sẽ nhận giá trị tốt nhất của nó. Tương tự nếu MIN có giá trị beta là 6 nó cũng không cần xem xét các nút nằm dưới nó có giá trị lớn hơn hoặc bằng 6. Để bắt đầu thuật toán tìm kiếm Alpha-beta, ta đi xuống hết độ sâu lớp theo kiểu tìm kiếm sâu, đồng thời áp dụng đánh giá heuristic cho một trạng thái và tất cả các trạng thái anh em của nó. Giả thuyết tất cả đều là nút MIN. Giá trị tối đa của các nút MIN này sẽ được truyền ngược lên cho nút cha mẹ (là một nút MAX). Sau đó giá trị này được gán cho ông bà của các nút MIN như là một giá trị beta kết thúc tốt nhất. Tiếp theo thuật toán này sẽ đi xuống các nút cháu khác và kết thúc việc tìm kiếm đối với nút cha mẹ của chúng nếu gặp bất kỳ một giá trị nào lớn hơn hoặc bằng giá trị beta này. Quá trình này gọi là cắt tỉa Beta (β cut). Cách làm tương tự cũng được thực hiện cho việc cắt tỉa Alpha (α cut) đối với các nút cháu của một nút MAX. Hai luật cắt tỉa dựa trên các giá trị alpha và beta là: Quá trình tìm kiếm có thể kết thúc bên dưới một nút MIN nào có giá trị beta nhỏ hơn hoặc bằng giá trị alpha của một nút cha MAX bất kỳ của nó. 2. Quá trình tìm kiếm có thể kết thúc bên dưới một nút MAX nào có giá trị alpha lớn hơn hoặc bằng giá trị beta của một nút cha MIN bất kỳ của nó. Việc cắt tỉa Alpha-beta như vậy thể hiện quan hệ giữa các nút ở lớp n và các nút ở lớp n+2 và do quan hệ đó toàn bộ các cây con bắt nguồn ở lớp n+1 đều có thể loại khỏi việc xem xét. Chú ý rằng giá trị truyền ngược thu được hoàn toàn giống như kết quả Minimax, đồng thời tiết kiệm được các bước tìm kiếm một cách đáng kể. Nguyên tắc Alpha-beta: Nếu biết điều đó thật sự tồi thì đừng mất thời gian tìm hiểu nó sẽ tồi tệ đến đâu. Ý tưởng này được gọi là nguyên tắc Alpha-beta do nó dùng trong thủ tục Alpha-beta (ta sẽ xét dưới đây). Hai tham số của thủ tục này được gọi là alpha và beta được dùng để theo dõi các triển vọng - chúng cho biết các giá trị nằm ngoài khoảng [alpha, beta] là các điểm "thật sự tồi" và không cần phải xem xét nữa. Khoảng [alpha, beta] còn được gọi là cửa sổ alpha, beta. Trong ngữ cảnh của các trò chơi, nguyên tắc Al