Đề tài 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

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 Alpha-beta nói rằng, mỗi khi xem xét một nút bất kì, nên kiểm tra các thông tin đã biết về các nút cha, ông của nó. Có thể do có đủ thông tin từ cha, ông nên không cần phải làm bất cứ việc gì nữa cho nút này. Do đó, nguyên tắc này cũng giúp chỉnh sửa hoặc xác định chính xác giá trị tại nút cha, ông nó [5]. Như trên nói, một cách để tiện theo dõi quá trình tính toán là dùng các tham số alpha và beta để ghi lại các thông tin theo dõi cần thiết. Thủ tục Alpha-beta được bắt đầu tại nút gốc với giá trị của alpha là - và beta là +. Thủ tục sẽ tự gọi đệ quy chính nó với khoảng cách giữa các giá trị alpha và beta ngày càng hẹp hơn. 2.3.2 Giải thuật Thuật toán Alpha -Beta Nếu mức đang xét là đỉnh (gốc cây), đặt giá trị của alpha là - và beta là +. 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, 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 lại kết quả. Nếu như mức đang xét là của người chơi cực tiểu (MIN), thực hiện các công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục Alpha-beta hoặc cho đến khi alpha là bằng hoặc lớn hơn beta. Áp dụng thủ tục Alpha-beta với giá trị alpha và beta hiện tại cho một con. Ghi nhớ lại kết quả. So sánh giá trị ghi nhớ với giá trị beta, nếu giá trị đó nhỏ hơn thì đặt beta bằng giá trị mới này. Ghi nhớ lại beta (thu hẹp khoảng [alpha, beta] bằng cách giảm giá trị beta). Nếu như mức đang xét là của người chơi cực đại (MAX), thực hiện các công việc sau cho đến khi tất cả các con của nó đã được xét với thủ tục Alpha-beta hoặc cho đến khi alpha là bằng hoặc lớn hơn beta. Áp dụng thủ tục Alpha-beta với giá trị alpha và beta hiện tại cho một con. Ghi nhớ lại kết quả. So sánh giá trị ghi nhớ với giá trị alpha, nếu giá trị đó lớn hơn thì đặt Alpha bằng giá trị mới này. Ghi nhớ lại alpha (thu hẹp khoảng [alpha, beta] bằng cách tăng giá trị alpha). MIN MAX 2 3 3 3 0 0 2 2 3 5 0 2 1 MAX MIN A D E B C Hình 2.7 Minh họa giải thuật Alpha-beta A có=3 ( Giá trị nút A sẽ không lớn hơn 3). B bị cắt tỉa , vì 5>3. C có =3 ( Giá trị nút C sẽ không nhỏ hơn 3). D bị cắt tỉa , vì 0<3. E bị cắt tỉa , vì 2<3. Giá trị nút C là 3. Từ ý tưởng trên ta sẽ xây dựng hàm AlphaBeta bằng ngôn ngữ tựa Pascal. Hàm này sẽ có dạng khai báo như dưới đây, trong đó depth là độ sâu tìm kiếm, INFINITY là giá trị vô cùng, thuật toán tính toán dựa trên thế cờ hiện tại pos là các biến toàn cục [15][16]. function AlphaBeta(alpha, beta, depth): integer; begin if (depth = 0) or (pos là nút lá) then AlphaBeta := Eval { Tính giá trị thế cờ pos } else begin best := -INFINITY;  Gen; { Sinh ra mọi nước đi từ vị trí pos } while (còn lấy được một nước đi m) and (best Alpha then Alpha := best;  Thực hiện nước đi m; value := -AlphaBeta(-beta, -Alpha, depth-1); Bỏ thực hiện nước đi m; if value > best then best := value; end;  AlphaBeta := best; end; end; Ví dụ lời gọi thủ tục AlphaBeta đầu tiên với độ sâu tìm kiếm 4 và thế cờ hiện tại pos có dạng như sau: AlphaBeta(-INFINITY, +INFINITY, 4); alphaa beta Miền xem xét miền “tồi tệ” (cẳt bỏ) miền “tồi tệ” (cẳt bỏ) So với thuật toán Minimax thì trong thuật toán AlphaBeta đã đưa thêm hai biến alpha, beta làm hai mức ngưỡng. Ta thấy cứ mỗi khi best >= beta thì thuật toán không thực hiện tiếp vòng lặp, có nghĩa là nó không chịu mở rộng tiếp những nhánh còn lại nữa. Các nhánh đó đã bị cắt bỏ và do đó ta sẽ tiết kiệm được thời gian. Việc cắt bỏ này hoàn toàn an toàn với những lí do ta đã xét ở trên. Ta thấy rằng mỗi lần hàm này được gọi thì chỉ có tham số beta được dùng để so sánh cắt bỏ, còn tham số alpha không được dùng. Tuy nhiên khi áp dụng cùng thuật toán cho cây con thì ta đã hoán vị hai giá trị alpha, beta cho nhau (và đảo cả dấu), do đó alpha sẽ có tác dụng trong độ sâu sau, rồi độ sâu sau nữa lại đến lượt beta... Nói cách khác, một giá trị chỉ luôn ảnh hưởng đến người chơi cực đại, còn giá trị kia lại luôn ảnh hưởng đến người chơi cực tiểu. Chúng là các ngưỡng giữa các nước đi được chấp nhận và không chấp nhận. Những nước đi cần quan tâm phải nằm lọt giữa hai giá trị này. Dần dần khoảng cách giữa hai giá trị alpha và beta càng ngày càng thu hẹp và dẫn đến các nhánh cây có giá trị nằm ngoài khoảng này nhanh chóng bị cắt bỏ: Hình 2.8: alpha, beta giống như hai lưỡi dao dùng để cắt bỏ lớp vỏ dầy. Hai lưỡi dao này sẽ được thu hẹp dần dần. Lượng cắt bỏ phụ thuộc vào tốc độ thu hẹp, thu hẹp càng nhanh cắt bỏ càng nhiều. 2.3.3 Đánh giá Hiệu quả của việc cắt nhánh Alpha-beta phụ thuộc nhiều vào thứ tự các nước đi kế tiếp được thực hiện. Nếu các nước đi kế tiếp được thực hiện có thứ tự ngẫu nhiên thì tổng số nút được thực hiện sẽ khoảng O(b3d/4) [8]. Trong đó b là độ rộng của cây (hệ số phân nhánh trung bình của các con), d là độ sâu của cây. 2-1 với d chẵn +-1 với d lẻ Trong điều kiện lí tưởng, thuật toán Alpha-beta chỉ phải xét số nút theo công thức:  Như vậy, trong trường hợp tốt nhất thuật toán Alpha-beta chỉ cần thực hiện khoảng O(bd/2) nút để chọn ra nước đi tốt nhất, thay vì O(bd). Hệ số phân nhánh hiệu quả trở thành thay vì b như trong thuật toán Minimax [8][14]. Thuật toán Alpha-beta nói chung giúp chúng ta tiết kiệm nhiều thời gian so với Minimax mà vẫn đảm bảo kết quả tìm kiếm chính xác. Tuy nhiên lượng tiết kiệm này không ổn định - phụ thuộc vào số nút mà nó cắt bỏ. Trong trường hợp xấu nhất thuật toán không cắt được một nhánh nào và phải xét số nút đúng bằng thuật toán Minimax. Ta cần đẩy mạnh việc cắt bỏ nhờ đẩy nhanh sự thu hẹp của cửa sổ tìm kiếm Alpha-beta. Cửa sổ này được thu hẹp một bước khi gặp một giá trị mới tốt hơn giá trị cũ. Khi gặp giá trị tốt nhất thì cửa sổ này thu hẹp nhất. Do đó nếu càng sớm gặp giá trị tốt nhất thì cửa sổ càng chóng thu hẹp. Như vậy phải làm sao cho các nút ở lá được sắp xếp theo trật tự từ cao xuống thấp. Trật tự này càng tốt bao nhiêu thì thuật toán chạy càng nhanh bấy nhiêu (các công thức về số nút phải lượng giá trong điều kiện lí tưởng ở trên tính được với trật tự là tốt nhất). Ví dụ: Ta sẽ xét xem thuật toán Alpha-beta hoạt động như thế nào đối với cây trò chơi sau: 1 3 4 9 11 7 13 17 19 21 24 26 28 34 32 36 5 2 =8 8 9 38 29 14 12 10 30 23 25 27 22 20 18 37 35 33 15 6 39 31 16 2 4 = 4 1 3 = 5 1 2 =3 3 9 6 5 = 5 3 8 = 4 4 5 = 5 Kết quả tìm kiếm nước đi 8 7 2 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2 16 6 4 Hình 2.9: Một cây trò chơi có độ sâu 3 và hệ số nhánh 3. Số trong các hình chữ nhật cho biết thứ tự đưa ra các kết luận. Chú ý rằng chỉ có tất cả là 16 đánh giá tĩnh được thực hiện (các nút đen) chứ không phải là 27 như khi không dùng thuật toán Alpha-beta. Nhánh đi tốt nhất cho người chơi cựa đại là nhánh giữa. Các thứ tự kết luận (các con số bên trái) được đưa ra như sau: [1-2] Tìm kiếm đi xuống dưới theo nhánh trái cho đến lá. Ở đây giá trị tĩnh thu được là 8. Giá trị đầu tiên này do người chơi cực đại được phép chọn trong ba giá trị ở nhánh này đã đảm bảo rằng là kết quả thu được sẽ ít nhất là bằng 8. Điều lưu ý này được bước 2 ghi lại. [3-5] Để chắc chắn không còn có điểm nào cao hơn 8, người chơi cực đại phải xét cả hai thế cờ còn lại và thu được các giá trị 7 và 2. Do đó đến đây đã kết luận chính xác điểm cao nhất có thể đạt được ở cây con là đúng bằng 8. [6] Leo lên một tầng cây. Đây là các nước đi của người chơi cực tiểu. Ta không hi vọng anh ta cho người chơi cực đại được nhiều điểm nên có thể tạm kết luận ở mức này là sẽ đạt được nhiều nhất là 8 điểm. [7-8]. Để xem người chơi cực tiểu còn lựa chọn nào tốt hơn (và tồi tệ hơn cho người chơi cực đại) ta phải xem xét cả hai nước đi còn lại. Nước đi còn lại đầu tiên dẫn đến giá trị lượng giá tĩnh là 9> 8. Như vậy nhánh giữa là tồi tệ hơn cho người chơi cực tiểu. Đến đây việc cắt bỏ được thực hiện do đó người chơi cực đại không thể với tới được điểm đó khi đã có sẵn lựa chọn thấp hơn cho anh ta (là 8). Điều này cũng dẫn đến không cần thiết phải xét hai nút còn lại - đằng nào nhánh giữa cũng đủ tồi tệ rồi và người chơi cực tiểu sẽ không chọn nó để đi. [9-14] Người chơi cực tiểu cần phải khảo sát tiếp lựa chọn cuối cùng. Cách làm tương tự như phần trên. Ở đây phải lượng giá cả ba nút cây và kết luận cuối cùng được đưa ra là người chơi cực đại đi giỏi lắm thì chỉ đạt được 4 điểm. [15] Như vậy nhờ việc khảo sát nhánh cây bên phải người chơi cực tiểu thấy rằng nếu chọn đi theo nhánh này thì người chơi cực đại chỉ được có 4 điểm thay cho 8. [16] Bây giờ ta có thể kết luận ở mức trên cùng. Mức này là của người chơi cực đại. Anh ta thấy rằng nếu chọn đi theo nhánh trái thì được 4 điểm. Như vậy anh ta đã chắc chắn điểm của mình sẽ ít nhất là 4 rồi. Để xem liệu có thể đạt được điểm cao hơn nữa hay không cần phải xem xét hai nhánh còn lại. [17-30] Tương tự như phần trên, ta kết luận nhánh giữa sẽ mang lại cho người chơi cực đại 5 điểm. [31] Cũng tương tự như kết luận 16, ở đây ta kết luận khả quan hơn là người chơi cực đại đã cầm chắc 5 điểm và có thể còn cao hơn. [32-38] Ta kết luận được rất nhanh là cây con bên phải chỉ cho "thu hoạch" nhiều nhất là 3 điểm - một điểm số quá kém do đó thuật toán không xem xét các trường hợp còn lại nữa. Do đó đã tiết kiệm được 6 nút không cần phải lượng giá và cũng không phải sinh nước đi cho hai trường hợp. [39] Kết luận cuối cùng là điểm cao nhất mà người chơi cực đại có thể thu được là 5 điểm nhờ chọn đi theo nhánh giữa. 2.4 So sánh giải thuật Minimax và giải thuật Alpha-beta. Dưới đây là bảng so sánh số nút phải xét giữa hai giải thuật Minimax và Alpha-beta. Độ sâu Minimax AlphaBeta Tỉ lệ số nút Minimax/Alpha-beta Số nút Số lần tăng Số nút Số lần tăng 1 40 40 1 2 1600 40 79 1.9 20 3 64000 40 1852 23.2 34 4 2560000 40 3199 1.7 800 5 102400000 40 74118 23.2 1381 6 4096000000 40 127999 1.7 32000 7 163840000000 40 2964770 23.2 55262 8 6553600000000 40 5120000 1.7 1280000 Với b = 40 và d = 4 ta có số nút phải xét là 2x402 - 1 = 3199. Như vậy trong điều kiện lí tưởng thì số nút phải xét nhờ Alpha-beta (chỉ khoảng 3 nghìn nút) ít hơn thuật toán Minimax (hơn 2,5 triệu nút) là 2560000/ 3199 khoảng 800 lần. Còn với b = 40 và d = 5 ta có số nút phải xét là 403 + 40(5/2) - 1 = 64000+10119-1 = 74118. Số nút phải xét nhờ Alpha-beta ít hơn thuật toán Minimax (hơn 102 triệu nút) là 102400000/74118 = 1382 lần. Ta có thể nhận xét như sau: - Số lần tăng số nút khi tăng độ sâu của Minimax luôn là hệ số phân nhánh b, trong trường hợp này là 40. Số lần tăng của Alpha-beta ít hơn nhiều: chỉ cỡ 1.7 lần khi tăng từ d lẻ sang d chẵn và 23.2 lần khi từ d chẵn sang lẻ, trung bình chỉ tăng khoảng hơn 6 lần khi tăng d. - Số nút của Alpha-beta tăng chậm hơn rất nhiều lần so với Minimax. Tỉ số nút phải xét giữa hai giải thuật này càng cao khi d càng lớn. Công thức tính số nút cho thấy số nút phải xét khi dùng Alpha-beta ít hơn nhiều so với Minimax nhưng vẫn là hàm số mũ và vẫn dẫn tới bùng nổ tổ hợp. Thuật toán Alpha-beta hoàn toàn không chống được bùng nổ tổ hợp mà chỉ làm giảm tốc độ bùng nổ tổ hợp. Tuy trong thực tế số nút phải xét (lượng giá) thường nhiều hơn trong điều kiện lí tưởng nhưng nó vẫn đủ để tiết kiệm khá nhiều thời gian. Trong cùng một khoảng thời gian, thuật toán Alpha-beta có thể tìm đến độ sâu gấp hai lần độ sâu tìm kiếm bằng Minimax. Hình sau đây là đồ thị so sánh giữa hai thuật toán này [5]. Hình 2.10 : Khảo sát sự bùng nổ tổ hợp, Thuật toán Alpha-beta chỉ làm giảm sự bùng nổ tổ hợp chứ không chống được nó. Hệ số phân nhánh trong các đồ thị trên là 40. Tóm lại : Do bùng nổ tổ hợp quá lớn của cây trò chơi mà cả hai người chơi không thể (và không bao giờ) có thể tìm kiếm vét cạn (hết mọi khả năng). Do đó phương pháp tìm kiếm duy nhất là chỉ tìm kiếm đến một độ sâu giới hạn nào đó và chọn nước đi dẫn đến một thế cờ có lợi nhất cho mình. Do phải tính cả khả năng chống trả của đối phương nên ta không dùng được các thuật toán tìm kiếm thông thường. Phải dùng một thuật toán tìm kiếm riêng cho cây trò chơi. Đó là thuật toán Minimax và cải tiến của nó là thuật toán Alpha-beta. Tuy cả hai thuật toán đều không tránh được bùng nổ tổ hợp nhưng thuật toán Alpha-beta làm chậm bùng nổ tổ hợp hơn nên được dùng nhiều trong các trò chơi cờ. CHƯƠNG 3: ỨNG DỤNG 3.1 Phân tích bài toán 3.1.1 Trò chơi Trò chơi N quân hậu bắt nguồn từ bài toán rất nổi tiếng là Bài toán 8 con hậu: đặt lần lượt 8 con hậu lên bàn cờ quốc tế (kích thước 8x8) sao cho không có 2 con hậu nào khống chế lẫn nhau. Do vậy, người ta có khá nhiều cách định nghĩa về trò chơi N quân hậu, điển hình là 3 cách sau: Cho bàn cờ quốc tế có kích thước N x N, 2 người chơi lần lượt đặt từng quân hậu lên bàn cờ sao cho không có 2 quân hậu nào khống chế nhau. Người chơi nào không đặt được quân hậu lên bàn cờ nữa là người thua cuộc. Cho bàn cờ quốc tế có kích thước N x N, 2 người chơi lần lượt đặt từng quân hậu lên bàn cờ sao cho không có 2 quân hậu nào khống chế nhau cho đến khi không đặt được nữa. Mỗi quân hậu đặt lên bàn cờ sẽ khống chế các ô nằm trong 8 hướng đi của nó nếu ô đó còn chưa bị khống chế. Ai khống chế được nhiều ô hơn là người thắng cuộc. Cho bàn cờ quốc tế kích thước N x N. Người đi đầu tiên sẽ đặt a quân hậu lên bàn cờ. Người chơi thứ 2 tiếp tục đặt b con hậu lên bàn cờ (a > b và a + b ≤ N) sao cho không có 2 quân hậu nào khống chế lẫn nhau. Sau đó người chơi thứ nhất sẽ di chuyển các con hậu của mình để ăn các con hậu của đối phương, người chơi thứ 2 có nhiệm vụ phòng thủ, di chuyển các con hậu của mình để đối phương không bắt được. Sau k nước đi nếu người chơi thứ nhất ăn được hết b con hậu của đối phương thì người chơi thứ nhất thắng, ngược lại người chơi thứ 2 thắng. Sau khi cân nhắc, cách phát biểu trò chơi thứ 2 được chọn để tiến hành viết ứng dụng cho luận văn. Tuy nhiên, để cho trò chơi hấp dẫn hơn và công bằng hơn chúng ta bổ sung thêm một số luật chơi. Phát biểu trò chơi (bài toán) như sau: Cho bàn cờ có kích thước N x N (3 ≤ N ≤ 15), trên đó có sẵn m ô đá ( hay có thể hiểu là chướng ngại vật) (0 ≤ m ≤ (N - 2)2) nằm ở các vị trí ngẫu nhiên, các ô còn lại là ô trống. Hai người chơi lần lượt đặt từng con hậu lên bàn cờ sao cho không có 2 con hậu nào khống chế lẫn nhau. Hai con hậu khống chế nhau nếu chúng nằm trên đường đi của nhau và không có ô đá nào nằm trên đường đi ấy. Mỗi con hậu đặt lên bàn cờ sẽ khống chế các ô nằm trên 8 đường đi của nó nếu ô đó còn trống, chưa bị khống chế bởi con hậu nào khác. Trò chơi kết thúc khi không đối thủ nào đặt được quân hậu lên bàn cờ nữa. Người nào khống chế được nhiều ô hơn là người thắng cuộc. Hình 3.1 dưới đây minh họa hai trường hợp: Hai con hậu không khống chế nhau và hai con hậu khống chế nhau: Hình 3.1 (a) Hai con Hậu không khống chế nhau (b) Hai con Hậu khống chế nhau Trong hình (a) Con Hậu xanh ở vị trí (2,3) đặt trước do đó nó khống chế được 5 ô, con Hậu màu vàng đặt sau nên chỉ khống chế được 3 ô. 3.1.2 Cơ sở lý thuyết Theo như phát biểu trò chơi ở trên, ta có thể thấy trò chơi N quân hậu thuộc lớp các trò chơi đối kháng giữa hai người chơi. Cụ thể trò chơi này thuộc dạng trò chơi có tổng bằng không với hai người chơi (Two players, Zero-sum-game). Vì thế ta có thể áp dụng thuật toán tìm kiếm Minimax và thuật toán Alpha-beta trong trò chơi này. Mặt khác nếu viết chương trình để người chơi với người thì chỉ cần xây dựng các tập luật chơi để người chơi không phạm quy và kết thúc khi có người thắng. Tuy nhiên như vậy lại không ứng dụng và kiểm tra được thuật toán trong luận văn này. Vì vậy chúng ta sẽ viết chương trình cho Người chơi với Máy, trong trường hợp này ta phải tính toán như thế nào để khả năng máy tính thắng cao hơn người. Máy tính có lợi thế là khả năng tính toán nhanh, khả năng nhớ tốt gấp nhiều lần so với con người, vậy để máy tính thắng thì thật dễ, vấn đề là làm sao để máy có thể nghĩ được như người? Và có thể tính trước được ít nhất là 4 đến 5 nước.Vậy phải có thuật toán để máy có thể quét qua các phương án đi, và chọn phương án cuối cùng là tốt nhất sao cho máy tính có thể thắng. Trong ứng dụng này ta chọn thuật toán Minimax và thuật toán cải tiến Alpha-beta (chương 2) để cài đặt cho máy tính chơi. 3.2 Cài đặt chương trình Chương trình được cài đặt bằng ngôn ngữ C# (.NET Framework 2.0). Ngoài ra còn sử dụng thêm một số phầm mềm như: PowerCHM, Photoshop và phần mềm tạo file icon. 3.2.1 Cấu trúc chương trình và mối quan hệ giữa các lớp chính Chương trình được thiết kế theo mô hình Hướng đối tượng(Object-Oriented) để tiện cho việc cải tiến về sau. Do chương trình mới được phát triển nên cấu trúc còn đơn giản, chỉ có 3 lớp chính là các lớp Form1 (tên lớp mặc định do C# đặt cho form), lớp CBoard và lớp gameAI. Trong đó lớp gameAI là lớp được áp dụng thuật toán trong chương 2 của chúng ta. Mối quan hệ giữa 3 lớp thể hiện qua sơ đồ các lớp trong hình 3.2 như sau: 1 2 3 4 Hình 3.2: Sơ đồ thể hiện mối liên quan giữa 3 lớp chính. Trong đó: - Lớp Form1 có thuộc tính mb thuộc lớp CBoard. - Lớp CBoard có thuộc tính form thuộc lớp Form1. - Lớp CBoard có thuộc tính machine thuộc lớp GameAI. - Lớp GameAI có thuộc tính ownBoard thuộc lớp CBoard. Các lớp tương tác với nhau thông qua các bước sau: 1. Lớp Form1 truyền thông tin nhận được từ người chơi cho lớp CBoard, lớp CBoard lấy được thông tin thông qua thuộc tính form. 2. Lớp Cboard xử lý dữ liệu thu được từ lớp Form1 và truyền cho lớp GameAI, lớp GameAI thu được thông qua thuộc tính ownBoard . 3. Lớp GameAI sau khi nhận được thông tin sẽ xử lý và truyền lại cho lớp Cboard, lớp Cboard nhận được thông qua thuộc tính machine. 4. Lớp Cboard nhận được thông tin từ lớp GameAI, xử lý và truyền lại cho lớp Form1 thông qua thuộc tính mb. Lớp form1 xử lý lại thông tin và điều chỉnh giao diện của form. Sau đây chúng ta sẽ xem xét cấu trúc và nhiệm vụ của 3 lớp trên. 3.2.2 Lớp Form1 Lớp này thể hiện giao diện của trò chơi, làm nhiệm vụ giao tiếp với người chơi. Các thao tác chính của lớp này là: Nhận thông tin khởi tạo một ván chơi từ người sử dụng như: kích thước bàn cờ, trình độ của máy, số ô đá (hay vật cản) sử dụng, ai là người đi trước để cung cấp thông tin cho lớp CBoard khởi tạo một ván chơi mới. Ghi nhận thông tin về nước đi của người chơi mỗi khi người chơi nhấp chuột lên một ô trống rồi truyền cho lớp CBoard xử lý. Cập nhật nước đi của người và máy lên màn hình. Hiển thị các thông tin về trận đấu như điểm của các đối thủ, các nước đã đi, ai là người đang đi… Thể hiện 1 số hiệu ứng khi người dùng di chuyển chuột trên bàn cờ để tiện cho người chơi suy nghĩ, đánh giá. Ngoài ra còn thực hiện xuất các kết quả của các ván chơi ra một file Excel để tiện theo dõi lại sau nhiều ván chơi. Trong mục 3.3 chúng ta sẽ thấy được các thành phần cụ thể của lớp Form1. 3.2.3 Lớp CBoard Lớp CBoard đóng vai trò như một bàn cờ trong thực tế. Lớp này chứa các thông tin về bàn cờ: Một mảng 2 chiều lưu trữ trạng thái từng ô của bàn cờ. Kích thước bàn cờ, người đi trước, số ô đá trên bàn cờ, thời gian và trình độ suy nghĩ của máy, điểm của 2 đối thủ. Lưu trữ thông tin về nước đi hiện tại: ai đang đi, là nước đi thứ mấy… Các phương thức chính của lớp Cboard như sau: Khởi tạo một ván chơi mới. Kiểm tra một nước đi có hợp lệ hay không? Ghi nhận một nước đi. Thực hiện nước đi của người chơi. Yêu cầu máy thực hiện nước đi. 3.2.4 Lớp gameAI Có thể nói lớp gameAI là lớp trung tâm của các chương trình trò chơi đối kháng. Lớp này chứa các phương thức phục vụ cho việc quyết định đi một nước của máy. Sau đây chúng ta sẽ xem xét chi tiết các thuộc tính và phương thức của lớp này. Hình 3.3: Cấu trúc lớp gameAI Trong lớp gameAI có các thuộc tính đáng chú ý là: Mảng 2 chiều board[,] chứa trạng thái của bàn cờ hiện tại. board[i, j] = -100 nếu ô đó là ô đá. board[i, j] = -x tức là ô (i, j) chứa con hậu được đặt ở nước thứ x. board[i, j] = x nếu ô (i, j) bị khống chế bởi con hậu đặt ở nước thứ x. Mảng listCell[] chứa danh sách các ô sẽ bị khống chế nếu ta đặt con hậu ở một ô nào đó 2 mảng dx, dy thể hiện 8 hướng đi có thể của quân hậu. ownBoard là một thể hiện( đối tượng) của lớp cBoard, chứa bàn cờ chúng ta đang chơi và các thông tin về nó như kích cỡ, trình độ máy v.v….. ownedCell: ghi nhận số ô đã bị khống chế trên bàn cờ totalCell: tổng số ô trống trên bàn cờ lúc đầu = tổng số ô – số ô đá. startTime: ghi nhận thời gian bắt đầu suy nghĩ của máy. resX, resY: ghi lại nước đi máy sẽ đi. bestValue ghi nhận giá trị tốt nhất nếu thực hiện nước đi (resX, resY). Các phương thức của lớp gameAI Lớp chỉ có một phương thức có thuộc tính public là phương thức requestMove(). Phương thức này có đầu vào là một trạng thái của bàn cờ, trả lại giá trị (resX, resY) là ô mà máy sẽ đặt quân hậu. Để tìm kiếm được nước đi tốt nhất, phương thức requestMove sử dụng các phương thức hỗ trợ là: AlphaBeta: thực hiện tìm kiếm theo thuật toán Alpha-beta. Minimax: thực hiện tìm kiếm theo thuật toán Minimax. Hàm eval: lượng giá thế cờ hiện tại. Phương thức heuristicGenerateMove: sinh heuristic các nước đi có thể. Phương thức doMove: thử thực hiện một nước đi được sinh bởi phương thức heuristicGenerateMove. - Phương thức remove: bỏ thực hiện nước đi đã thử (như đã nói trong thuật toán ở chương 2). Sau đây chúng ta sẽ xem xét các phương thức của lớp gameAI một cách chi tiết. Phương thức Minimax Function Minimax(depth): integer; Begin If (đã quá thời gian suy nghĩ) then return –INFINITY; {dừng không duyệt nữa} if (depth=0) or (không thể đi được nước nào nữa) then return eval(depth); {lượng giá ngay thế cờ hiện tại và kết thúc} best = -INFINITY; pMove = heuristicGenerateMove; {sinh các nước đi có thể} while (còn lấy được nước đi m trong pMove)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 begin best := value; if (đây là nước đi đầu tiên của máy) then cập nhật nước đi resX, resY; end; end; return best; End; Phương thức Alphabeta Function AlphaBeta(Alpha, beta, depth): integer; Begin If (đã quá thời gian suy nghĩ) then return –INFINITY; {dừng không duyệt nữa} if (depth=0) or (không thể đi được nước nào nữa) then return eval(depth); {lượng giá ngay thế cờ hiện tại và kết thúc} best = -INFINITY; pMove = heuristicGenerateMove; {sinh các nước đi có thể} while (còn lấy được nước đi m trong pMove) and (best < beta) do begin if (best > Alpha) then Alpha := best; Thực hiện nước đi m; value = -AlphaBeta(-beta, -Alpha, depth - 1); Bỏ thực hiện nước đi m; if (value > best) then begin best := value; if (đây là nước đi đầu tiên của máy) then cập nhật nước đi resX, resY; end; end; return best; End; Phương thức sinh nước đi heuristicGenerateMove Trong chương 2 khi đánh giá thuật toán Alpha-beta ta đã nhận xét: thuật toán hoạt động càng hiệu quả khi sự thu hẹp cửa sổ Alpha và Beta càng nhanh. Cửa sổ này được thu hẹp một bước khi gặp một giá trị mới tốt hơn giá trị cũ. Khi gặp giá trị tốt nhất thì cửa sổ này thu hẹp nhất. Do đó nếu càng sớm gặp giá trị tốt nhất thì cửa sổ càng chóng thu hẹp. Như vậy phải làm sao cho các nút ở lá được sắp xếp theo trật tự từ cao xuống thấp. Trật tự này càng tốt bao nhiêu thì thuật toán chạy càng nhanh bấy nhiêu. Tuy vậy, do giới hạn về thời gian tính toán và sự bùng nổ tổ hợp, ta không thể liệt kê hết các nút lá để sắp xếp được. Do đó, ta chỉ áp dụng cách sinh các nước đi theo một tiêu chuẩn mà ta cho là tốt, phù hợp với đặc điểm trò chơi đang xét như sau: Ta thấy, nếu không có ô đá thì nước đi đầu tiên vào ô trung tâm bao giờ cũng chiếm được nhiều ô trống nhất. Do đó, ta sẽ ưu tiên xét các ô theo thứ tự từ ô trung tâm tỏa ra các ô xung quanh (tất nhiên là trừ ô đá!) Một cách cảm tính, ta có thể nhận thấy đi vào các ô có số ô trống trong 8 ô xung quanh nó lớn thì có vẻ có lợi hơn. Như vậy ta có thể sinh các nước đi sắp tới theo hướng heuristic như sau: tìm tất cả các ô còn trống. với mỗi ô, đếm số ô trống xung quanh nó, cho tất cả vào một danh sách. Tiến hành sắp xếp danh sách theo thứ tự giảm dần của số ô trống xung quanh. Nếu hai ô có cùng số ô trống xung quanh thì ưu tiên ô gần trung tâm hơn. Giải thuật được cài đặt như sau: Procedure generateHeuristicMove(var pMove); begin for i := 1 to boardSize do for j := 1 to boardSize do if board[i, j] = 0 then {nếu ô (i, j) còn là ô trống} begin k := số ô trống xung quanh ô (i, j); đặt bộ 3(i, j, k) vào mảng pMove; end; sắp xếp mảng pMove theo tiêu chí ở trên; End; Hàm đếm số ô trống xung quanh ô (i, j) được thực hiện đơn giản, chỉ cần kiểm tra 8 ô xung quanh nó. Lưu ý trường hợp ô (i, j) ở biên của bàn cờ, ta phải sử dụng kỹ thuật lính canh: đặt bên ngoài biên của bàn cờ là các ô đá để tránh trường hợp tràn mảng. Phương thức lượng giá eval Do đặc điểm của trò chơi, hàm lượng giá được thực hiện như sau: Ta chỉ việc tính hiệu số giữa số ô người chơi chiếm giữ và số ô máy chiếm giữ. Tham số depth được đưa vào để biết được đối thủ nào gọi hàm lượng giá này. Function eval(depth): integer; begin for i := 1 to boardSize do for j := 1 to boardSize do if ô (i,j) bị người chơi chiếm then tăng số ô người chiếm lên 1 else if ô (i,j) bị máy chiếm then tăng số ô máy chiếm lên 1; if (depth mod 2 = 0) {nếu người chơi gọi hàm lượng giá} return (số ô máy chiếm – số ô người chiếm) else return (số ô người chiếm – số ô máy chiếm); End; Phương thức doMove Phương thức doMove nhận tham số đầu vào là (i, j): chỉ số ô sẽ đi và x là số thứ tự của nước đi. Phương thức thực hiện như sau: đánh dấu ô sẽ đi là –x. Từ ô (i, j) ta đi lần lượt theo 8 hướng có thể đến khi nào ra biên hoặc gặp ô đá. Với mỗi ô trên đường đi, nếu còn là ô trống thì đánh dấu ô đó mang giá trị x. Trong quá trình đó, cập nhật lại giá trị số ô đã bị chiếm. Phương thức remove Phương thức remove có tham số đầu vào là x: số thứ tự của nước đi. Phương thức thực hiện bỏ nước đi được tạo bởi hàm doMOVE. Phương thức đơn giản chỉ quét các ô trên bàn cờ, nếu giá trị tuyệt đối của ô đó bằng x thì ta gán lại giá trị bằng 0, đồng thời giảm giá trị số ô bị chiếm đi 1. Mã nguồn lớp gameAI: using System; using System.Collections.Generic; using System.Text; using System.Drawing; using System.Collections; namespace n_queens { // xay dung lop diem moi dua vao lop point da co class myPoint { public Point pt; int val; public myPoint(int x, int y, int startVal) { pt = new Point(x, y); val = startVal; } //Tính khoang cách giữa điểm a và điểm trung tâm static double distance(myPoint a, double mid) { return Math.Sqrt(Math.Pow(a.pt.X - mid, 2)+Math.Pow(a.pt.Y - mid, 2)); } // Phương thức tĩnh so sánh khoang cach giua hai diem voi o trung tam public static int compare(myPoint a, myPoint b, float mid) { if (a.val > b.val) return -1; else if (a.val < b.val) return 1; else { double d1 = distance(a, mid); double d2 = distance(b, mid); if (d1 < d2) return -1; else if (d1 > d2) return 1; else return 0; } } } class CompareInv : IComparer// lop Icomparer co 1 phuong thuc compare de so sanh 2 doi tuong { int middlePoint; public CompareInv(int middle) //ham tao { middlePoint = middle; } public int Compare(object obj1, object obj2)//so sanh 2 đoi tuong { myPoint a, b; a = (myPoint)obj1; b = (myPoint)obj2; return myPoint.compare(a, b, middlePoint); } } class gameAI {// khai bao đoi tuong thuoc lop CBoard CBoard ownBoard; /// /// mang chưa trạng thái của ban co /// int[,] board = new int[17, 17]; //dinh nghia 8 huong /// /// thể hiện 8 hướng đi của quân hậu /// int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 }; /// /// int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 }; /// /// Thời gian bắt đầu /// long startTime; /// /// Giá trị thuật toán trả về /// int resX, resY, bestValue; /// /// Số ô đã chiếm /// int ownedCell, totalCell;// so o bi chiem va so o trong ban dau CompareInv compInv; //doi tuong thuoc lop CompareInv /// /// danh sách các ô có thể bị chiếm /// Point[] listCell = new Point[17 * 17]; /// /// hàm tạo của lớp /// public gameAI(CBoard mb) // ham tao { ownBoard = mb; totalCell = mb.boardSize * mb.boardSize - mb.nStone; } /// /// Phuong thuc Sinh nước đi /// void heuristicGenerateMove(ArrayList pMove) { int i, j, k, c; ArrayList al = new ArrayList(); for (i = 1; i <= ownBoard.boardSize; i++) for (j = 1; j <= ownBoard.boardSize; j++) if (board[i, j] == 0) { //Dem o trong gan ke voi o [i,j] c = 0; for (k = 0; k < 8; k++) if (board[i + dx[k], j + dy[k]] == 0) c++; al.Add(new myPoint(i, j, c)); } al.Sort(compInv);// sap xep cac doi tuong trong danh sách al foreach (myPoint p in al) { pMove.Add(p.pt); } } /// /// Thuc hien di chuyen ban co /// /// /// void doMove(Point start, int ord) { int u = start.X, v = start.Y; int i, j; board[u, v] = -ord;// danh dau o [u,v] da di ownedCell++;// so o bi chiem // danh dau cac o bi chiem ngang, doc, cheo i = u - 1; j = v; while ((i >= 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } i--; } i = u + 1; j = v; while ((i -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } i++; } i = u; j = v - 1; while ((j >= 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j--; } i = u; j = v + 1; while ((j -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j++; } i = u - 1; j = v - 1; while ((i >= 1) && (j >= 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j--; i--; } i = u + 1; j = v + 1; while ((i -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j++; i++; } i = u - 1; j = v + 1; while ((i >= 1) && (j -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j++; i--; } i = u + 1; j = v - 1; while ((i = 1) && (board[i, j] > -100)) { if (board[i, j] == 0) { board[i, j] = ord; ownedCell++; } j--; i++; } } /// /// Tro lai buoc di chuyen /// /// /// void remove(Point pt, int ord) { for (int i = 1; i <= ownBoard.boardSize; i++) for (int j = 1; j <= ownBoard.boardSize; j++) if (Math.Abs(board[i, j]) == ord) { board[i, j] = 0; ownedCell--; } } /// /// Phuong thuc Uoc luong gia tri cua nuoc di /// /// /// int eval(int ord) { int countOdd = 0, countEven = 0; for (int i = 1; i <= ownBoard.boardSize; i++) for (int j = 1; j <= ownBoard.boardSize; j++) if ((board[i, j] != 0) && (board[i, j] > -100) && (board[i, j] % 2 == 0)) countEven++;//chan else if (board[i, j] % 2 != 0) countOdd++; // le if (ownBoard.playerMove % 2 == 0) { if (ord % 2 == 0) return countEven - countOdd; else return countOdd - countEven; } else { if (ord % 2 == 0) return countOdd - countEven; else return countEven - countOdd; } } /// /// thu tuc Alpha-beta /// /// /// /// /// int AlphaBeta(int Alpha, int beta, int depth) { // het thoi gian suy nghi if (DateTime.Now.Ticks - startTime >= ownBoard.limitTime * 10000000) return -10000; if ((depth == 0) || (totalCell == ownedCell)) return eval(depth); else { ArrayList pMove = new ArrayList(); Point pt; int best, value; best = -10000; //best = -Infinitive heuristicGenerateMove(pMove); IEnumerator myEnumerator = pMove.GetEnumerator(); while (myEnumerator.MoveNext() && (best < beta)) { if (best > Alpha) Alpha = best; pt = (Point)myEnumerator.Current; doMove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); value = -AlphaBeta(-beta, -Alpha, depth - 1); remove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); if ((Math.Abs(value) != 10000) && (value > best)) { best = value; if (depth == ownBoard.machineLevel) { resX = pt.X; resY = pt.Y; } } } return best; } } /// /// Thu tuc Minimax /// int Minimax(int depth) { if (DateTime.Now.Ticks - startTime >= ownBoard.limitTime * 10000000) return -10000; if ((depth == 0) || (totalCell == ownedCell)) return eval(depth); else { ArrayList pMove = new ArrayList(); Point pt; int best, value; best = -10000; //best = -Infinitive heuristicGenerateMove(pMove); IEnumerator myEnumerator = pMove.GetEnumerator(); while (myEnumerator.MoveNext()) //&& (best < beta)) { pt = (Point)myEnumerator.Current; doMove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); value = -Minimax(depth - 1); remove(pt, ownBoard.nMove + ownBoard.machineLevel - depth + 1); if ((Math.Abs(value) != 10000) && (value > best)) { best = value; if (depth == ownBoard.machineLevel) { resX = pt.X; resY = pt.Y; } } } return best; } } /// /// Yêu cầu nước đi /// public Point requestMove(int[,] mb) { board = mb; compInv = new CompareInv((ownBoard.boardSize + 1) / 2); ownedCell = ownBoard.playerScore + ownBoard.machineScore; startTime = DateTime.Now.Ticks; bestValue = Minimax(ownBoard.machineLevel);//AlphaBeta(-10000, 10000, ownBoard.machineLevel); return new Point(resX, resY); } } } 3.3 Một số giao diện và kết quả chạy chương trình Màn hình ban đầu như sau: Hình 3.4: Màn hình ban đầu của trò chơi Trong đó có các tùy chọn để tạo một ván chơi mới Hình 3.5 Các tùy chọn của một ván chơi Sau khi chọn xong các thông số người chơi ấn vào nút “Bắt đầu chơi” để chơi. Màn hình trò chơi bắt đầu: Hình 3.6: Màn hình sau bắt đầu chơi Bàn cờ sau 2 nước đi: Hình 3.7: Bàn cờ sau 2 nước đi. Ô màu xanh là ô mà máy chiếm được sau 1 nước đi của nó, Ô mày vàng là ô mà người chiếm được sau 1 nước đi của người. Còn các ô còn lại là chưa bị chiếm. Sau 2 nước đi kết quả được thể hiện trong hộp trạng thái như sau: Hình 3.8: Kết quả sau 2 nước đi Trong đó thể hiện số điểm của hai đối thủ, đến lượt ai đang chơi và danh sách các nước đi cụ thể của 2 đối thủ. KẾT LUẬN Với mục tiêu đề ra của luận văn là tìm hiểu và nghiên cứu về thuật toán tìm kiếm đối kháng Minimax, các cải tiến của nó và ứng dụng trong trò chơi có tổng bằng không, các kết luận chính đã đạt được của luận văn có thể tóm tắt như sau: Đã nhắc lại một cách tổng quan về vấn đề tìm kiếm trong đó có phát biểu bài toán tìm kiếm và giới thiệu các kỹ thuật tìm kiếm cơ bản như tìm kiếm không có thông tin, tìm kiếm có thông tin và tìm kiếm đối kháng. Tìm hiểu về đặc điểm của trò chơi có tổng bằng không trong lĩnh vực Lý thuyết trò chơi. Đồng thời đưa ra mô hình toán học của trò chơi có tổng bằng không và phát biểu định lý minimax áp dụng cho các trò chơi có tổng bằng không. Đã nghiên cứu giải thuật tìm kiếm Minimax và giải thuật cải tiến của nó là giải thuật Alpha-beta cho các trò chơi có tổng bằng không. Cài đặt được giải thuật cho trò chơi có tổng bằng không với hai người chơi trong bài toán xếp các quân Hậu lên bàn cờ. Kết quả của việc cài đặt là chương trình trò chơi xếp các quân Hậu giữa người và máy tính. Trong đó thuật toán được cài đặt cho việc suy nghĩ của Máy tính. Mặc dù có nhiều cố gắng nhưng chắc chắn rằng các kết quả đã cài đặt được không tránh khỏi những thiếu sót và hạn chế, hy vọng rằng trong tương lai vấn đề này sẽ được nghiên cứu sâu hơn và phát triển với thuật toán được cải tiến tốt hơn, chẳng hạn chúng ta có thể đi vào nghiên cứu vấn đề song song hóa thuật toán trên. Trên cơ sở các kết quả đã đạt được, chúng ta có thể phát triển những nghiên cứu tiếp về thuật toán Alpha- Beta song song [16]. Hơn nữa, chúng ta có thể nghĩ đến việc triển khai những nghiên cứu về ứng dụng của những kết quả này trong các lĩnh vực khác của xã hội, đặc biệt là kinh tế. Tài liệu tham khảo Tiếng Việt Nguyễn Đình Hóa (2004), Cấu trúc dữ liệu và Thuật giải, NXB ĐHQGHN. Đỗ Xuân Lôi (1998), Cấu trúc dữ liệu và giải thuật, NXB Khoa học kỹ thuật, Hà Nội. Nguyễn Đức Nghĩa - Nguyễn Tô Thành (1997), Toán rời rạc, NXB Giáo dục. Nguyễn Thanh Thủy (2007), Trí tuệ nhân tạo: Các phương pháp giải quyết vấn đề và kỹ thuật xử lý tri thức, NXB Khoa học kỹ thuật. Đỗ Trung Tuấn (1997), Trí tuệ nhân tạo, NXB Giáo dục. Đinh Mạnh Tường (2001), Cấu trúc dữ liệu & Thuật toán, NXB Khoa học kĩ thuật, Hà nội. Đinh Mạnh Tường (2002), Trí tuệ nhân tạo, NXB Khoa học kỹ thuật, Hà nội. Tiếng Anh Jessica Billings (2008), The Minimax Algorithm, CS 330. Jeroen W.T.Carolus (2006), Alpha-beta with Sibling Prediction Pruning in Chess, Faculteitder Natuurwetenschappen, Wiskundeen Informatica Universty of Amsterdam Netherlands. Michael A. Goodrich (2007), Proof of the Minimax Theorem. Heylighen (1993), Zero sum games – Principia Cybernetica Web. R. D. Luce and H. Raiffa (1957), Games and Decisions, John Wiley, New York. George Luger (2002), Artificial Intelligence: Structures and Strategies for Complex Problem Solving, Addison-Wesley Publisher. Stuart J.Russell and Peter Norvig (2003). Artificial Intelligence: A Modern Approach, Prentice Hall, Second edition, p55-p122. Ken Thompson (2008), Play chess with God, Bell Labs, Arun Pratik. Vladan V. Vuˇckovi´c (2007), The method of the chess search algorithms Parallelization using two-Processor distributed system, p175-p188.