Membuat AI TicTacToe dengan Algoritma Minimax — Javascript — Part 2 -dan Mengenal Apa Itu Minimax Secara Tuntas.

Part Sebelumnya

Part #1 — Membuat Game Logic Tic-Tac-Toe
https://medium.com/@viandwi24/membuat-ai-tictactoe-dengan-algoritma-minimax-javascript-part-1-3df454b70d18

Sesuai janji dipart sebelumya, kali ini kita akan membuat AI untuk dapat menemukan Cara Untuk Menang dan Mengurangi Cara Untuk Disudutkan, Yaitu menggunakan Algoritma Minimax. Mari kita simak kenapa kita perlu menggunakan Algoritma Minimax ini dan apa itu Minimax?

Table Of Content

• Mengenal Minimax
• Penerapan Minimax Dalam Membuat Keputusan Permainan Tic-Tac-Toe
• Membuat AI dengan Minimax di Javascript

Minimax

Dilansir dari Wikipedia, berikut penjelasan singkat tentang Minimax :

Pada algoritme minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan tersebut.
https://id.wikipedia.org/wiki/Minimax

Gambaran Tentang Minimax :

Singkatnya, Minimax Bisa Digambarkan sebagai Pohon Kemungkinan, dimana Pohon tersebut akan terus bercabang untuk mengambil suatu angka (skor) yang paling Tinggi (Max).

Sesuai namanya, Minimax akan membuat suatu pohon kemungkinan, dimana angka teratas akan melakukan pencarian skor tertinggi (Maximizing) , dan dimana setiap turun satu tingkat kebawah (kedalaman) akan dilakukan pencarian skor terendah (Minimizing).

Lalu Kenapa kita menggunakan algoritma ini untuk membuat AI bermain TicTacToe?
Jawabannya sederhananya, karena algoritma ini sangat cocok.

Dengan algoritma ini, sang AI akan menyimulasikan permainan di belakang layar, tentunya bisa di peragakan dengan gambar Pohon Kemungkinan Diatas. dimana di tingkat kedalaman pertama, Sang AI akan melakukan cek semua kemungkinan pergerakan, lalu memilih pergerakan yang paling tinggi kemungkinananya untuk menang. Lalu bagaiaman kalau ditingkat pertama sang AI belum mendapat kemungkinan menang?
Maka sang AI akan lanjut ke tingkat lebih rendah kembali, lalu dia akan menyamar menjadi musuh dan mencoba mencari tingkat kemungkinan kalah lebih besar. Kenapa dia mencari kemungkinan kalah?
karena ditingkat ini sang AI berusaha berfikir menjadi Lawan, artinya sang lawan akan mengambil kemungkinan menang. Oleh karena itu ketika sang AI menyamar menjadi musuh, dia akan bergerak se optimal mungkin dan mengambil kemungkianan kalah sang lawan, karena Kalahnya lawan berarti adalah kemenanangan dia. nah di tingkat ini lah dinamakan Minimizing / Min karena sang Ai berusaha mencari tingkat skor terendah (kemungkinan menang lawan rendah)

Perhatikan gambar diatas di tingkat teratas, sang AI akan mencari kemungkinan pergerakan. dari contoh diatas ada 3 kemungkinan pergerakan, yaitu memberi “O” di tengah, dibawah atas di samping kanan. 3 Kemungkinan pergerakan ini sang AI harus mengambil skor tertinggi / kemungkinan menang tertinggi. Bagaimana AI bisa tau ditingkat ini ?

AI melihat ada 3 Kemungkinan Pergerakan

Contoh di pergerakan kiri, sang AI memberi “O” di tengah dan dia menang. Inilah yang disebut kemungkinan menang, disini kita akan berikan dia Skor 1 untuk memang.

Tapi tidak berhenti disitu, AI harus mencari kemungkinan pergerakan selanjutnya, karena di tingkat pertama sang AI harus mencoba semua kemungkinan pergerakan dan memastikan yang dia ambil merupakan skor tertinggi.

Lah bagaimana kalau kemungkinan nya masih meninggalkan kemugnkinan lain? Dicontoh pertama sudah jelas jelas ketika kemungkinan di coba si AI langsung menang, tapi di kemungkinan ke 2 dan ke 3sang AI belum menang, artinya ini saatnya si AI harus bisa membaca pergerakan sang Lawan.

Karena di kemungkinan ke 2 dan ke 3 permainan masih berlanjut, maka kali ini AI harus membaca pergerakan lawan, AI harus bisa mengambil Pegerakan lawan yang di perkirakan adalah dimana Lawan Kalah. Teknik ini dinamakan Minimazing (Mencari yang terendah)

Bisa kalian lihat lengkap diatas, dimana AI akan melanjutkan ke tingkat kedalaman lagi, lalu mulai mencari kemungkinan langkah untuk bergerak.
Tapi ada perbedaan dengan sebelumnya di tingkat depth 0, yup di tingkat depth 1 si AI akan melakukan Minimizing, AI akan “menyamar” menjadi Lawan, oleh karena itu di tingkat Minimizing ini sang AI tidak mencari tingkat skor tertinggi (kemenangan), tapi mencari skor terendah, yaitu kemungkinan Lawan akan kalah. ini merupakan kebalikan dari Maximizing, karena memang disini kita tidak menjadi AI, tapi dirinya Menyamar Menjadi Sang Lawan.

Oleh karena itu Yand Dipilih skor adalah yang Terendah, bisa dilihat contoh kemungkinan terakhir diatas, dimana Ada 2 kemungkinan yaitu skor 0 dan -1, tapi yang dikembalikan ke atas adalah skor -1, kenapa? yah karena AI melakukan Minimizing.

Selanjutnya, semuanya akan dikembalikan ke pohon awal / puncak pohon.

Dicontoh diatas, hanya terdapat 3 tingkat kedalaman (depth 3). itu karena permainan berakhir di depth 3, jika semisal permainan masih belum berhenti (belum ada yang menang / draw), maka depth akan di teruskan ke tingkat selanjutnya sampai game berakhir.

Jadi urutan dalam Minimax ini adalah :
Maximizing -> Minimizing -> Maximizing -> ………

Ini sesuai dengan permainan Tic Tac Toe yang mana setiap satu kali pergerakan, player akan bergantian.

Kembali lagi Ke Awal, setelah di kedalaman O (depth 0) mendapat semua skor nya, bisa dilihat skor akhirnya adalah :

Karena di kedalaman ini adalah Maximizing, artinya kita harus menentukan skor paling tertinggi (max), Pilihan yang memiliki skor tertinggi, itulah yang menjadi Pilihan Terbaik yang akan dipilih Oleh Sang “AI”.

Kesimpulan

Yup, algoritma ini adalah salah satu yang cocok untuk membuat AI dalam Permainan Tic-Tac-Toe kita. Karena dengan begini, AI bisa membuat keputusan yang memungkinkan dirinya tak terkalahkan, karena dia akan membuat simulasi setiap kemungkinan yang adadan memastikan pergerakan dia selanjutnya benar benar kemenangan.

Ini seperti cara manusia berfikir, manusia akan memikirkan setiap kemungkinan yang terjadi, lalu mengambil keputusan kemungkinan yang terbaik.

Membuat AI Tic-Tac-Toe

Sekarang kita akan meneruskan part sebelumnya, mari kita edit file ai.js lalu kita buat class bernama TicTacToeAI

• board
  adalah variable untuk menyimpan kondisi papan tictactoe yang akan dimainkan oleh AI, board disini akan merepresentasikan dari class TicTacToeBoard di part sebelumnya.
• player
  adalah variabel untuk mendefiniskan player yang dimainkan oleh AI, tentu saja jika tidak Xmaka O
• moves
  variabel ini menampung bentuk simulasi langkah dari AI nantinya saat melakukan simulasi permainan dengan algoritma Minimax
• maxDepth
  karena minimax merupakan gambaran dari pohon cabang kemungkinan, kita bisa membatasi kedalaman yang bisa dicapai oleh minimax, dengan begini kita bisa mengatasi kedalaman.
  Membatasi kedalaman Minimax dalam membuat cabang juga akan berpengaruh terhadap hasil nya. Karena sudah pasti kedalaman yang rendah membuat AI tidak bisa mengambil keputusan sampai permaianan berakhir.
• constructor
  fungsi ini akan dipanggil saat menlakukan init class AI, dimana kita membutuhkan 2 parameter yaitu board dan player.
• getBestMove
  fungsi ini adalah fungsi yang nanti kita panggil agar AI mulai mencari score terbaik untuk melangkah

Lanjut, sekarang kita ke inti programnya, disini kita akan buat fungsi minimax untuk mencari segala kemungkinan langkah yang bisa dilakukan.

tambahkan fungsi berikut di file ai.js tadi, tepatnya dibawah fungsi getBestMove

Kalian bisa lihat, dimana fungsi Minimax ini disebut fungsi Recursive, apa maksudnya ? fungsi Minimax ini bisa memanggil dirinya sendiri yang bisa menyebabkan perulangan. Oleh karena itu kita perlu terminal, dimana terminal adalah kondisi yang menyebabkan rantai rekursif nya terputus, tanpa terminal maka program bisa akan loop secara terus menerus.

Terminal di fungsi kali ini adalah mengecek apakah tic tac toe tersebut sudah menang atau draw. jika menang atau draw maka kita akan return hasil akhir score terbaik.

Lalu kita mendefinisikan juga isMaximizing artinya apa? seperti di teori diatas, isMaximizing akan mengatur pergerakan AI, apakah AI harus Memaksimalkan skornya atau malah Meminimalkan Skor.

Mudahnya, jika Minimax sedang Maximizing maka AI akan menjadi diri sendiri, sebagai contoh akan menjadi player “X”, sedangkan ketika Minimizing maka AI akan menjadi lawan nya yaitu player “O”.

Logika saja, ketika kita menjadi diri sendiri, maka kita akan memilih skor tertinggi agar kita menang, sedangkan kita akan berfikir ketika kita menjadi lawan, maka kita akan mengambil skor terendah agar diri kita menang.

Nah itu lah yang sedang dilakukan AI saat fungsi Minimax dijalankan, Ketika dia Maximizing dia akan menjadi diri sendiri dan berusaha mencari nilai terbaik, jika dia melakukan Minimizing artinya dia akan mencari nilai terendah.

Penerapan Max dan Min ini untuk apa? karena ini permainan Tic-Tac-Toe maka Player Turn akan dilakukan secara bergilir kan? nah ketika Maximizing artinya giliran AI, sedangkan ketika giliran player lawan maka dia akan menjadi Minimizing.

Lalu, disetiap fungsi Min dan Max, kita mencatan pergerakan kemungkinannya beserta skor, kedalamannya lalu kita catat / push ke variabel moves , ditujukan dibagian :

this.moves.push({ depth, isMaximizing, move: i, score })

Nah dari situ kita bisa tahu skor terbaik yang bisa kita ambil nantinya, oke sekarang kita buat fungsi getBestMove yang sempat kita kosongi tadi, edit file ai.js dan tambahkan :

Karena hasil pergerakan yang kita catat di variabel moves itu adalah pergerakan semuanya, mulai dari kedalaman 0 — sampai selesai, sedangkan sekarang kita akan menentukan langkah AI selanjutnya dalam keadaan board sekarang, jadi kita memerlukan data dari kedalaman o saja, maka kita gunakan perintah filter seperti pada :

let filter_depth_0  = this.moves.filter((el) => {
    if (el.depth == 0) bestScore = Math.max(el.score, bestScore)
    return el.depth === 0
})

ta lupa diatas kita juga mengambil skor tertinggi di depth 0 yang kita simpan di variable bestScore , lalu kita bisa melihat variabel filter_depth_0 sekarang akan berisi moves di kedalaman 0 saja.

Selanjutnya kita mengambil move yang memiliki skor tertinggi

let filter_best_move= filter_depth_0.filter((el) => el.score >= bestScore)

jika di filter_depth_0 kita mendapati ada skor 0, 1, -1, 1 maka disini setelah kita filter kembali maka hasilnya akan berupa 1,1 mengapa? karena kita hanya mengambil skor tertinggi saja.

Selanjutnya jika hasilnya lebih dari satu, maka kita biarkan AI menentukan acak mana pilihan yang akan diambil, karena bobot pilihanya sama, kita gunakan fungsi :

let bestMove = filter_best_move[Math.floor(Math.random() * filter_best_move.length)]

Akhirnya, pergerakan selanjutnya yang akan dipilih sang AI sudah ditentukan, di variabel bestMove inilah pergerakan yang paling memungkinkan dipilih AI untuk berusaha memenangkan pertandingan.

Jadi, file ai.js setidaknya akan memiliki source code lengkap seperti berikut :

Saatnya Uji Coba!

kita edit file game.js lalu isi dengan :

let board = new TicTacToeBoard()
board.move('o', 0)
board.move('o', 1)
board.move('x', 2)
board.move('x', 3)
board.move('o', 7)
board.move('x', 8)
board.printBoardPretty()

Oke, jadi saya akan membuat kondisi papan yang sama dengan teori diatas tadi yah. Coba jalankan di browser, harusnya kondisi papan sama dengan materi kita yang ada diatas tadi.

Jadi saya ingin membuktikan kebenaran teori kita diatas tadi tentang gambaran Minimax dalam Tic-Tac-Toe, jadi saya ingin tau langkah terbaik apa yang akan di jalankan sang AI.

Sekarang, edit kembali game.js jadikan seperti berikut :

let board = new TicTacToeBoard()
// buat kondisi
board.move('o', 0)
board.move('o', 1)
board.move('x', 2)
board.move('x', 3)
board.move('o', 7)
board.move('x', 8)
board.printBoardPretty()
// ai
console.log(" AI Memilih ")
let ai_player = 'o'let AI = new TicTacToeAI(ai_player, board)
let result = AI.getBestMove()
console.log(result)

hasilyang diperoleh adalah berikut :

yup, fungsi getBestMove mengembalikan objek yang berisi depth, IsMax, move, score, dan Instance dari AI saat sedang mencari minimax.

disitu terterah hasil AI adalah memilih move: 4 yang artinya pilihan terbaik adalah untuk mengisi “0” dikolom ke 4 (kolom tengah)

kita ganti saja script diatas menjadi :

let board = new TicTacToeBoard()
// buat kondisi
console.log(" Kondisi Sebelum AI memilih :")
board.move('o', 0)
board.move('o', 1)
board.move('x', 2)
board.move('x', 3)
board.move('o', 7)
board.move('x', 8)
board.printBoardPretty()
// ai
console.log(" AI Memilih : ")
let ai_player = 'o'let AI = new TicTacToeAI(ai_player, board)
let result = AI.getBestMove()
board.move(ai_player, result.move)
board.printBoardPretty()

dengan begitu, pergerakan AI akan langsung kita terapkan di papan permainan, dan hasilnya akan seperti berikut :

dan yup, sesuai dengan teori kita yang diatas tadi, sang AI berhasil memilih sesuai dengan apa yang kita mau, yaitu memilih langkah dengan skor tertinggi. mari coba kita liat lagi teori tadi :

Yup, kalian sudah lihat, hasilnya seperti teori kita di gambar diatas, dimana sang AI harusnya memilih langkat di kedalaman 0 di atas sendiri yang merupakan skor +1

Part Artikel

• Part 1 — Membuat Logic Game Tic-Tac-Toe
  https://medium.com/@viandwi24/membuat-ai-tictactoe-dengan-algoritma-minimax-javascript-part-1-3df454b70d18
• Part 3 — Finishing Game dengan membuat Board Table Responsive
  https://medium.com/@viandwi24/membuat-ai-tictactoe-dengan-algoritma-minimax-javascript-part-3-dd49078d3427?sk=3b340c3fca1bc38a6deae263d408b535

Untuk source code hasil, akan saya bagikan di part terakhir yah!

Berikut tutorial dari saya, di part selanjutnya kita akan membuat Tampilan HTML nya agar bisa dioperasikan dengan mudah!
Sekiat dari saya, Semoga Bermanfaat !