FreeCell

Một ván chơi FreeCell trên phần mềm KDE

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,^[1] và tất cả các lá bài đều được lật mặt lên trên ngay từ đầu.^[2] 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.^[3]

Luật chơi

Chia bài và cách xếp bài

• Một bộ bài 52 lá tiêu chuẩn được sử dụng.
• Có bốn ô mở và bốn dãy quân bài để mở. Một số quy tắc thay thế sử dụng từ một đến mười ô.
• Thẻ được chia ngửa mặt lên trên, xếp thành tám cột, bốn trong số đó có bảy lá và bốn trong số đó có sáu lá. Một số quy tắc thay thế sẽ sử dụng từ bốn đến mười cột.

Xây bài trong quá trình chơi

• Các thẻ hàng đầu của mỗi thác bắt đầu với một chuỗi bài.
• Chuỗi bắt buộc phải được xây từ trên xuống dưới với màu sắc xen kẽ đen-đỏ 
• Dãy quân bài xếp theo thứ tự chất (cơ rô bích nhép, hay cơ rô bích chuồn).

Cách di chuyển

• Bất kỳ bài trong khung hoặc bài hàng đầu của bất kỳ dãy bài nào đều có thể được di chuyển để vào một ô trống, một thác bài trống hoặc ra dãy quân bài theo thứ tự chất.
• Toàn bộ hoặc một phần dãy bài đảo màu có thể được di chuyển để xây dựng trên dãy bài hiện có, hoặc di chuyển đến thác bài rỗng, bằng cách đặt và loại bỏ các lá bài thông qua các ô trung gian một cách đệ quy. Các phiên bản chơi dùng máy tính thường hiển thị từng chuyển động này, nhưng người chơi sử dụng bài lá thật bằng giấy thường di chuyển cả một dãy bài cùng một lúc.

Chiến thắng

• Trò chơi được tính là thắng khi tất cả các lá bài được di chuyển vào cột bài có chất tương ứng.

Không phải tất cả các cách chia bài đều có thể thắng được, nhưng xác suất này là rất thấp. Người ta ước tính rằng 99,999% cách chia bài đều có thể thắng được.

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."^[4] 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).^[2]

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.^[5]

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.^[6]

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.^[7]

Độ 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 đủ;^[8] 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.^[2]

Chú thích

1. . ISBN 9780470487631 https://books.google.com/books?id=BjhFgc4DdjIC&pg=PA293. |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
2. ^ Keller, Michael (ngày 4 tháng 8 năm 2015). “FreeCell -- Frequently Asked Questions (FAQ)”. Solitaire Laboratory. Truy cập ngày 7 tháng 2 năm 2017.
3. “PySol - Rules for Freecell”. PySolFC documentation. Truy cập ngày 3 tháng 2 năm 2018.
4. Gardner, Martin (tháng 6 năm 1968). “Mathematical Games”. Scientific American. 218 (6): 114. doi:10.1038/scientificamerican0668-112.
5. Kaye, Ellen (ngày 17 tháng 10 năm 2002). “One Down, 31,999 to Go: Surrendering to a Solitary Obsession”. New York Times.
6. Cronin, Dennis (ngày 4 tháng 5 năm 2000). “Interview with Paul Alfille”. Freecell.net. Truy cập ngày 4 tháng 3 năm 2011.
7. Elyasaf, Achiya; Hauptman, Ami; Sipper, Moshe (tháng 12 năm 2012). “Evolutionary Design of FreeCell Solvers” (PDF). IEEE Transactions on Computational Intelligence and AI in Games. 4 (4): 270–281. doi:10.1109/TCIAIG.2012.2210423.
8. Helmert, Malte (tháng 3 năm 2003). “Complexity results for standard benchmark domains in planning”. Artificial Intelligence. 143 (2): 219–262. doi:10.1016/S0004-3702(02)00364-8.

Đọc thêm

• “OHSU scientists say FreeCell can be adapted to spot early signs of dementia”. Oregon Health & Science University. Bản gốc lưu trữ ngày 27 tháng 2 năm 2021. Truy cập ngày 1 tháng 6 năm 2017.
• O'Hale, Marty M. (ngày 14 tháng 8 năm 2007). “The Four Virtues of FreeCell”. The Escapist Magazine. Bản gốc lưu trữ ngày 8 tháng 8 năm 2011. Truy cập ngày 9 tháng 6 năm 2012.