Tic Tac Toe

Из-за простоты игры в крестики-нолики ее часто используют в качестве педагогического инструмента для обучения концепциям хорошего спортивного поведения и разделу искусственного интеллекта, который занимается поиском игровых деревьев. Несложно написать компьютерную программу для идеальной игры в крестики-нолики или перечислить 765 по существу различных позиций (сложность пространства состояний) или 26 830 возможных игр вплоть до вращений и отражений (сложность игрового дерева) на этом пространстве.[1] При оптимальной игре обоих игроков игра всегда заканчивается вничью, что делает крестики-нолики бесполезной игрой.[2]

Игру можно обобщить до игры m,n,k, в которой два игрока поочередно размещают камни своего цвета на доске m×n с целью получить k камней своего цвета в ряд. Крестики-нолики — это игра (3,3,3).[3] Обобщенные крестики-нолики Харари являются еще более широким обобщением крестиков-ноликов. Их также можно обобщить как игру nd. Крестики-нолики — это игра, в которой n равно 3, а d равно 2.[4] Их можно обобщить еще больше, играя на произвольной структуре инцидентности, где строки — это линии, а ячейки — это точки. Крестики-нолики — это игра, заданная структурой инцидентности, показанной справа, состоящей из девяти точек, трех горизонтальных линий, трех вертикальных линий и двух диагональных линий, каждая линия состоит как минимум из трех точек.