IMPLEMENTASI ALGORITMA NEGASCOUT UNTUK PERMAINAN CHECKERS

22074279, Aditya Kurniawan Effendi (2012) IMPLEMENTASI ALGORITMA NEGASCOUT UNTUK PERMAINAN CHECKERS. Final Year Projects (S1) thesis, Universitas Kristen Duta Wacana.

	Text (Skripsi Informatika) 22074279_bab1_bab5_daftarpustaka.pdf Download (2MB)
	Text (Skripsi Informatika) 22074279_bab2-sd-bab4_lampiran.pdf Restricted to Registered users only Download (3MB) | Request a copy

Abstract

Negascout ditemukan oleh Alexander Reinefeld pada tahun 1983. Algoritma ini adalah optimalisasi dari algoritma Minimax dengan menggunakan zero-width window untuk menetukan node mana yang akan dipotong. Berbeda dengan Alpha-Beta Pruning yang menggunakan jendela pencarian yang lebih besar yaitu alpha dan beta. Dalam penelitian ini algoritma Negascout akan diimplementasikan pada permainan Checkers. Permainan iniadalah salah satu permainan zero-sum game yang berarti pemain dinyatakan menang jika pemain kalah, seandainya pemain membutuhkan 1 poin untuk menang, maka untuk kalah pemain dinyatakan kalah jika mendapatkan nilai -1. Dalam permainan ini setiap pemain dapat mengetahui semua kondisi permainan, seperti jumlah bidak yang dimiliki pemain dan lawan, posisi bidak, dan langkah apa saja yang dimiliki oleh pemain maupun lawan. Penerapan algoritma Negascout pada permainan ini akan dibandingkan dengan algoritma Alpha-Beta Pruning untuk melihat performanya. Kedua algoritma digunakan untuk mencari solusi terbaik dari 5 kondisi papan yang diberikan dan diberikan batas depth 4, 6 dan 8. Dari 86% hasil pengujian yang dilakukan algoritma Negascout membutuhkan waktu lebih singkat dari algoritma Alpha-Beta Pruning pada pengujian yang dilakukan. Selain itu hasil pengujian juga menunjukkan algoritma Negascout menghasilkan satu node solusi yang berbeda dengan algoritma Alpha-Beta Pruning. Dilihat dari nilai heuristik yang dihasilkan algoritma Negascout menghasilkan solusi yang sama baiknya dengan algoritma Alpha Beta Pruning.

Actions (login required)

View Item