Tic Tac Toe games

Memainkan sebuah permainan merupakan sebuah konsep penelitian yang sangat populer dikalangan komunitas AI (kecerdasan buatan). Para peneliti di bidang itu telah mengembangkan beberapa metode pencarian untuk permainan. Metode-metode pencarian yang dikembangkan bisa berupa pencarian secara tradisional maupun secara heuristic yang lebih cerdas. Penelitian ini akan mencoba memfokuskan pada permainan sederhana yang dinamakan Tic-Tac-Toe. Algoritma genetika mempunyai ciri yaitu mampu membangun beberapa strategi pada berbagai situasi ,dan melalui aturan ’kemampuan bertahan hidup’, beberapa strategi yang tidak baik dapat dieliminasi sehingga hanya strategi baik yang dipakai.

Walaupun Tic-Tac-Toe merupakan sebuah permainan sederhana, penelitian ini akan mencoba menerapkan konsep algoritma genetika dan pembelajaran mesin untuk mencari strategi-strategi yang pas. Dikarenakan kemampuan algoritma genetika yang bagus, diharapkan parameter-parameter dan operator-operator yang dipilih mampu menyelesaikan masalah ini, juga dapat dipakai untuk menyelesaikan permasalahan bidang yang hampir sama terkait dengan permainan.

Permainan Tic-Tac-Toe sangatlah sederhana; diilhami oleh permainan anak-anak. Dimainkan pada papan berukuran 3 x 3. Pada awal permainan, papan dikosongkan. Kedua pemain, X dan O, akan menempatkan biji-bijinya keatas papan, sekali pasang satu biji. Pemain yang mampu menempatkan tiga bijinya dalam satu garis (vertikal, horizontal, diagonal) itulah yang menang. Dan dikatakan seri apabila papan telah penuh maupun tidak ada yang menang.

Umumnya, ada dua metode untuk memecahkan masalah semacam Tic-Tac-Toe. (1) metode tradisional dan (2) metode pengurutan dan pencarian Heuristic.

Untuk menyelesaikan permasalahan pencarian, penggunaan Pohon Keputusan merupakan langkah pertama yang bisa dilakukan, memperluas pohon permainan seluas mungkin, dan menganalisa tiap kemungkinan langkah dan hasilnya. Tiap percabangan juga dapat dianalisa menggunakan Algoritma Minimax yang akan membentuk sebuah fungsi untuk mengevaluasi tiap kemungkinan solusi dan memberikan nilai untuk langkah yang berpeluang memenangkan permainan. Kemungkinan terbesar untuk memenangkan permainan merupakan hasil dari penentuan langkah, dan langkah tersebut ditentukan oleh hasil evaluasi fungsinya.

Sebagai alternatif penyelesaian yang lain, beberapa aturan pencarian heuristic dapat digunakan untuk mengurangi beberapa cabang pohon dari pohon keputusan yang didapat sehingga terlihat lebih pendek. Contohnya menggunakan Depth First Search.