Membuat AI TicTacToe dengan Algoritma Alpha–beta pruning — Javascript
Table Of Content
- Alpha-beta pruning
- Minimax
- Menyempurnakan Minimax menjadi Alpha-beta
- Membuat Game Tic Tac Toe Sederhana di Javascript
- Membuat UI Sederhana untuk Game
Alpha-beta pruning
Alpha-beta pruning adalah algoritma yang digunakan untuk mencari sebuah nilai maksimum dari suatu pohon percobaan dengan bantuan limitasi nilai Alpha dan Beta nya untuk memutus rantai pencarian yang terlalu banyak.
Kenapa dinamakan Alpha-beta pruning ? Algoritma ini nantinya akan dipangkas / di limitasi menggunakan nilai Alpha sebagai nilai Tertinggi yang bisa di peroleh oleh ai dan nilai Beta untuk nilai terendah yang diperoleh musuh. Lalu node dari pohon cabang akan di pangkas jika sudah ada dibawah nilai Alpha dan Beta oleh karena itu ditambahkan kata prune yang artinya memangkas.
Untuk membantu pemahaman teman — teman saya sarankan membaca artikel sebelumnya tentang “Algoritma Minimax” karena Alpha beta ini merupakan algoritma penyempurna dari Minimax.
Berikut link nya :
Tapi jika teman — teman tidak mau membaca nya its okay saya akan coba jelaskan kembali dengan singkat.
Minimax
Sekarang coba perhatikan gambar dibawah ini.
Teman — teman coba lihat nilai pohon cabang yang paling bawah yang ada pada depth 4.
Sebelumya algoritma ini dari minimax, yang mana di pohon skor diatas akan di beri label “max” untuk cabang pertama (depth 0), lalu setiap turun kebawah akan berganti label “min”, lalu turun kebawah lagi akan menjadi “max” dan begitu seterusnya.
Algoritma ini mencari dan menyeleksi mana skor yang harus di bawa ke atas nya.
Algoritma ini akan bekerja dari bawah lalu ke atas membawa skor yang harus di pilih di setiap label nya, jika labelnya max artinya cabang tersebut harus memilih skor yang paling tinggi, jika labelnya min maka berlaku sebaliknya.
Sebagai contoh perhatikan kedalaman paling bawah sendiri yaitu depth 4 :
Teman — teman bisa perhatikan, di depth 4 memiliki 9 skor yang mana adalah hasil dari 6 cabang dari depth 3.
Sekarang ambil cabang pertamanya.
Dicabang pertama ada 2 nilai yaitu 10 dan positif tak hingga. sekarang mana yang kita pilih ?
Nah karena di depth 3 merupakan “min” yang berarti minimizing, kita harus memilih skor yang paling kecil atau paling rendah teman — teman.
Dari kedua skor diatas, yang paling rendah adalah 10. Oleh karena itu skor 10 yang dipilih lalu dibawa untuk menjadi skor di depth 3 yaitu 10.
Begitu juga dengan yang lainnya, Teman — teman bisa lihat gambar dibawah ini juga sama, akan dipilih nilai terendah untuk nilai minimizing nya.
Lanjut, setelah proses penentuan nilai di depth 3 selesai yang diambil dari depth 4,
Selanjutnya kita harus menyelesaikan kembali yaitu menentukan nilai dari depth 2 yang mana kita ambil dengan melakukan maximizing dari depth 3.
Perhatikan gambar diatas, teman — teman bisa melihat bahwasannya sebagai contoh cabang pertama ada nilai 10 dan 5, yang kita ambil untuk depth 2 adalah skor 10. karena kita melakukan proses maximizing yang artinya mencari skor tertinggi.
Oleh karena itu kita bawa skor 10 ke atas yaitu ke depth 2.
Begitu juga dengan cabang lainnya, contoh nya ada nilai 5 dan negative tak hingga, maka yang diambil adalah nilai 5 nya.
Nah cara maximizing dan minimizing tersebut akan terus dilakukan sampai ke depth 0 atau di tingkatan paling atas sendiri. sehingga kita akan mendapatkan skor yang paling optimal yaitu -7
Lalu, apa hubunganya dengan TicTacToe dan Algoritma minimax?
Perhatikan gambar berikut ini.
Nah sekarang mungkin kalian lebih paham lagi, fungsi dari pohon pencarian adalah mensimulasikan setiap langkah yang bisa di lakukan pada permainan, sebagai contoh adalah permainan tic tac toe.
Nah skor yang berasal dari permainan selesai, yaitu :
* 1 untuk Menang
* 0 untuk draw / seri
* -1 untuk kalah
Teman — teman bisa melihat dari gambar diatas dimana hasil skor dari permainan setiap cabang akan di hitung dengan menggunakan Algoritma minimax tadi.
Dengan cara ini, kita bisa mendapatkan skor mana yang paling tinggi dan dari node atau cabang mana skor optimal tersebut.
Dari gambar diatas, teman — teman bisa tahu skor paling optimal adalah dari cabang pertama yaitu meletakan player “O” di tengah papan tictactoe, dan itu akan menyebabkan kemenangan oleh karena itu kita beri skor 1.
Lalu mengapa kita menggunakan algoritma ini? Jawabanya simpel yah karena cocok.
Dengan algoritma ini kita bisa memastikan setiap kemungkinan pergerakan lalu mencari skor yang paling optimal. Ditambah lagi ini adalah game board 2 player, yang artinya ada 2 player yang saling menginginkan nilai tertinggi. Oleh karena itu di beri nama Minimax karena ketika dia melakukan Maximizing artinya player menjadi player utama berusaha mencari kemungkinan terbaik, lalu ketika player Minimizing artinya dia berusaha menjadi lawannya dan memastikan kalah, oleh karena itu mencari skor terendah.
Sangat cocok bukan? Oleh karena itu Algoritma Minimax ini adalah algoritma yang akan kita gunakan.
Menyempurnakan Minimax menjadi Alpha-beta
upssss tapi tunggu dulu, teman — teman sadar tidak bahwa semakin banyaknya node / cabang pencarian itu akan sangat memakan banyak sumber daya komputasi. Karena komputer akan terus membuat simulasi disetiap cabang sampai permainan berakhir di sisi cabang — cabangnya.
Ini adalah kekurangan dari Algoritma Minimax ini, oleh karena itu kita berkenalan kembali dengan Algoritma Alpha-beta pruning.
Algoritma ini sebenarnya adalah algoritma Minimax yang di beri tambahan nilai Alpha dan Beta.
Nilai awal dari Alpha adalah Negatif tak hingga, dan nilai Beta adalah Positif tak hingga.
Nilai ini akan di perbarui terus selama pencarian cabang (minimizing / maximizing).
Lalu pencarian cabang akan di hentikan ketika nilai Alpha nya lebih besar atau sama dengan nilai Beta.
Yang artinya nilai yang semula Beta > Alpha, ini akan berhenti ketika nilai nya berubah menjadi Alpha > Beta.
Dengan algoritma ini, kita bisa menghentikan node yang tidak perlu kita cari lagi, jadi kita akan hentikan pencarian pada node itu atau istilahnya kita pangkas.
Jika teman — teman belum paham,
Logikanya gini, misalkan teman — teman punya 8 pasar untuk dikunjungi membeli sayuran. Nah ketika di pasar pertama teman teman tidak mendapatkan sayuran tersebut, lalu lanjut ke pasar kedua. Dipasar kedua baru teman teman mendapatkan sayurannya.
Sekarang pertanyaannya, karena kita sudah mendapat sayurannya di pasar kedua, apakah teman teman harus melanjutkan pencarian dipasar ketiga sampai kedelapan? Tentu tidak perlu kan? karena kita sudah mendapat kondisi yang paling optimal yaitu kita sudah dapat sayurannya, mengapa kita berusaha cari di lain pasar lagi… sangat menghabis kan waktu.
Membuat Game Tic Tac Toe Sederhana di Javascript
sebelum lanjut mengaplikasian algoritmanya, terlebih dulu saya akan membuat game dasaranya dulu atau saya sebut Game Logic nya dulu.
Saya tidak akan menjelaskannya secara detail, saya akan gunakan kode yang sudah ada dari artikel sebelumnya.
Jika teman teman belum paham kode yang saya tulis ini bisa membuka di artikel saya sebelumnya tentang membuat Game Logic Tic Tac Toe sederhana di :
Oke, jadi caranya cukup simple. Buat dulu 4 file berikut yaitu :
Lalu, edit index.html lalu isikan :
Lalu isikan file board.js :
Lalu sekarang coba isikan file game.js dengan kode berikut :
const board = new TicTacToeBoard();//board.move('x', 0);board.move('x', 1);board.move('o', 4);//board.printBoardPretty();
Simpan semuanya lalu jalankan di browser, seharusnya teman — teman akan mendapatkan tampilan berikut di console browser :
Untuk sekarang kita masih membuat game logic nya saja, jadi tampilan ascii seperti diatas adalah tampilan sementara kita.
Kita punya perintah :
board.move(player, indexBoard)
perintah untuk mengisi bidak tic tac toe, player bisa o atau x, index adalah nomor urut petak di papannya dari angka 0–8board.printBoardPretty()
untuk menampilkan keadaan papan tic tac toe ke console browser
Membuat AI Dengan Algoritma Alpha-beta
disini langkah awalnya saya akan membuat class agar lebih clean dan elegan kode kita nanti karena akan berbasis objek.
Disini saya membuat dasaran class nya :
class TicTacToeAI {board = null;
player = null;
enemy = null;
maxDepth = 10;
scores = { win: 1, lose: -1, tie: 0 }; constructor(player, board) {
this.player = player;
this.enemy = (this.player == 'x') ? 'o' : 'x';
this.board = board;
}
getBestMove () {
...
}
alphaBeta () {
...
}
}
Oke jadi dari kode diatas kita punya class TicTacToeAI yang mana saat di construct dia harus menerima 2 parameter yaitu player dan board.
- player : menunjukan ai akan berlaku sebagai player x atau o
- board : adalah object dari TicTacToeBoard, menunjukan keadaan papan sekarang.
Lalu kita juga punya variabel global yaitu :
- board
menyimpan papan tictactoe untuk state nya - player
menyimpan player ai akan menjadi x atau o - enemy
menyimpan player musuh akan sebagai apa, ini akan otomatis terisi jika player di set X maka secara otomatis variabel enemy akan di set menjadi O - maxDepth
kedalaman maksimal yang kita ijinkan untuk pencarian cabang nantinya, jika kedalaman melebih batas maka akan langsung di hentikan. - scores
mencatat skor konstan jika menang maka skor 1, jika kalah skor -1 dan jika seri maka skor 0
selanjutnya kita punya metode getBestMove() dan alphaBeta(), kita gunakan getBestMove untuk memanggil metode alphaBeta() nantinya secara cepat.
Didalam metode alphaBeta, sekarang kita ganti dengan :
Diatas kita mempunyai metode alphaBeta, dimana didalamnya kita punya 3 terminal, terminal ini berfungsi memutus rantai rekursif, karena untuk dapat membuat sebuah pohon pencarian cabang tentu saja kita harus membuat fungsi rekursif.
Fungsi rekursif adalah fungsi yang dapat memanggil fungsi dirinya lagi secara berulang.
Kenapa kita menggunakan fungsi rekursif? karena sebenarnya tujuannya kode kita sama, hanya saja kita memerlukan cabang. Oleh karena itu kita menggunakan parameter depth yang mana disetiap perulangan fungsi rekursif depth nya akan ditambah 1.
Selanjutnya kita punya terminal pertama yaitu terminal getWinner, yang berfungsi untuk menghentikan rantai dengan me return skor. terminal ini berlaku jika getWinner menghasilkan output berupa ada yang menang atau kalah atau draw.
Jika tidak ada yang menang, kalah atau draw maka terminal ini akan diabaikan.
Lanjut, di terminal kedua adalah terminal max depth, ini berfungsi memutus rantai dengan me return skor seri jika depth nya sudah melebih maxDepth yang sudah ditentukan diawal tadi.
Terminal ketiga adalah terminal depth == 0 , di depth ke 0 kita akan mengistemewakan nya, karena kita ingin mengambil skor tertinggi dan pilihan ai nya akan memilih dimana dia akan meletakan bidaknya nanti.
Sekarang coba lihat potongan kode berikut :
if (isMaximizing) {
bestScore = -Infinity;
for (let i = 0; i < board.state.length; i++) {
const e = board.state[i];
if (e == '') {
var newBoard = new TicTacToeBoard([...board.state]);
newBoard.move(this.player, i);
newNode = this.alphaBeta(newBoard, depth+1, false, alpha, beta);
bestScore = Math.max(newNode.score, bestScore);
alpha = Math.max(alpha, bestScore);
bestMove = i;
if (alpha > beta) break;
}
}
}Kode diatas memungkinkan kita bisa mensimulasikan setiap kemungkinan pergerakan, jadi misal pergerakan x di petak 0 maka apakah menang atau tidak? seperti itulah fungsi nya.
Karena maximizing, maka kita akan mengecek apakah skor nya lebih tinggi atau tidak, jika lebih tinggi dari nilai max pertama, maka skor akan diganti dengan skor yang tertinggi.
Oleh karena itu lah kita menggunakan fungsi Math.max() .
Jika teman — teman merasa kurang jelas dan detail, teman — teman bisa melihat artikel berikut :
Karena sebenarnya dasar dari kode sama dengan algoritma minimax diatas, yang beda adalah teman — teman bisa lihat kode berikut :
if (alpha > beta) break;yap, kode diatas bermaksud jika suatu saat nilai alpha lebih besar dengan nilai betanya maka akan di hentikan proses pencarian cabang selanjutnya.
Karena nilai awal alpha adalah -Infinity dan beta adalah Infinity maka kita akan membuat nilai alpha ini diperbarui setiap pencarian skor cabangnya.
makanya teman teman melihat kode ini :
bestScore = Math.max(newNode.score, bestScore);
alpha = Math.max(alpha, bestScore);yak, nilai alpha akan terus diperbarui seperti layaknya bestScore , jadi suatu saat akan terjadi nilai alpha lebih besar dari beta agar dapat di hentikan.
Untuk minimizing sebenarnya sama saja, hanya bedanya yang dicari adalah nilai minimal dan nilai betanya.
Sekarang, kode akhir dari file ai.js kita adalah berikut :
Membuat UI Sederhana untuk Game
kode yang saya ambil ini berasar dari artikel saya sebelumnya juga yang bisa kalian cek di :
Okay, jadi saya singkatkan saja.
Modifikasi file index.html dengan :
Lalu buat file baru bernama style.css dan isi dengan :
Lalu ganti file game.js tadi dengan kode :
Sekarang teman — teman bisa membukanya di browser dan harus nya menampilkan seperti ini :
Ini saja yang bisa saya sampaikan tentang Algoritma Alpha-beta pruning untuk membuat AI game TicTacToe.
Saya juga akan membagikan source code dari tutorial ini, dan video youtube agar lebih mudah dipahami nantinya.
Source Code Github :
https://github.com/viandwi24/tictactoe-alpha-beta-jsDemo :
https://viandwi24.github.io/tictactoe-alpha-beta-js/Versi Video Youtube :
-
Sekian materi yang bisa saya bagikan, semoga ini semua bisa bermanfaat untuk kalian, sekian dan sampai jumpa!!!
