Algoritma pada Permainan Tic Tac Toe dalam Aplikasi Kecerdasan Buatan

April 13, 2010 at 4:43 pm (1)

Dalam program Tic Tac Toe akan digunakan algoritma minimax 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 langkahlangkah 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.

Berikut garis besar algoritma minimax secara umum :

Cari langkah yang dengan nilai maksimum IF langkah tersebut merupakan langkah kemenangan THEN pilih lagkah tersebut. ELSE FOR EACH kemungkinan langkah yang ada Cari langkah lawan yang bernilai minimum. RETURN nilai dari langkah tersebut. Pilih langkah yang bernilai maksimum dari langkah-langkah tersebut. 2

Pemakaian algoritma umum diatas untuk permainan tic- tac-toe adalah sebagai berikut :

IF ada langkah kemenangan THEN pilih langkah tersebut. ELSE IF lawan mempunyai 2 spot terisi dalam satu garis dengan spot ketiga masih kosong THEN tutup langkah tersebut (isi spot kosong ketiga tersebut). ELSE melangkah ke state yang mempunyai kemungkinan menang tertinggi (berdasarkan nilai heuristic yang dibangkitkan). 2