Tic-tac-toe (còn gọi là noughts và thánh giá hoặc Xs và Os) là một trò chơi giấy và bút chì cho hai người chơi, X và O, người thay phiên nhau đánh dấu khoảng trống trong một mạng lưới 3 × 3. Người chơi thành công trong việc đặt ba nhãn hiệu của họ trong một hàng ngang, dọc hoặc chéo thắng trò chơi.
Các trò chơi ví dụ sau đây là chiến thắng của các cầu thủ đầu tiên, X:
Game of Tic-tac-toe, thắng X
Người chơi sớm khám phá ra rằng vở kịch tốt nhất từ cả hai bên dẫn đến một trận hòa. Do đó, tic-tac-toe thường được chơi bởi trẻ nhỏ.
Bởi vì sự đơn giản của tic-tac-toe, nó thường được sử dụng như một công cụ sư phạm cho giảng dạy các khái niệm về tinh thần thể thao tốt và chi nhánh của trí tuệ nhân tạo mà đề cập đến việc tìm kiếm cây trò chơi. Nó là đơn giản để viết một chương trình máy tính để chơi tic-tac-toe hoàn hảo, để liệt kê các 765 vị trí cơ bản khác nhau (không gian phức tạp nhà nước), hoặc 26.830 trò chơi có thể lên đến quay và phản xạ (độ phức tạp cây trò chơi) trên không gian này . [1]
Các trò chơi có thể được khái quát hóa cho một m, n, k-trò chơi, trong đó hai người chơi luân phiên đặt viên đá màu sắc riêng của họ trên một m × board n, với mục tiêu nhận được k màu sắc riêng của họ trong một hàng. Tic-tac-toe là (3,3,3) -Game. [2] khái quát hóa tic-tac-toe Harary là một sự tổng quát thậm chí rộng hơn về toe tic tac. Nó cũng có thể được khái quát như một trò chơi thứ. Tic-tac-toe là trò chơi trong đó n bằng 3 và d = 2. [3] Nếu chơi đúng cách, các trò chơi sẽ kết thúc trong một trận hòa làm tic-tac-toe một trò chơi vô ích.