Tài liệu Phát triển game cờ gánh

ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA KHOA HỌC & KỸ THUẬT MÁY TÍNH LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC PHÁT TRIỂN GAME CỜ GÁNH GVHD: Ths Vương Bá Thịnh TP. HỒ CHÍ MÍNH, THÁNG 06/2019 LỜI CAM ĐOAN Nhóm báo cáo luận văn xin cam đoan rằng, ngoại trừ kết quả tham khảo từ các công trình khác đã được ghi rõ trong luận văn, các nội dung được trình bày trong luận văn này là do chính chúng tôi thực hiện và chưa có nội dung nào được nộp để lấy bằng cấp ở một trường khác. TPHCM, ngày 12 tháng 04 năm 2019 2 LỜI CẢM ƠN Để có thể hoàn thành bài luận văn này, nhóm nghiên cứu đã phải trải qua quá trình đào tạo bài bản, kỹ lưỡng của các Thầy Cô Giảng Viên, Cán Bộ trong Khoa Khoa Học và Kỹ Thuật Máy Tính, trường Đại Học Bách Khoa Thành Phố Hồ Chí Minh. Hành trình trải qua trong suốt khóa học của nhóm chúng em là hành trình trải qua nhiều thử thách và gian nan. Đã có lúc Thầy Cô vô cùng nghiêm khắc và kỷ luật với những hành vi sai trái và sự thiếu hiểu biết của chúng em. Nhưng chúng em hiểu điều đó xuất phát từ sự quan tâm và tình yêu thương của Thầy Cô. Đây là món quà vô cùng quý báu để từng thành viên trong nhóm có thể trưởng thành hơn, tích lũy được nhiều kiến thức, kinh nghiệm cho con đường tương lai. Chúng em sẽ không thể quên được những chỉ dẫn tận tình, động viên và tình cảm ấm áp của Thầy Cô dành cho từng thành viên. Cả nhóm không thể hoàn thành khóa học nếu không có những điều này. Tất cả thành viên trong nhóm nghiên cứu chân thành cảm ơn quý Thầy Cô đã dìu dắt chúng em trong suốt chặng đường vừa qua. Nhóm nghiêm cứu vô cùng biết ơn Thầy Vương Bá Thịnh đã giảng dạy cho chúng em 2 môn có ý nghĩa quan trọng, làm tiền đề cho luận văn này đó là Trí tuệ nhận tạo và Lập trình game. Đồng thời Thầy cũng là người trực tiếp hướng dẫn cả nhóm hoàn thành đề tài luận văn này. Cả nhóm xin hứa với quý Thầy Cô, sau khi ra trường chúng em sẽ là những công dân tử tế, có tri thức, có trình độ, sẽ vận dụng tất cả những kiến thức tốt đẹp mà Thầy Cô đã truyền dạy để góp phần xây dựng tổ quốc nói riêng và thế giói nói chung ngày một tốt đẹp hơn. Chúng em xin hứa! Nhóm nghiên cứu 3 TÓM TẮT Cách mạng công nghiệp 4.0 (CMCN 4.0) đã , đang và sẽ diễn ra với tốc độ nhanh chóng. Tác động mạnh mẽ của nó làm thay đổi tất cả mọi mặt của đời sống xã hội con người, về cả vật chất lẫn tinh thần. Đây là thời điểm vô cùng thách thức và cũng đầy cơ hội cho đất nước và con người Việt Nam. Đặc biệt là ngành Khoa Học Và Kỹ Thuật Máy Tính, càng phải là ngọn cờ đi đầu để nghiên cứu và ứng dụng các thành tựu công nghệ của cuộc CMCN 4.0 vào đời sống trong mọi lĩnh vực của xã hội. Việc thành hay bại sẽ quyết định trực tiếp vào khả năng Việt Nam có thể sánh vai với các cường quốc Năm Châu hay không. Trí tuệ nhân tạo (AI) là một trong những lĩnh vực quan trọng nhất của cuộc CMCN 4.0. Con người đã có thể tạo ra được AI có khả năng đánh bại con người trong một số lĩnh vực. Một số ví dụ cụ thể là:  Ngày 06/08/2018 đã đánh dấu một bước tiến lớn với ngành công nghệ AI của nhân loại, khi trí tuệ nhân tạo OpenAI của Elon Musk đã chính thức đánh bại, nói đúng hơn là “nghiền nát” 5 game thủ Dota 2 chuyên nghiệp gồm Fog, Merlini, Blitz, Capitalist và MoonMeander.  Ngày 24/1/2019 Trí tuệ nhân tạo dựa trên DeepMind của Google được ra đời mang tên AlphaStar đã đánh bại 2 game thủ Starcraft II chuyên nghiệp TLO và MaNa với tỷ số cách biệt 10-1. Nhóm nảy sinh ý tưởng về việc áp dụng AI vào trong các game trí tuệ mang tính giải trí đang thịnh hành tại Việt Nam như: Cờ Tướng , Cờ Vua , Cờ Vây, Cờ Gánh… Sau khi xem xét kỹ lưỡng, nhóm quyết định chọn game Cờ Gánh làm đề tài nghiên cứu vì mức độ phổ biến, tính đơn giản của nó, dễ tiếp cận mọi người và đề tài nghiên cứu AI về game Cờ Gánh vẫn còn khá mới mẻ Nội dung báo cáo sẽ trình bày nghiên cứu các AI sử dụng giải thuật cơ bản đến các AI sử dụng những giải thuật nâng cao. Cụ thể là 2 loại AI:  MiniMax  Monte Carlo Tree Search Với mỗi loại AI sẽ có bảng đánh giá năng lực của từng loại. Và cuối cùng là tổng kết, so sánh, đánh giá cả 2. MỤC LỤC 4 Phần 1 - Tổng quan..........................................................................................................7 Phát biểu vấn đề:.............................................................................................................7 Mục tiêu đề tài nghiên cứu:.............................................................................................7 Phần 2 - Cơ sở lý thuyết chung.......................................................................................8 1. Giới thiệu:................................................................................................................... 8 1.1. Board Game.........................................................................................................8 1.2. Cờ Gánh...............................................................................................................8 2. Luật chơi:.................................................................................................................... 9 3. Lý thuyết:..................................................................................................................11 3.1. Phân tích trò chơi...............................................................................................11 3.2. Không gian trạng thái của trò chơi.....................................................................11 3.3. Hệ số phân nhánh...............................................................................................11 3.4. Mạng nơron nhân tạo (Neural Networks)...........................................................12 3.4.1. Mạng nơron nhân tạo (Neural Networks) là gì?..........................................12 3.4.2. Một số kiểu Neural Networks.....................................................................13 3.5. AI trong game Cờ Gánh.....................................................................................16 3.6. Mô hình thiết kế.................................................................................................16 3.7. Dòng điều khiển.................................................................................................17 Phần 3 - Mô hình trí tuệ nhân tạo MiniMax................................................................19 1. Cơ sở lý thuyết:.........................................................................................................19 1.1. Hàm lượng giá...................................................................................................19 1.2. Hàm đánh giá tuyến tính có trọng số..................................................................20 1.3. Chọn các tham số...............................................................................................21 2. Hiện thực MiniMax:..................................................................................................21 Phần 4 - Mô hình trí tuệ nhân tạo Monte Carlo Tree Search.....................................26 1. Cơ sở lý thuyết:.........................................................................................................26 1.1. Bước lựa chọn:...................................................................................................28 5 1.2. Bước mở rộng:...................................................................................................29 1.3. Bước mô phỏng:.................................................................................................30 1.4. Bước truyền ngược:............................................................................................31 1.5. Lựa chọn bước di chuyển:..................................................................................31 2. Hiện thực:.................................................................................................................32 Phần 5: Thiết kế UI........................................................................................................34 1. Giao diện màn hình khởi động của Game:................................................................34 2. Giao diện khi vào chơi Game:...................................................................................35 3. Giao diện Setting Game:...........................................................................................36 Phần 6 - Kiểm chứng và đánh giá giải thuật................................................................37 Phần 7 - Tổng kết...........................................................................................................39 1. Đánh giá kết quả:......................................................................................................39 2. Đóng góp của luận văn:............................................................................................39 3. Hướng phát triển:......................................................................................................39 3.1. Các cải tiến có thể được thêm vào MiniMax......................................................40 3.2. Các cải tiến có thể được thêm vào MCTS..........................................................41 3.3. Một số hướng mở rộng trong tương lai:.............................................................42 DANH SÁCH HÌNH VẼ................................................................................................43 DANH SÁCH BẢNG VÀ BIỂU ĐỒ.............................................................................44 Tài liệu tham khảo.........................................................................................................45 Phụ Chương 1: Giải thuật Minimax.............................................................................47 Phụ Chương 2: Giải thuật MCTS.................................................................................49 Phần 1 - Tổng quan Phát biểu vấn đề: 6 Theo sự phát triển của thời đại, các nhu cầu của con người ngày càng nâng cao để phục vụ cho cuộc sống. Game là một loại hình giải trí cực kì phổ biến ở thời điểm hiện tại và ngày càng phát triển đa dạng về thể loại. Trong đó Board game là thể loại rất dễ tiếp cận với mọi người, dễ chơi, phù hợp với mọi lưới tuổi, nên chúng em đã chọn phát triển 1 game Board game có tên là: Cờ gánh. Cờ gánh là một trò chơi dân gian ở Việt Nam, rất được ưa chuộng, khá hay và thú vị. Nó đã có khá lâu đời, với mong muốn, mang lại một trò chơi, đơn giản, thú vị và cải biến thêm một chút về luật chơi, dựa trên luật chơi có sẵn, nhóm mong là trò chơi này sẽ tạo hứng thú cho người chơi. Mục tiêu đề tài nghiên cứu: Tạo ra AI có thể hiểu luật chơi và thi đấu cờ với người chơi. Tìm cách thắng được nhiều điểm nhất có thể. Kèm theo đó AI phải: -Luôn luôn đánh đúng theo luật của trò chơi. -Tìm cách đi hiệu quả dựa trên các tiêu chí cho trước. 7 Phần 2 - Cơ sở lý thuyết chung 1. Giới thiệu: 1.1. Board Game Board Game bao gồm một bề mặt chơi (board) được chia thành các lĩnh vực được điền bởi một tập hợp các phần tử di động. Một cách phổ biến nhất, các phần được liên kết trực tiếp với người chơi, trong khi bề mặt chơi thể hiện một môi trường vượt ra khỏi tầm kiểm soát trực tiếp của người chơi. Người chơi điều động các phần tử của họ trên bề mặt chơi trong một nỗ lực để nắm bắt các phần của người chơi khác, đạt được một mục tiêu, giành quyền kiểm soát lãnh thổ, hoặc có được một số mặt hàng có giá trị. Mối quan tâm chính của người chơi trong các trò chơi này là phân tích các mối quan hệ hình học giữa các phần. 1.2. Cờ Gánh Bàn cờ là một bề mặt phẳng có 25 điểm nằm tại giao điểm của một lưới vuông 5 nhân 5 như trên hình vẽ bên phải. Các đường kẻ nằm ngang, thẳng đứng hoặc đường chéo, được vẽ trên bàn cờ như hình vẽ bên dưới, thể hiện các đường di chuyển được phép của các quân cờ. Tại xuất phát điểm, các quân cờ của hai người chơi được bố trí ở các điểm nằm rìa ngoài của bàn cờ như trên hình vẽ bên dưới. Bàn cờ gánh có 16 quân chia làm hai màu cho hai người chơi. Trong bàn cờ này, phe màu xanh có 8 quân và phe màu đỏ có 8 quân được sắp như hình vẽ bên dưới. Mục tiêu của mỗi người chơi là ăn các quân cờ của đối phương. Trận cờ kết thúc khi: + Một người chơi không còn con cờ nào trên bàn, thì người kia sẽ chiến thắng + Hoặc hai người đi đến một lúc nào đó (thỏa số bước quy định ban đầu, ví dụ 200 bước đi mà vẫn chưa phân thắng thua) thì ta sẽ đếm số cờ còn lại trên bàn cờ, người chơi nào còn nhiều cờ hơn, thì người đó sẽ chiến thắng. 8 Hình 1 Hình ảnh một bàn cờ gánh 2. Luật chơi: Mỗi quân cờ di chuyển từng bước một theo đường thẳng hay đường kẽ đến giao điểm trống kế tiếp. Hình 2 Mô tả cách di chuyển của một quân cờ Có hai cách để ăn quân cờ của đối phương: 9  Gánh: Khi một quân cờ của phe này đi vào giữa hai quân cờ của phe kia, thì hai quân cờ hai bên sẽ ăn. Trong Hình 3, quân cờ H di chuyển theo mũi tên xanh vào giữa hai quân đỏ N và Q. Hai quân này sẽ bị ăn mất. Hình 3 Hình ảnh về cách Gánh để ăn hai quân cờ khác  Nhảy qua đầu để ăn: Một quân cờ ở vị trí E, có thể bay qua đầu quân cờ ở vị trí J, và ăn mất quân cờ ở vị trí J. Hình 4 Hình ảnh về cách Nhảy qua đầu quân cờ khác để ăn 3. Lý thuyết: 10 3.1. Phân tích trò chơi Để biết những gì mong đợi từ một agent1, tốt nhất là có một số nghiên cứu toán học về Cờ Gánh được thực hiện trước khi phát triển AI để xác định các thuộc tính như hệ số phân nhánh và kích thước của không gian tìm kiếm, có nghĩa là số lượng trạng thái của trò chơi là duy nhất. Các thuộc tính này có thể cho biết liệu có thể giải quyết hoàn toàn trò chơi hay không hoặc có bao nhiêu di chuyển một agent có thể được mong đợi tìm kiếm trước khi di chuyển. 3.2. Không gian trạng thái của trò chơi Tổng số trạng thái khác nhau trong một trò chơi Cờ Gánh rất quan trọng, vì nếu con số này đủ nhỏ, trò chơi có thể được giải quyết bằng cách tìm ra một chiến lược chiến thắng nhất định cho một trong những người chơi. Để làm được điều này, trước hết chúng ta cần một công thức mô tả số cách một phần tử có thể được đặt trên bảng trò chơi. Một game Cờ Gánh bắt đầu với 16 quân cờ trên bàn cờ 5x5. Vì vậy có thể đặt quân cờ đầu tiên lên 1 trong 25 vị trí trên bàn cờ, quân thứ 2 là 1 trong 24 vị trí còn lại. Tương tự với các trạng thái bàn cờ có 15, 14… quân cờ. Tiếp tục như vậy ta có kết quả là: 25!/9! + c 116*25!/10! + c 216*25!/11! +.. + c 15 16 *25!/24! = 25!/9! *(1 + c 116*/10 + c 216*/(10*11) + c 316*/(10*11*12)+....+c 15 16 */(10*11*12*...*24)) = (circa)1.5986532e+20 3.3. Hệ số phân nhánh Yếu tố phân nhánh rất quan trọng vì nó xác định số trạng thái mà một agent phải xem xét để tìm cách di chuyển tốt nhất bằng cách duyệt qua các trạng thái đó trong trò chơi. 1 agent: một đối tượng chơi cờ một cách thông minh Mặc dù không thể thay đổi hệ số phân nhánh, vì nó là riêng biệt cho mỗi trò chơi, có thể thay đổi thuật toán kiểm tra cây trò chơi. Những thay đổi này có thể cho thuật toán loại bỏ một số trạng thái trước khi chúng được kiểm tra. Khi điều này được thực hiện, hệ 11 số phân nhánh yếu tố để xác định nhánh của các trạng thái mà thuật toán phải mở rộng để tìm bước di chuyển tốt nhất, trở nên nhỏ hơn so với với hệ số phân nhánh trung bình. Bằng cách phân loại các trạng thái không thể dẫn đến bước đi tốt nhất có thể, thuật toán có thể sử dụng nhiều thời gian hơn để xem các trạng thái có thể là bước đi tốt nhất, và theo cách đó làm giảm hệ số phân nhánh. 3.4. Mạng nơron nhân tạo (Neural Networks) 3.4.1. Mạng nơron nhân tạo (Neural Networks) là gì? Mạng nơron nhân tạo, Artificial Neural Network (ANN) là một mô hình xử lý thông tin phỏng theo cách thức xử lý thông tin của các hệ nơron sinh học. Nó được tạo nên từ một số lượng lớn các phần tử (nơron) kết nối với nhau thông qua các liên kết (trọng số liên kết) làm việc như một thể thống nhất để giải quyết một vấn đề cụ thể nào đó. Một mạng nơron nhân tạo được cấu hình cho một ứng dụng cụ thể (nhận dạng mẫu, phân loại dữ liệu..) thông qua một quá trình học từ tập các mẫu huấn luyện. Về bản chất học chính là quá trình hiệu chỉnh trọng số liên kết giữa các nơron. Cấu trúc neural nhân tạo: Hình 5 Cấu tạo một Neural Các thành phần cơ bản của một nơron nhân tạo bao gồm: • Tập các đầu vào: Là các tín hiệu vào (input signals) của nơron, các tín hiệu này thường được đưa vào dưới dạng một vector N chiều. 12 • • • • • Tập các liên kết: Mỗi liên kết được thể hiện bởi một trọng số liên kết – Synaptic weight. Trọng số liên kết giữa tín hiệu vào thứ j với nơron k thường được kí hiệu là wkj. Thông thường, các trọng số này được khởi tạo một cách ngẫu nhiên ở thời điểm khởi tạo mạng và được cập nhật liên tục trong quá trình học. Bộ tổng (Summing function): Thường dùng để tính tổng của tích các đầu vào với trọng số liên kết của nó. Ngưỡng (còn gọi là một độ lệch - bias): Ngưỡng này thường được đưa vào như một thành phần của hàm truyền. Hàm truyền (Transfer function): Hàm này được dùng để giới hạn phạm vi đầu ra của mỗi nơron. Nó nhận đầu vào là kết quả của hàm tổng và ngưỡng. Đầu ra: Là tín hiệu đầu ra của một nơron, với mỗi nơron sẽ có tối đa là một đầu ra. Như vậy nơron nhân tạo nhận các tín hiệu đầu vào, xử lý (nhân các tín hiệu này với trọng số liên kết, tính tổng các tích thu được rồi gửi kết quả tới hàm truyền), và cho một tín hiệu đầu ra (là kết quả của hàm truyền). 3.4.2. Một số kiểu Neural Networks Cách thức kết nối các nơron trong mạng xác định kiến trúc (topology) của mạng. Các nơron trong mạng có thể kết nối đầy đủ (fully connected) tức là mỗi nơron đều được kết nối với tất cả các nơron khác, hoặc kết nối cục bộ (partially connected) chẳng hạn chỉ kết nối giữa các nơron trong các tầng khác nhau. Người ta chia ra hai loại kiến trúc mạng chính: Tự kết hợp (autoassociative): là mạng có các nơron đầu vào cũng là các nơron đầu ra. Mạng Hopfield là một kiểu mạng tự kết hợp 13 Hình 6 Mạng tự kết hợp Kết hợp khác kiểu (heteroassociative): là mạng có tập nơron đầu vào và đầu ra riêng biệt. Perceptron, các mạng Perceptron nhiều tầng (MLP: MultiLayer Perceptron), mạng Kohonen, … thuộc loại này. Hình 7 Mạng kết hợp khác kiểu Ngoài ra tùy thuộc vào mạng có các kết nối ngược (feedback connections) từ các nơron đầu ra tới các nơron đầu vào hay không, người ta chia ra làm 2 loại kiến trúc mạng. 14 Kiến trúc truyền thẳng (feedforward architechture): là kiểu kiến trúc mạng không có các kết nối ngược trở lại từ các nơron đầu ra về các nơron đầu vào, mạng không lưu lại các giá trị output trước và các trạng thái kích hoạt của nơron. Các mạng nơron truyền thẳng cho phép tín hiệu di chuyển theo một đường duy nhất, từ đầu vào tới đầu ra, đầu ra của một tầng bất kì sẽ không ảnh hưởng tới tầng đó. Các mạng kiểu Perceptron là mạng truyền thẳng. Hình 8 Mạng truyền thẳng Kiến trúc phản hồi (Feedback architecture): là kiểu kiến trúc mạng có các kết nối từ nơron đầu ra tới nơron đầu vào. Mạng lưu lại các trạng thái trước đó, và trạng thái tiếp theo không chỉ phụ thuộc vào các tín hiệu đầu vào mà còn phụ thuộc vào các trạng thái trước đó của mạng. Mạng Hopfield thuộc loại này. Hình 9 Mạng phản hồi 3.5. AI trong game Cờ Gánh Nếu bạn chọn một agent để chơi thay một người chơi, điều không có ở đó. Vậy agent này phải cố gắng giải quyết một vấn đề nhất định cho người chơi đó. Trong trường hợp này, vấn đề là chiến thắng trong một game Cờ Gánh. Vấn đề này không phải là dễ 15 dàng để giải quyết, khi trò chơi có đối thủ chống lại nó. Trò chơi mà các agent đang chơi hoàn toàn có thể quan sát được, các agent có toàn quyền truy cập vào tất cả các thông tin trong trạng thái trò chơi hiện tại. Trò chơi cũng là tuần tự và tĩnh, vì các người chơi di chuyển sau người chơi khác và các thông tin được lưu trữ trong các trạng thái là trạng thái nhất quán cho bàn cờ. Khi các agent cạnh tranh với nhau trong môi trường như vậy, người đại diện thường sử dụng kiến thức về các quy tắc của trò chơi để phán đoán các khả năng trong trò chơi, cố gắng tìm một nhà nước đi để đảm bảo chiến thắng. 3.6. Mô hình thiết kế Để giúp dễ dàng mở rộng và thay đổi sau này, game cần tuân theo một mô hình, view và mẫu thiết kế điều khiển. Điều này cho phép trò chơi chạy mà không cần GUI hoặc chạy với GUI khác nhau mà không cần thay đổi bất cứ điều gì trong cấu trúc dữ liệu. Hình 10 Mô hình thiết kế game cờ gánh GUI phải cho phép người chơi đưa ra một số lựa chọn nhất định khi bắt đầu trò chơi, quan trọng nhất là kích thước bảng, loại người chơi và tên người chơi. Trong trò chơi, GUI phải hiển thị điểm số và bảng trò chơi, đồng thời cung cấp cho người dùng cơ hội thoát hoặc khởi động lại trò chơi. Một phần quan trọng khác của GUI là chuyển hướng tất 16 cả các lần nhấp chuột đến các phần khác của chương trình, như một người chơi bình thường. Bộ điều khiển trò chơi (Game Controller) phải có khả năng điều khiển cửa sổ trò chơi và các tùy chọn trò chơi mới. Ngoài ra, nó sẽ gửi các tùy chọn được chọn khi bắt đầu trò chơi đến Game Engine. Nó cũng phải báo cho GUI hiển thị thông tin qua trò chơi khi một trong những người chơi thắng. Công cụ trò chơi (Game Engine) sẽ xử lý logic trò chơi, giống như các quy tắc trò chơi. Nó cũng phải gửi thông tin trò chơi cho người chơi, cho họ thay đổi để di chuyển và gửi những di chuyển này đến GUI. Các lớp người chơi (Players) phải phản hồi lại các yêu cầu di chuyển được tạo bởi Game Engine và thực hiện các bước di chuyển. Để cho phép các lớp nhân vật khác nhau hoạt động với Game Engine, nó phải có khả năng giao tiếp với các đối tượng người chơi mà không cần thiết kế thừa từ hoặc là các lớp con lẫn nhau. 3.7. Dòng điều khiển Để đảm bảo logic của các sự kiện thông qua trò chơi, nhóm đã hiện thực một đồ thị dòng điều khiển như sau: Tùy chọn duy nhất có sẵn cho người dùng khi khởi chạy là tùy chọn trò chơi mới, chọn setting cho một trò chơi mới. Khi người dùng hoàn thành, trò chơi sẽ bắt đầu. Các trạng thái bây giờ xen kẽ giữa các trạng thái trong đó màu xanh hoặc màu đỏ có lượt cho đến khi trò chơi kết thúc. Khi trò chơi kết thúc, người dùng sẽ có thể bắt đầu một trò chơi mới, khởi động lại trò chơi hoặc thoát. 17 Hình 11 Đồ thị dòng điều khiển 18 Phần 3 - Mô hình trí tuệ nhân tạo MiniMax 1. Cơ sở lý thuyết: Thủ tục Minimax là một thủ tục được phát triển đặc biệt cho các môi trường agent hoàn toàn có thể quan sát được, tĩnh, tuần tự và đa tác nhân. Đó là một cách tiếp cận cũ và được thử nghiệm tốt để giải quyết các vấn đề về hai người chơi. Nó hoạt động bằng cách xây dựng một cây trò chơi đầy đủ xuống một mức độ nào đó. Từ cấp độ đó cây trò chơi được đánh giá từ dưới lên. Các bước di chuyển của agent được xác định là tối đa, vì nó là di chuyển của mình, lợi thế cần được tối đa hóa. Đối thủ là người chơi min kể từ khi anh ta muốn giảm thiểu lợi thế của agent bằng các bước di chuyển. Khi cây trò chơi được đánh giá tất cả các trạng thái ở cấp kế tiếp của cây được đưa ra các giá trị bằng cách đánh giá trong một hàm lượng giá. Điều này trả về giá trị của mỗi trạng thái ở cấp kế. Nếu một người chơi ở cấp độ kế là min, anh ta sẽ chọn trạng thái có giá trị thấp nhất trong số tất cả các con của mình và lấy giá trị đó làm giá trị của anh ta. Nếu nó là max anh ta sẽ chọn trạng thái có giá trị cao nhất trong số tất cả các con của mình và có giá trị đó là giá trị của mình. Điều này tiếp tục cấp cho các cấp độ, cho đến khi đỉnh của cây đạt được, tại thời điểm đó nốt con có chứa giá trị tiện ích phù hợp được chọn là bước đi tốt nhất. Giả sử rằng các hàm lượng giá là hoàn hảo các thủ tục MiniMax sẽ chơi một cách hoàn hảo, không có sai lầm nào cả. Thật không may, hàm này thường chỉ là một ước lượng thô của một giá trị thực sự của một trạng thái. Có một hàm lượng giá tốt là điều cần thiết cho thủ tục MiniMax, nếu hàm xấu hoặc thậm chí sai thủ tục sẽ thực hiện kém so với các thủ tục khác có hàm lượng giá tốt hơn, ngay cả khi thủ tục khác có hàm lượng giá xấu được cung cấp thêm thời gian để xem thêm phía trước trong trò chơi 1.1. Hàm lượng giá Định nghĩa của hàm lượng giá là một hàm ước tính chi phí của đường đi nhỏ nhất từ trạng thái hiện tại đến trạng thái mục tiêu. Vì việc đoán khoảng cách đến trạng thái mục tiêu phụ thuộc rất nhiều vào cách chơi của đối thủ, nên một hàm lượng giá được sử dụng thay thế trong môi trường đa tác nhân. Hàm lượng giá về cơ bản thực hiện điều tương tự, nhưng nó không trả về độ dài dự kiến từ trạng thái hiện tại cho mục tiêu, nhưng trả về giá 19 trị lượng giá trạng thái. Nếu hàm lượng giá là chính xác, trạng thái gần với chiến thắng sẽ có một giá trị I lớn hơn, so với trạng thái cách xa chiến thắng. Tuy nhiên, không có gì đảm bảo điều này, vì hầu hết các giá trị tiện ích chỉ là ước tính, dựa trên các thuộc tính nhất định của trạng thái hiện tại. Hàm lượng giá theo nhiều cách là thành phần quan trọng nhất trong tác nhân MiniMax. Nếu lượng giá là xấu, hoặc đưa ra các giả định sai về lượng giá trạng thái trò chơi, agent sẽ hoạt động kém so với các agent có lượng giá tốt hơn, ngay cả khi có nhiều thời gian hơn để phân tích bảng trò chơi. Có những cách tiếp cận khác nhau để tối ưu hóa hàm lượng giá. Một cách tiếp cận là sử dụng chức năng đánh giá tuyến tính có trọng số. Những ưu điểm và nhược điểm của phương pháp được mô tả trong phần tiếp theo. 1.2. Hàm đánh giá tuyến tính có trọng số Hàm đánh giá tuyến tính có trọng số lấy một tập hợp các hàm, mỗi hàm đại diện cho một thuộc tính mà hàm đánh giá sẽ tính đến. Nếu s là trạng thái và wi là trọng số của fi(s) thì hàm đánh giá tuyến tính có trọng số có thể được định nghĩa như trong công thức sau, trong đó n là số thuộc tính từ trạng thái mà hàm tính đến. Cách tiếp cận này thường được sử dụng để xây dựng các hàm lượng giá vì nó đơn giản và khả thi. Vấn đề duy nhất là xác định các hàm và trọng số của chúng, nhưng có các phương pháp cho điều đó. Cờ Gánh là một trò chơi có tổng bằng không, có nghĩa là tổng số điểm của người chơi luôn bằng không. Khi một người chơi thực hiện một động tác làm tăng cơ hội giành chiến thắng, đối thủ của anh ta sẽ giảm cơ hội chiến thắng. Điều này làm tăng giá trị lượng giá của người chơi đầu tiên và giá trị lượng giá của đối thủ. Người chơi gần nhất với chiến thắng sẽ luôn có điểm số dương và đối thủ của anh ta sẽ có điểm âm, có cùng giá trị. Điều này dễ dàng cho các agent sử dụng hàm lượng giá để phân tích cách họ đang làm so với đối thủ của họ. 20