Tic Tac Toe

Vì tính đơn giản của tic-tac-toe, nó thường được sử dụng như một công cụ sư phạm để dạy các khái niệm về tinh thần thể thao tốt và nhánh của trí tuệ nhân tạo liên quan đến việc tìm kiếm cây trò chơi. Thật dễ dàng để viết một chương trình máy tính để chơi tic-tac-toe một cách hoàn hảo hoặc liệt kê 765 vị trí cơ bản khác nhau (độ phức tạp của không gian trạng thái) hoặc 26.830 trò chơi có thể có cho đến phép quay và phản xạ (độ phức tạp của cây trò chơi) trên không gian này. [1] Nếu được cả hai người chơi chơi một cách tối ưu, trò chơi luôn kết thúc với tỷ số hòa, khiến tic-tac-toe trở thành một trò chơi vô ích. [2]

Trò chơi có thể được khái quát thành một trò chơi m, n, k trong đó hai người chơi luân phiên đặt các viên đá có màu sắc của riêng họ lên một bảng m × n, với mục tiêu lấy k màu của riêng họ liên tiếp. Tic-tac-toe là trò chơi (3,3,3). [3] Tic-tac-toe tổng quát của Harary là sự khái quát thậm chí còn rộng hơn của tic-tac-toe. Nó cũng có thể được khái quát như một trò chơi thứ n. Tic-tac-toe là trò chơi trong đó n bằng 3 và d bằng 2. [4] Nó có thể được khái quát hơn nữa bằng cách chơi trên một cấu trúc tỷ lệ tùy ý, trong đó các hàng là dòng và ô là điểm. Tic-tac-toe là trò chơi được đưa ra bởi cấu trúc tỷ lệ hiển thị bên phải, bao gồm chín điểm, ba đường ngang, ba đường dọc và hai đường chéo, mỗi đường bao gồm ít nhất ba điểm.