Tic Tac Toe

Karena kesederhanaan tic-tac-toe, permainan ini sering digunakan sebagai alat pedagogis untuk mengajarkan konsep sportivitas yang baik dan cabang kecerdasan buatan yang berhubungan dengan pencarian pohon permainan. Sangat mudah untuk menulis program komputer untuk memainkan tic-tac-toe dengan sempurna atau untuk menghitung 765 posisi yang pada dasarnya berbeda (kompleksitas ruang keadaan) atau 26.830 kemungkinan permainan hingga rotasi dan refleksi (kompleksitas pohon permainan) pada ruang ini.[1] Jika dimainkan secara optimal oleh kedua pemain, permainan selalu berakhir seri, membuat tic-tac-toe menjadi permainan yang sia-sia.[2]

Permainan ini dapat digeneralisasi menjadi permainan m,n,k di mana dua pemain secara bergantian menempatkan batu dengan warna mereka sendiri pada papan m×n, dengan tujuan mendapatkan k batu dengan warna mereka sendiri secara berurutan. Tic-tac-toe adalah permainan (3,3,3).[3] Tic-tac-toe umum Harary adalah generalisasi yang lebih luas dari tic-tac-toe. Ini juga dapat digeneralisasi sebagai permainan nd. Tic-tac-toe adalah permainan di mana n sama dengan 3 dan d sama dengan 2.[4] Ini dapat digeneralisasi lebih jauh dengan bermain pada struktur insidensi arbitrer, di mana baris adalah garis dan sel adalah titik. Tic-tac-toe adalah permainan yang diberikan oleh struktur insidensi yang ditunjukkan di sebelah kanan, yang terdiri dari sembilan titik, tiga garis horizontal, tiga garis vertikal, dan dua garis diagonal, setiap garis terdiri dari setidaknya tiga titik.