井字棋，英文名叫Tic-Tac-Toe，是一种在3*3格子上进行的连珠游戏，和五子棋比较类似，由于棋盘一般不画边框，格线排成井字故得名。游戏需要的工具仅为纸和笔，然后由分别代表O和X的两个游戏者轮流在格子里留下标记（一般来说先手者为X）。由最先在任意一条直线上成功连接三个标记的一方获胜。比如像下图这样：玩过这个游戏的人大都会发现，如果两个玩家都作出最好的选择，这个游戏是一定会平局的。所以，井字棋最常使用是作为儿童游戏。虽然这个游戏看上去很简单，但是它的整个过程却复杂得多。从理论上讲，“井字棋”一共可能有19683种现象和362880种过程。（如果不把追求获胜的判定算进去的话）当获胜导致游戏结束时，就只剩下255168种可能过程。假设其中X都是先手：那么其中131184次将为X获胜，77904次将为O获胜，46080次为平局。而当无视O和X的序列并消除所有对称的情况，就只剩下138种可能的结果了，其中91次是由X获胜，44次是由O获胜，只有3个独特的情况下才产生平局。
