Thuật toán xáo bài của trò chơi FreeCell trên Windows

 (solitairelaboratory.com)
12 điểm bởi regentag 2024-10-25 | 8 bình luận | Chia sẻ qua WhatsApp

FreeCell trên Windows, trò mà hẳn nhiều người đã từng chơi, sắp xếp các lá bài theo thứ tự ngẫu nhiên và mỗi cách sắp xếp đều có một số đi kèm. Khi chọn cùng một số, cách sắp xếp bài sẽ giống hệt nhau.

Cho đến trước Windows 2000, trò chơi có các số từ 1 đến 32.000, nhưng từ XP trở đi đã được mở rộng lên đến 1.000.000.

Thuật toán tạo ra cách sắp xếp bài khi nhập số đã được công khai, nên cũng được sử dụng trong các chương trình FreeCell khác.

Thuật toán này được cài đặt bằng mã C ngắn gọn và phụ thuộc vào các hàm rand() và srand() do trình biên dịch của MS cài đặt.

Bài viết liên quan

8 bình luận

 
valorqueen 2024-10-25

Anh Tag chơi giỏi thật đấy.
 
qdr7h 2024-10-25

Thuật toán tạo số ngẫu nhiên ban đầu trông có vẻ là random, nhưng thực ra dùng một công thức truy hồi để tạo ra dãy số giả ngẫu nhiên, tức pseudo-random number, vốn không thật sự ngẫu nhiên. Mỗi cách hiện thực hàm rand() có thể khác nhau, nhưng gần như mọi thuật toán đều có chung đặc tính là nếu seed ban đầu giống nhau thì dãy số ngẫu nhiên sinh ra sau đó cũng sẽ giống hệt nhau. Vì vậy, nếu thuật toán sắp xếp bài là deterministic thì mọi cách sắp xếp bài đều được quyết định một cách deterministic bởi seed.

Hơi lạc đề một chút, nhưng việc có thể tạo ra pseudo-random number trông ngẫu nhiên đến mức nào cũng từng là một trong những chủ đề được nghiên cứu từ lâu. TAOCP Vol.2 cũng có đề cập ngắn gọn đến nội dung này.
 
kandk 2024-10-25

Thực ra trên máy tính không hề có khái niệm ngẫu nhiên thực sự.
Vì vậy thông thường người ta đo hành vi của con người theo đơn vị ms và dùng nó làm seed ngẫu nhiên.
 
dlehals2 2024-10-25

Tôi cứ nghĩ số ngẫu nhiên dùng timestamp của thời gian hiện tại, hóa ra là tôi đã hiểu nhầm rồi haha. Cảm ơn bạn đã chia sẻ.
 
regentag 2024-10-25

Khi khởi tạo thì nhiều người thường dùng thời gian làm seed. Vì thời gian luôn liên tục thay đổi mà.
 
regentag 2024-10-25

Xin lưu ý, trong phần trợ giúp của Windows có viết rằng: “Dù chưa được chứng minh, nhưng tất cả các ván chơi ở đây đều có lời giải”; tuy nhiên theo nỗ lực thử nghiệm của nhiều người, ván số 11982 đến nay vẫn được biết là không thể thắng.

Ngay cả sau mốc 32.000 cũng có những cách xếp bài được cho là không thể thắng, như các ván số 146692, 186216, 455889, 495505, 512118, 517776 và 781948.
 
namojo 2024-10-28

Không biết làm sao họ có thể ghi lại chuyện này mà vẫn không giải được nhỉ? Đúng là có nhiều người cực kỳ lì lợm!
 
bakyeono 2024-10-25

Đúng là những người đáng sợ...!