Penerapan HPA* Pada Game Ms. Pac-Man

Abstrak

Game Ms. Pac-Man merupakan permainan yang diminati beberapa peneliti dalam hal membuat kecerdasan buatan untuk memainkan Ms. Pac-Man. Berbeda dari Pac-Man, Ms. Pac-Man merupakan permainan non-deterministik sehingga banyak hal yang tidak pasti dalam permainan tersebut, membuat Ms. Pac-Man cukup sulit. Para peneliti menganggap hal tersebut merupakan tantangan yang menarik dalam perkembangan ilmu komputer khususnya kecerdasan buatan. Bahkan para peneliti membuat kompetisi untuk kecerdasan buatan terbaik dalam permainan ini, menggunakan skor sebagai perbandingan performa agen. Salah satu kompetisi yang ada adalah IEEE CIG 2011. Dalam permasalahan tersebut, penulis akan menggunakan metode Hierarchical Path-Finding A* (HPA*), metode sejenis A* untuk membuat agen kontroller pada Ms. Pac-Man. Tujuan dari penggunaan metode tersebut adalah menguji apakah metode HPA* dapat mencapai performa yang bagus. Performa pada metode A* belum mendekati skor tertinggi saat ini. Pada penelitian sebelumnya skor maksimal yang didapat menggunakan A* adalah 24640 dalam sepuluh kali pencobaan. Dibandingkan dengan penelitian terbaru yang menggunakan decision tree dapat mencapai skor 43720, skor yang dicapai dengan metode A* kira-kira setengah dari penelitian terbaru. Untuk memperbaiki hasil metode A*, pada penelitian ini digunakan metode HPA*. Dengan membagi daerah permainan menjadi beberapa bagian melalui HPA*, skor yang didapat diharapkan lebih baik dari penelitian sebelumnya. Namun hasil yang didapat pada penelitian ini masih kalah, skor yang didapat adalah 17050. Oleh karena itu, pada penelitian ini dibahas implementasi HPA* beserta analisis performa dari metode HPA*.