Game Tic Tac Toe - Grafik Komputer 2 (Tugas)

                Simbol atau karakter X dalam permainan tic tac toe ini adalah karakter yang dimainkan oleh pemain dalam hal ini user. Kita akan menempatkan X pada bidang papan yang telah disediakan.dalam peletakan simbol atau karakter X ini, kita akan selalu dihalangi oleh karakter O yang dimainkan oleh komputer agar tidak membentuk garis lurus. Kita harus menempatkan simbol X dengan benar agar dapat membentuk garis lurus.

Penyelesaian :

      Identifikasi ruang keadaan

Permasalahan dalam permainan ini dapat dilambangkan dengan (Papan berukuran 3X3 dengan 9 kotak, simbol X, dan simbol O).

      Keadaan awal dan tujuan

Keadaan awal             = Papan kosong.

Keadaan tujuan           = Simbol X dapat membentuk satu garis lurus(vertical, horisontal,   diagonal).

1.      1.  Aturan-aturan

                             I.      Papan yang kosong harus diisi dengan simbol X.

                           II.      Pengisian simbol dilakukan satu kali setiap giliran.

                         III.      Simbol X harus dapat membentuk satu garis lurus(vertical,horisontal,diagonal).

                         IV.      Halangi simbol O yang dimainkan oleh komputer agar tidak membentuk satu garis lurus(vertical,horisontal,diagonal).

2.     2.  Algoritma yang digunakan

Algoritma Minimax

Algoritma minimax merupakan metode yang sangat terkenal dalam pengambilan peluang kalah atau rugi. Algoritma minimax merupakan algoritma yang cukup terkenal dalam bidang kecerdasan buatan. Dimana dengan algoritma tersebut komputer dapat mengambil keputusan terbaik untuk menyelesaikan masalah. Masalah yang akan diangkat disini adalah AI untuk permainan tic-tac-toe , dimana AI tersebut tidak akan pernah kalah. Dengan algoritma minimax ini, pohon solusi akan dibuat dari awal permainan sampai akhir permainan dimana semua kemungkinan kondisi dijadikan simpul dari pohon solusi, sehingga AI tinggal memilih langkah yang akan menuntunnya ke hasil akhir

Algoritma Backtracking

Algoritma runut-balik (backtracking) adalah algoritma yang berbasis pada DFS untuk mencari solusi persoalan secara lebih mangkus. Runut-balik, yang merupakan perbaikan dari algoritma brute-force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Dengan metode runut-balik, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.Semua kemungkinan solusi dari persoalan disebut ruang solusi. Untuk memfasilitasi pencarian solusi ini,maka ruang solusi diorganisasikan dalam suatu struktur pohon Algoritma runut balik atau backtracking merupakan bentuk tipikal dari algoritma rekursif. Lintasan dari akar ke daun menyatakan solusi yang mungkin. Seluruh lintasan dari akar ke daun membentuk ruang solusi.

Konsep Permainan

Konsep permainan yang diterapkan dalam permainan ini adalah, pemain harus mampu meletakkan simbol yang dimainkannya dalam satu garis lurus baik secara vertikal, horisontal, maupun diagonal. Selain itu pemain juga dituntut agar mampu menghalangi komputer untuk melakukan hal yang serupa, yaitu meletakkan simbol yang dimainkan komputer dalam satu garis lurus. Pemain harus berhati-hati agar tidak lengah saat menyusun simbol yang dimainkannya, karena salain menghalangi jalan yang pemain mainkan, komputer juga tetap berusaha agar mampu meletakkan simbolnya dalam satu garis lurus baik secara vertikal, horisontal, maupun secara diagonal.

            Dalam permainan ini terdapat papan berukuran 3X3 yang berisikan 9 kotak untuk diisikan simbol oleh pemain. Untuk menyelesaikan permainan ini, pemain cukup meletakkan simbolnya dalam satu garis lurus. Ketika pemain mulai meletakkan simbolnya maka komputer akan dengan segera memulai gilirannya.Pemain dapat meletakkan simbol ditempat yang sesuai dengan keinginannya dengan menggunakan mouse, yaitu dengan cara mengklik kotak yang ingin diletakkan simbol.

Pada permainan ini komputer dibekali dengan knowledge berupa perhitungan minimax, knowledge 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. Dan untuk setiap langkahnya, komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum.Komputer akan selalu menghalangi jalan pemain agar jangan sampai membuat satu garis lurus, dan apabila komputer mampu lebih dulu untuk membuat satu garis lurus, maka pemain akan kalah.

credit image:
chessandpoker.com