อัลกอริทึมการสับไพ่ของเกม Freecell บน Windows
(solitairelaboratory.com)Freecell บน Windows ที่หลายคนน่าจะเคยเล่น จะจัดเรียงไพ่แบบสุ่ม และการจัดเรียงไพ่แต่ละแบบจะมีหมายเลขกำกับอยู่ เมื่อเลือกหมายเลขเดียวกัน ไพ่ก็จะถูกจัดเรียงเหมือนเดิม
ก่อน Windows 2000 จะมีหมายเลขตั้งแต่ 1~32,000 แต่หลัง XP ได้เพิ่มขึ้นเป็น 1,000,000
อัลกอริทึมที่ใช้สร้างการจัดเรียงไพ่เมื่อป้อนหมายเลขนั้นถูกเปิดเผยไว้ จึงถูกนำไปใช้ในโปรแกรม Freecell อื่น ๆ ด้วย
อัลกอริทึมนี้ถูกเขียนเป็นโค้ด C สั้น ๆ และขึ้นอยู่กับฟังก์ชัน rand() และ srand() ที่คอมไพเลอร์ของ MS ใช้งานอยู่
8 ความคิดเห็น
คุณแท็กเก่งจังเลยนะ
เดิมทีอัลกอริทึมสร้างเลขสุ่มนั้นแม้จะดูเหมือนเป็น random แต่ที่จริงแล้วใช้สมการเวียนเกิดที่สร้างลำดับของ pseudo-random number ซึ่งไม่ได้สุ่มจริงทั้งหมด การทำงานจะแตกต่างกันไปตาม implementation ของฟังก์ชัน
rand()แต่คุณสมบัติที่แทบทุกอัลกอริทึมมีร่วมกันคือ ถ้า seed ตัวแรกเหมือนกัน ลำดับเลขสุ่มที่ตามมาก็จะเหมือนกันด้วย ดังนั้นถ้าอัลกอริทึมจัดเรียงไพ่เป็นแบบ deterministic การจัดเรียงไพ่ทั้งหมดก็ย่อมถูกกำหนดแบบ deterministic ด้วย seed เช่นกันเป็นเรื่องที่ออกนอกประเด็นไปเล็กน้อย แต่การจะสร้าง pseudo-random number ที่ดูเป็นการสุ่มได้มากแค่ไหนก็เป็นหนึ่งในหัวข้อวิจัยมาอย่างยาวนานเช่นกัน ใน TAOCP Vol.2 ก็มีพูดถึงเรื่องนี้แบบสั้น ๆ เช่นกัน
จริง ๆ แล้วในคอมพิวเตอร์ไม่มีแนวคิดเรื่องความสุ่มอย่างแท้จริง
ดังนั้นโดยทั่วไปจึงมักวัดพฤติกรรมของคนในระดับมิลลิวินาที แล้วนำค่านี้ไปใช้เป็น random seed
ผมเคยเข้าใจว่าตัวเลขสุ่มใช้ timestamp ของเวลาปัจจุบัน ที่แท้ก็เข้าใจผิดนี่เอง 555 ขอบคุณที่แชร์ครับ
ตอนเริ่มต้นก็มักจะใช้เวลาเป็น seed กันเยอะนะครับ เพราะเวลามันเปลี่ยนไปเรื่อย ๆ
ขอเสริมว่าในวิธีใช้ของ Windows เขียนไว้ว่า “แม้จะยังไม่ได้รับการพิสูจน์ แต่ทุกเกมที่เล่นที่นี่มีวิธีแก้” อย่างไรก็ตาม จากความพยายามของผู้เล่นหลายคน เชื่อกันว่าดีลหมายเลข 11982 เป็นเกมที่ยังไม่สามารถชนะได้จนถึงตอนนี้。
แม้แต่หลังจากเลข 32,000 ไปแล้ว ก็ยังมีการจัดเรียงไพ่ที่เชื่อกันว่าไม่สามารถชนะได้ เช่น หมายเลข 146692, 186216, 455889, 495505, 512118, 517776 และ 781948.
ไม่สิ เขาไปค้นพบได้ยังไงกันนะว่าเขียนเรื่องนี้ทิ้งไว้แล้วแต่กลับแก้ไม่ได้น่ะ? มีคนโหด ๆ เยอะจริง ๆ!
พวกคนที่น่ากลัว...!