Algoritma
Implementasi algoritma yang digunakan dalam permainan ini yaitu algoritma minimax yang menunjukkan konsep AI dalam permainan ini.
Algoritma Minimax
Algoritma minimax merupakan basis dari semua permainan berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia sekalipun. Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut berhubung kombinasi kemungkinan untuk sebuah permainan catur pada setiap geraknya sangat banyak sekali. Berbeda dengan permainan catur, permainan tic-tac-toe ini mempunyai lebih sedikit kemungkinan solusi, sehingga kita akan mempunyai cukup komputasi untuk memainkan setiap kombinasi langkah dari setiap posisi dan kondisi. Namun hal ini dapat dihindari dengan membatasi sejauh mana komputer akan menganalisis hasil dari langkah - langkah yang mungkin ( menentukan kedalaman pohon ). Tetapi dengan hal ini, kita harus menambah kedalaman pohon tersebut setiap langkahnya agar kedalaman pohon pada state tersebut sama dengan state sebelumnya. Algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini berarti, pada langkah pertama komputer akan menganalisis seluruh pohon permainan. Untuk setiap langkahnya, komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya pada permainan tic-tac-toe ini digunakan nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Misalnya ada 2 pemain A dan B. Jika pemain A bisa mendapatkan poin dalam 1 langkah, maka langkah tersebut adalah langkah penambahan pundi-pundi poinnya. Jika pemain B mengetahui bahwa langkah tersebut akan mengarahkan pemain A mendapatkan poin, dan di lain kondisi ada langkah lain yang akan mengarahkan ke hasil akhir seri atau pemain B tidak mendapatkan poin, maka langkah terbaik untuk pemain B adalah langkah yang akan mengarahkan hasil akhir permainan ke hasil seri atau tidak mendapatkan poin. Di setiap tahap algoritma ini mengasumsikan bahwa pemain A mencoba untuk memaksimalisasi peluang menang. Di lain pihak, pada giliran berikutnya pemain B akan mencoba meminimalisir peluang menang untuk pemain A. Oleh karena itu, A disebut juga maximizing player ( MAX ) dan B disebut juga minimizing player ( MIN ).
Representasi pohon pencarian pada algoritma minimax
Pembentukan pohon pencarian solusi digunakan dengan menggunakan konsep depth - first search, dimulai dari awal permainan sampai akhir permainan. Proses yang dilakukan bergantian yaitu mencari nilai minimum, kemudian pada node - parent dilakukan pencarian untuk nilai maksimum. Setelah itu nilai dari setiap simpul diisi dari bawah ke atas dengan nilai yang sudah dievaluasi oleh fungsi heuristic. Simpul milik pemain A ( MAX ) menerima nilai maksimum dari simpul-simpul anaknya. Simpul milik pemain B ( MIN ) akan memilih nilai minimum dari simpul anak - anaknya. Values disini merepresentasikan suatu langkah terbaik dalam permainan ini. Jadi, pemain A ( MAX ) akan memilih langkah dengan nilai paling tinggi diakhir. Di sisi lain, pemain B ( MIN ) akan melakukan serangan balik dengan memilih langkah yang terbaik untuknya, yakni meminimalisir hasil dari langkah yang dipilih pemain A.
Berikut ini algoritma yang digunakan dalam permainan ini :
1. Tempatkan simbol yang digunakan pada salah satu kotak secara acak.
2. Atur posisi simbol agar membentuk salah satu garis ( vertikal, horizontal, atau diagonal ).
3. Simbol lain dapat mem - block simbol lain agar tidak dapat membentuk salah satu garis dengan cara meletakkan simbol yang berbeda kedalam garis tersebut.
4. Jika terdapat 3 simbol yang sama berada dalam salah satu garis ( vertikal, horizontal, dan diagonal ) maka pemain akan mendapatkan poin.
5. Jika semua ruang sudah terisi oleh kedua waran maka permainan berakhir,
Free Template Blogger collection template Hot Deals BERITA_wongANteng SEO theproperty-developer
Implementasi algoritma yang digunakan dalam permainan ini yaitu algoritma minimax yang menunjukkan konsep AI dalam permainan ini.
Algoritma Minimax
Algoritma minimax merupakan basis dari semua permainan berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia sekalipun. Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut berhubung kombinasi kemungkinan untuk sebuah permainan catur pada setiap geraknya sangat banyak sekali. Berbeda dengan permainan catur, permainan tic-tac-toe ini mempunyai lebih sedikit kemungkinan solusi, sehingga kita akan mempunyai cukup komputasi untuk memainkan setiap kombinasi langkah dari setiap posisi dan kondisi. Namun hal ini dapat dihindari dengan membatasi sejauh mana komputer akan menganalisis hasil dari langkah - langkah yang mungkin ( menentukan kedalaman pohon ). Tetapi dengan hal ini, kita harus menambah kedalaman pohon tersebut setiap langkahnya agar kedalaman pohon pada state tersebut sama dengan state sebelumnya. Algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini berarti, pada langkah pertama komputer akan menganalisis seluruh pohon permainan. Untuk setiap langkahnya, komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya pada permainan tic-tac-toe ini digunakan nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.
Misalnya ada 2 pemain A dan B. Jika pemain A bisa mendapatkan poin dalam 1 langkah, maka langkah tersebut adalah langkah penambahan pundi-pundi poinnya. Jika pemain B mengetahui bahwa langkah tersebut akan mengarahkan pemain A mendapatkan poin, dan di lain kondisi ada langkah lain yang akan mengarahkan ke hasil akhir seri atau pemain B tidak mendapatkan poin, maka langkah terbaik untuk pemain B adalah langkah yang akan mengarahkan hasil akhir permainan ke hasil seri atau tidak mendapatkan poin. Di setiap tahap algoritma ini mengasumsikan bahwa pemain A mencoba untuk memaksimalisasi peluang menang. Di lain pihak, pada giliran berikutnya pemain B akan mencoba meminimalisir peluang menang untuk pemain A. Oleh karena itu, A disebut juga maximizing player ( MAX ) dan B disebut juga minimizing player ( MIN ).
Representasi pohon pencarian pada algoritma minimax
Pembentukan pohon pencarian solusi digunakan dengan menggunakan konsep depth - first search, dimulai dari awal permainan sampai akhir permainan. Proses yang dilakukan bergantian yaitu mencari nilai minimum, kemudian pada node - parent dilakukan pencarian untuk nilai maksimum. Setelah itu nilai dari setiap simpul diisi dari bawah ke atas dengan nilai yang sudah dievaluasi oleh fungsi heuristic. Simpul milik pemain A ( MAX ) menerima nilai maksimum dari simpul-simpul anaknya. Simpul milik pemain B ( MIN ) akan memilih nilai minimum dari simpul anak - anaknya. Values disini merepresentasikan suatu langkah terbaik dalam permainan ini. Jadi, pemain A ( MAX ) akan memilih langkah dengan nilai paling tinggi diakhir. Di sisi lain, pemain B ( MIN ) akan melakukan serangan balik dengan memilih langkah yang terbaik untuknya, yakni meminimalisir hasil dari langkah yang dipilih pemain A.
Berikut ini algoritma yang digunakan dalam permainan ini :
1. Tempatkan simbol yang digunakan pada salah satu kotak secara acak.
2. Atur posisi simbol agar membentuk salah satu garis ( vertikal, horizontal, atau diagonal ).
3. Simbol lain dapat mem - block simbol lain agar tidak dapat membentuk salah satu garis dengan cara meletakkan simbol yang berbeda kedalam garis tersebut.
4. Jika terdapat 3 simbol yang sama berada dalam salah satu garis ( vertikal, horizontal, dan diagonal ) maka pemain akan mendapatkan poin.
5. Jika semua ruang sudah terisi oleh kedua waran maka permainan berakhir,
Free Template Blogger collection template Hot Deals BERITA_wongANteng SEO theproperty-developer
