Game Tic-Tac-Toe (OX)

Tic-Tac-Toe (OX) adalah permainan kertas-dan-pensil untuk dua pemain, X dan O, yang bergiliran menandai ruang dalam kisi 3 × 3. Pemain yang berhasil menempatkan tiga tanda masing -masing dalam baris horizontal, vertikal, atau diagonal memenangkan permainan.

Pemain segera menemukan bahwa permainan terbaik dari kedua belah pihak mengarah ke hasil imbang (sering disebut sebagai game kucing atau kucing). Oleh karena itu, tic-tac-toe paling sering dimainkan oleh anak-anak kecil.

Kesederhanaan tic-tac-toe menjadikannya ideal sebagai alat pedagogis untuk mengajarkan konsep sportifitas yang baik dan cabang kecerdasan buatan yang berkaitan dengan pencarian pohon permainan. Sangat mudah untuk menulis program komputer untuk memainkan tic-tac-toe dengan sempurna, untuk menyebutkan 765 posisi yang pada dasarnya berbeda (kompleksitas ruang negara), atau 26.830 permainan yang mungkin hingga rotasi dan refleksi (kompleksitas pohon permainan) di ruang ini.

Permainan ini dapat digeneralisasi ke m, n, k-game di mana dua pemain bergantian menempatkan batu dengan warna mereka sendiri di papan m × n, dengan tujuan mendapatkan k warna mereka sendiri berturut-turut. Tic-tac-toe adalah (3,3,3) -game.