Code đồ án game cờ tướng sử dụng thuật toán minimax , lập trình bằng JS, PHP + file báo cáo

Code đồ án game cờ tướng sử dụng thuật toán minimax , lập trình bằng JS, PHP + file báo cáo

Trong 2 người chơi thì một người gọi là người chơi cực đại (Max) và đối thủ của họ là người chơi cực tiểu (Min).Cả 2 đấu thủ đều cố gắng đi những nước thế nào để điểm tuyệt đối của mình lớn hơn hay cao nhất có thể.Tức là người chơi Max sẽ tìm cách làm điểm của mình cao hơn và làm điểm của đối thủ bớt âm hơn (giảm về trị số) .Trong khi người chơi Min thì ngược lại, sẽ cố gắng làm cho điểm của mình âm hơn và làm cho điểm của đối thủ giảm.

Giải thuật tìm kiếm Min-Max  được sử dụng để xác định tất cả những “diễn biến” tiếp theo của trò chơi cho đến tầng được yêu cầu.Điểm số ban đầu được gán cho lá, sau đó  bằng cách lượng giá các nước đi, điểm số được gán cho các tầng ở trên qua giải thuật Min Max, thuật giải thực hiện một lát cắt cho trước và tính điểm trên đó.

Ý tưởng cơ bản của thuật giải Min-Max theo đệ quy

Nếu mức đang xét là người chơi cực tiểu thì áp dụng thuật toán Min-Max cho các con của nó.Lưu kết quả là giá trị nhỏ nhất.

Nếu mức đang xét là người chơi cực đại thì áp dụng thuật toán Min-Max cho các con của nó.Lưu kết quả là giá trị lớn nhất.

Nếu mức đang xét là lá (tầng cuối cùng của cây tìm kiếm), 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ả

Mã 1

MinMax(x)

{ // x là nút muốn tính điểm

If  x is a leaf

Return score of  x;

Else

          If  x in a minNode

                     For allChildren of  x : v1,…,vn

Return   min {MinMax(v1),…,Min-Max(vn)}

Else

                     For allChildren of  x : v1,…,vn

Return   max {Min-Max(v1),…,Min-Max(vn)}

}

Tuy nhiên trên một cây có kích thước lớn thì ta không thể tìm hết tất cả các nút mà ta chỉ giới hạn trong một số tầng của cây và xem như đây là mô phỏng gần đúng của một cây Min-Max (chưa biết) bằng cách gán trọng số cho các lá của nó.Trọng số ở đây là trọng số không còn chính xác tuyệt đối mà là ước lượng.Trọng số nhận được theo cách này gọi là được tính toán với sự giúp đỡ của hàm lượng giá, hàm này được xây dựng vởi người dùng dựa trên sự hiểu biết và kinh nghiệm.

Mã 2

function MinMax (pos, depth): integer;

{

   if depth = 0 then        //Đạt đến giới hạn

      MinMax = Eval (pos) //Tính giá trị thế cờ pos

   else

          {

                     Gen (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

                     {

                      pos = Tính thế cờ mới nhờ đi m;

                     value = MinMax (pos, depth-1); // Tính điểm của pos

                     }

          }

}

Tham số depth – độ sâu tìm kiếm giúp ta biết phải tìm đến đâu, tham số pos cho biết thế cờ hiện tại để từ đó biết cách tính tiếp. Giá trị trả về của hàm chính là điểm của thế cờ pos. Hàm lượng giá Eval sẽ đánh giá được chất lượng của thế cờ pos hiện tại. Các thế cờ con pos’  là các thế cờ được tạo ra từ pos bằng cách đi một nước đi hợp lệ x nào đó. Do đó ta phải có các lệnh thực hiện đi quân để đến các thế cờ mới. Để biết từ thế cờ pos có thể đi được những nước nào, ta dùng một thủ tục Gen có tham số là thế cờ cha pos. Thủ tục này sẽ cất các thế cờ con pos’ đó vào bộ nhớ (dạng danh sách). Việc tiếp theo là ta lấy từng thế cờ đó ra và áp dụng tiếp thủ tục MinMax cho nó để tính điểm value của nó.

Mã 3

function MinMax (pos, depth): integer;

{

   if  depth = 0 then

           MinMax = Eval (pos) // Tính giá trị thế cờ pos

   else

          {         best = -INFINITY;

                     Gen (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

                     {

                        pos = Tính thế cờ mới nhờ đi m;

                        value = -Minimax (pos, depth – 1);

                         if value > best then best = value;

                     }

            MinMax = best;  //Trả về giá trị tốt nhất

}

}

Thông thường, 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 MinMax 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 MinMax 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 MinMax bỏ các tham số pos như sau:

Mã 4

function MinMax (depth): integer;

{

   if depth = 0 then MinMax = Eval // Tính thế cờ pos trong biến toàn cục

   else

{

           best = -INFINITY;

            Gen; // Sinh ra mọi nước đi từ thế cờ pos

              while còn lấy được một nước đi m do

                     {

                      thực hiện nước đi m;

                      value = -MinMax (depth – 1);

                      bỏ thực hiện nước đi m;

                       if value > best then best = value;

                     }

             MinMax = best;

          }

}