FreeCell

FreeCell là một trò chơi bài solitaire được chơi trên bộ bài tiêu chuẩn 52 lá. Điểm khác nhau cơ bản của trò này so với hầu hết các trò chơi bài solitaire là rất ít cách chia bài dẫn đến việc thua không thể chơi tiếp được, và tất cả các lá bài đều được lật mặt lên trên ngay từ đầu. Mặc dù các phiên bản phần mềm có khác nhau, hầu hết các phiên bản đều gắn cho các cách chia bài bằng một con số (bắt nguồn từ giá trị hạt giống được bộ sinh số giả ngẫu nhiên để xáo trộn bài).
Microsoft đã đưa vào một trò chơi máy tính FreeCell trên tất cả các bản phát hành hệ điều hành Windows từ năm 1995, góp phần rất lớn vào sự phổ biến của trò chơi. Điều này đúng với nhiều người chơi FreeCell đến nỗi nhiều phần mềm FreeCell khác cũng cố gắng tạo khả năng tương thích với bộ sinh số giả ngẫu nhiên của phiên bản Windows để mô phỏng lại cách chia bài của phần mềm trên.

Lịch sử

Một trong những trò chơi tổ tiên lâu đời nhất của FreeCell là Eight Off.Trong ấn bản tháng 6 năm 1968 của Scientific American, Martin Gardner mô tả trong mục "Trò chơi toán học" rằng một trò chơi của C. L. Baker tương tự như FreeCell, ngoại trừ các lá bài trên tableau được xây dựng đồng chất thay vì đảo màu của lá bài. Gardner viết, "Trò chơi do Baker học từ cha mình, người đã học chơi nó từ một người Anh trong những năm 1920." Biến thể này giờ được gọi là Trò chơi của Baker. Nguồn gốc của FreeCell có thể bắt đầu từ năm 1945 và một trò chơi Scandinavian có tên Napoleon ở St. Helena (không phải trò chơi Napoléon tại St. Helena, còn được gọi là trò Bốn mươi tên cướp).
Paul Alfille đã thay đổi trò chơi của Baker bằng cách thay đổi luật xếp lá bài bằng cách đảo màu, và đã tạo ra trò FreeCell. Ông đã viết phiên bản máy tính đầu tiên của trò này bằng ngôn ngữ lập trình TUTOR cho hệ thống máy tính giáo dục PLATO vào năm 1978. Alfille có thể hiển thị hình ảnh đồ họa dễ dàng nhận biết của các lá bài trên màn hình đơn sắc 512 × 512 trên hệ thống PLATO.
Phiên bản FreeCell ban đầu này cho phép các trò chơi có 4–10 cột và 1–10 ô ngoài trò chơi chuẩn 8 × 4. Đối với mỗi biến thể, chương trình lưu trữ một danh sách xếp hạng người chơi có chuỗi chiến thắng dài nhất. Ngoài ra còn có một hệ thống giải đấu cho phép mọi người cạnh tranh để chiến thắng các cách chia bài khó được chọn thủ công. Paul Alfille mô tả phiên bản FreeCell ban đầu này chi tiết hơn trong một cuộc phỏng vấn từ năm 2000.
Năm 2012, các nhà nghiên cứu đã sử dụng các phương pháp tính toán tiến hóa để tạo ra những chương trình chơi thắng trò FreeCell.

Độ phức tạp của chương trình giải bài toán

Trò chơi FreeCell có số lượng lá bài không đổi. Điều này ngụ ý rằng trong thời gian không đổi, một người hoặc một máy tính có thể liệt kê tất cả các chuyển động có thể có từ một cấu hình bắt đầu cho trước và khám phá một tập hợp cách đi để chiến thắng hoặc khẳng định là trò chơi không thể giải quyết được. Để thực hiện một phân tích phức tạp thú vị, người ta phải xây dựng một phiên bản tổng quát của trò chơi FreeCell với 4 × n lá bài. Phiên bản tổng quát của trò chơi này có độ phức tạp là NP-đầy đủ; nó không chắc rằng bất kỳ thuật toán nào hiệu quả hơn so với một tìm kiếm toàn bộ tồn tại mà có thể tìm thấy các giải pháp cho các cách chia bài FreeCell tổng quát tùy ý.
Có 52! (52 giai thừa), hoặc xấp xỉ 8×10⁶⁷, cách chia bài. Tuy vậy một số cách chia bài là giống hệt nhau vì các chất của các lá bài có thể hoán đổi cho nhau và các cột quân bài có thể đổi chỗ tùy ý. Sau khi loại bỏ các trường hợp trên chúng ta còn xấp xỉ 1.75×10⁶⁴ cách chia bài FreeCell.