เกมสองผู้เล่นที่ดูเหมือนง่ายๆ ที่เกี่ยวข้องกับก้อนกรวดสีดำและสีขาวได้จุดประกายการอภิปรายที่น่าสนใจเกี่ยวกับรูปแบบทางคณิตศาสตร์ ลำดับอนันต์ และความซับซ้อนเชิงคำนวณ เกม anti-pattern ท้าทายผู้เล่นให้หลีกเลี่ยงการสร้างลำดับใดๆ ที่ซ้ำกันสามครั้งติดต่อกัน นำไปสู่การค้นพบที่ไม่คาดคิดเกี่ยวกับสิ่งที่นักคณิตศาสตร์เรียกว่าลำดับ cubefree
รากฐานทางคณิตศาสตร์ของเกม
เกม anti-pattern ทำงานตามกฎที่ดูเหมือนง่ายแต่หลอกลวง: ผู้เล่นผลัดกันวางก้อนกรวดสีดำหรือสีขาวเป็นแถว และใครก็ตามที่สร้างรูปแบบที่ซ้ำกันสามครั้งติดต่อกันจะแพ้ สิ่งที่ทำให้เกมนี้น่าสนใจทางคณิตศาสตร์คือความเชื่อมโยงกับลำดับ cubefree ซึ่งเป็นวัตถุทางคณิตศาสตร์ที่ได้รับการศึกษามานานกว่าหนึ่งศตวรรษ การอภิปรายในชุมชนเผยให้เห็นว่าลำดับเหล่านี้เป็นที่รู้จักอย่างเป็นทางการในวรรณกรรมทางคณิตศาสตร์ โดยนักวิจัยชี้ไปที่งานที่ได้รับการยอมรับซึ่งย้อนกลับไปถึงปี 1906
การวิเคราะห์เกมได้เปิดเผยกลยุทธ์ชนะสำหรับผู้เล่นคนแรก ซึ่งสามารถทำได้ในน้อยกว่า 22 ครั้ง อย่างไรก็ตาม คำถามที่น่าสนใจกว่านั้นเกิดขึ้นจากชุมชน: เกมสามารถดำเนินต่อไปได้ตลอดกาลในทางทฤษฎีหรือไม่หากผู้เล่นร่วมมือกันเพื่อหลีกเลี่ยงรูปแบบที่แพ้?
สรุปกฎของเกม
- ผู้เล่นสองคนสลับกันวางก้อนกรวดสีดำหรือสีขาวตามลำดับ
- ผู้เล่นแพ้หากสร้างรูปแบบที่ซ้ำกันสามครั้งติดต่อกัน
- ผู้เล่นคนแรกมีกลยุทธ์การชนะที่พิสูจน์แล้วในการเดินหมากไม่เกิน 22 ครั้ง
- เชื่อมโยงกับแนวคิดทางคณิตศาสตร์ของ "ลำดับปลอดลูกบาศก์"
เกมอนันต์และความลึกลับของการบีบอัด
หนึ่งในการค้นพบที่โดดเด่นที่สุดเกี่ยวข้องกับศักยภาพของเกมในการเล่นแบบอนันต์ นักวิจัยได้แสดงให้เห็นว่าผู้เล่นที่ร่วมมือกันสามารถสร้างลำดับที่ไม่เคยซ้ำกันสามครั้งได้จริง ซึ่งสร้างสิ่งที่ดูเหมือนข้อมูลสุ่มแต่มีโครงสร้างสูง ลำดับอนันต์เหล่านี้แสดงคุณสมบัติการบีบอัดที่น่าทึ่ง - ลำดับหนึ่งล้านครั้งสามารถบีบอัดให้เหลือเพียง 7.2 กิโลไบต์ ซึ่งแสดงอัตราส่วนการบีบอัดเกือบ 6,000 ต่อ 1
การบีบอัดได้อย่างพิเศษนี้เกิดจากลักษณะแบบเรียกซ้ำของลำดับ การบีบอัดแต่ละครั้งเผยให้เห็นรูปแบบพื้นฐานที่สามารถบีบอัดได้เอง สร้างชั้นของโครงสร้างทางคณิตศาสตร์ ปรากฏการณ์นี้เชื่อมโยงกับทฤษฎีความซับซ้อน Kolmogorov ซึ่งวัดเนื้อหาข้อมูลด้วยโปรแกรมที่สั้นที่สุดที่จำเป็นในการสร้างมัน
ประสิทธิภาพการบีบอัดข้อมูล
- การเคลื่อนไหวในเกม 1 ล้านครั้งสามารถบีบอัดเป็นไฟล์ขนาด 7.2KB
- อัตราส่วนการบีบอัด: ประมาณ 6,000:1
- สามารถทำการบีบอัดหลายรอบได้เนื่องจากโครงสร้างแบบเรียกซ้ำ
- การเคลื่อนไหว 100 ล้านครั้งจะสร้างไฟล์ที่ท้าทายโปรแกรมแก้ไขข้อความเมื่อคลายการบีบอัด
ความเชื่อมโยงกับจำนวนอดิศัย
การอภิปรายในชุมชนได้สำรวจว่าลำดับเกมเหล่านี้เกี่ยวข้องกับค่าคงที่ทางคณิตศาสตร์พื้นฐานหรือไม่ โดยการตีความก้อนกรวดสีดำและสีขาวเป็นเลขฐานสอง เกมจำกัดจะสร้างจำนวนตรรกยะ ในขณะที่เกมอนันต์จะสร้างจำนวนอตรรกยะ สิ่งนี้ทำให้เกิดคำถามที่น่าสนใจว่าจำนวนอตรรกยะใดบ้างที่สามารถแสดงผ่านลำดับเกมที่ถูกต้อง
จำนวนอตรรกยะบางจำนวนไม่ใช่เกมที่ถูกต้อง ตัวอย่างเช่น ฉันแน่ใจว่าการขยายของ π/4 ในเลขฐานสองมี 000 เป็นลำดับย่อยอยู่ที่ไหนสักแห่ง แต่นั่นไม่สามารถเกิดขึ้นในเกมได้ เพราะมันไม่อนุญาตให้มีการซ้ำของสตริงย่อยสามครั้งติดต่อกัน
ความสัมพันธ์ระหว่างจำนวนที่สร้างจากเกมและจำนวนอดิศัยยังคงเป็นคำถามที่เปิดอยู่ ซึ่งแสดงถึงประเภทของความลึกลับทางคณิตศาสตร์ที่เกิดขึ้นจากกฎที่ดูเหมือนง่าย
ความเชื่อมโยงทางคณิตศาสตร์
- ลำดับ Cubefree (ได้รับการศึกษามาตั้งแต่ปี 1906)
- ลำดับ Thue-Morse
- ทฤษฎีความซับซ้อนของ Kolmogorov
- ทฤษฎีคำดั้งเดิม (Primitive word theory)
- การจำแนกภาษาปลอดบริบท (Context-free language)
- ทฤษฎีจำนวนเหนือพีชคณิต (Transcendental number theory)
ผลกระทบทางคณิตศาสตร์ในวงกว้าง
เกมนี้เชื่อมโยงกับหลายพื้นที่ของการวิจัยทางคณิตศาสตร์ รวมถึงทฤษฎีคำดั้งเดิมและการจำแนกภาษาปลอดบริบท รูปแบบต่างๆ ของเกม - ที่เกี่ยวข้องกับสีมากขึ้น เกณฑ์การซ้ำที่แตกต่างกัน หรือผู้เล่นเพิ่มเติม - เปิดเส้นทางใหม่สำหรับการสืบสวน การปรับเปลี่ยนแต่ละครั้งสร้างความท้าทายทางคณิตศาสตร์ที่แตกต่างกันพร้อมผลลัพธ์ที่อาจแตกต่างกันเกี่ยวกับกลยุทธ์ชนะและความเป็นไปได้ของการเล่นแบบอนันต์
การวิจัยแสดงให้เห็นว่าคณิตศาสตร์เพื่อความบันเทิงสามารถนำไปสู่ข้อมูลเชิงลึกทางทฤษฎีที่จริงจังได้อย่างไร สิ่งที่เริ่มต้นเป็นเกมง่ายๆ ได้เผยให้เห็นความเชื่อมโยงที่ครอบคลุมทฤษฎีจำนวน ทฤษฎีสารสนเทศ และทฤษฎีภาษาเชิงรูปแบบ แสดงให้เห็นลักษณะที่เชื่อมโยงกันของความรู้ทางคณิตศาสตร์และคุณค่าของการสำรวจปัญหาที่ดูเหมือนเล็กน้อยอย่างลึกซึ้ง
อ้างอิง: The anti-pattern game