หนึ่งในเกมในวินโดวส์ที่หลายๆคนรู้จัก (รองจากโซลิแทร์/เกมไพ่) แต่ไม่ค่อยได้ให้ความใส่ใจกับมันซักเท่าไร นั้นคือเกมนักเก็บกู้ระเบิด minesweeper ซึ่งมันจะแถมมากับระบบปฏิบัติการ Windows แทบจะทุก windows โดยเฉพาะรุ่นเก่าๆ เกมนี้จึงน่าจะผ่านหูผ่านตาของใครหลายๆคนมาบ้างแล้วนะครับ มันเป็นเกมที่อยู่ใกล้ตัวมาก และแน่นอน! มีไม่กี่คนที่จะสนใจเล่นมันจริงๆจังๆ และยังมีอีกหลายคนที่ไม่รู้แม้กระทั่งวิธีเล่น สำหรับผมเองก็คิดว่ามันเป็นเกมฆ่าเวลาที่ดีเกมหนึ่งเอาไว้สำหรับฝึกสมาธิ คือผิดพลาดนิดเดียวนี้ถึงกับต้องเริ่มใหม่ ความพยายามนั่งเล่นเกมนึงประมาณครึ่งชั่วโมง ก็พังทลายไปทันที > <
เรามาเริ่มจากการทำความรู้จักกับมันหน่อยดีกว่านะครับ
ไมน์สวีปเปอร์ จะประกอบด้วยรูปสี่เหลี่ยม แล้วใต้ช่องสี่เหลี่ยมเป็นบางช่องจะซ่อนระเบิดไว้ข้างใน เป้าหมายของเราคือการหาให้ได้ว่าระเบิดอยู่ที่ช่องใดบ้างโดยคำใบ้ของเราคือ ตัวเลขในแต่ละช่องที่ถูกเปิดออก ตัวเลขพวกนั้นบอกว่าบริเวณช่อง 8 ช่องที่ล้อมรอบตัวมันอยู่นั้นมีระเบิดอยู่กี่ลูก แต่ถ้าเราเปิดไปเจอกับช่องที่ไม่มีระเบิดอยู่แวดล้อมเลยมันก็จะเปิดช่องที่อยู่ล้อมทั้งหมดให้ทันที
หลักการและเทคนิคที่ผมเองใช้เล่น คือการมองไปยังตัวเลขแต่ละตัวว่าเราปักระเบิดไปครบทุกช่องหรือยัง ถ้าครบแล้วช่องแวดล้อมอื่นๆ จะยังไม่ได้ปักจะเป็นช่องปลอดภัยและเราก็จะใช้ตัวเลขจากช่องที่เปิดใหม่พวกนั้นคาดเดาระเบิดลูกต่อๆไปจนครบทั้งกระดาน โดยไม่มีการเดา
ว่าแล้วเรามาลองปริศนาบน minesweeper กันซะหน่อยดีกว่า
คำถามคือถ้าให้ไม่มีการเปิดอีกนั้นถามว่าระเบิดอยู่ตำแหน่งไหนบ้าง ดูสิว่าคุณจะรู้ไหม
สำหรับเกมแบบนี้ทางออกทางเดียวก็คือการสมมติครับ นึกอะไรไม่ออกก็ให้มีระเบิดอยู่ในตำแหน่งมุมบนซ้าย (1,1) กันก่อนดีกว่า
ถ้ามีระเบิดอยู่ตรงนั้น จากข้อมูลเลขสองที่อยู่ด้านล่าง (2,2) บอกได้ว่าจะต้องมีระเบิดอีกลูกอยู่ที่ตำแหน่งสองช่องบนตัวมันหรือสองช่องทางซ้ายอย่างใดอย่างหนึ่ง ถ้าระเบิดอยู่ในช่องทางซ้าย ทางบนทั้งสองจะว่าง แต่เลขสอง ทางขวา (2,3) บอกว่าสามช่องที่อยู่บนมันนั้นมีระเบิดสองลูกแต่ ดันเป็นที่ว่างซะสองแล้ว ดังนั้นจึงเกิดข้อขัดแย้ง
ในลักษณะเดียวกันมุมทุกมุมจึงต้องเป็นที่ว่าง เมื่อเรารู้ว่ามุมเป็นที่ว่างต่อมาเราลองให้ช่องถัดจากมุม (1,2) มีระเบิดบ้าง
เพื่อไม่ให้ขัดแย้งกับเลขสองตัวเดิมที่มุมอีก (2,2) ทำให้ช่องทางซ้าย (1,3) จะต้องเป็นช่องว่า (1,4) และ (1,5) จึงตืองมีระเบิดแต่มันดันไปแย้งกับเลขสองทางขวาสุด (2,5) และ (3,5) ในทำนองเดิมอีก ทำให้เรารู้ได้ว่าระเบิดไม่ได้อยู่ในช่องที่เราสมมติไว้ตอนแรก และในทำนองเดียวกัน ทำให้ช่องที่อยู่ติดกับช่องมุมทุกช่องไม่มีระเบิด เหลือให้เราเพียงแบบเดียวนั้นคือ
เป็นอันว่าจบคำถามครับ
น่าจะเริ่มเป็นกันแล้วที่นี้ลองอีกซักข้อนะครับ
ถ้าเรามีตารางเช่นนี้ถามว่า ตำแหน่ง (2,3) มีระเบิดอยู่หรือไม่
เฉลยก็คือ มันว่างไม่มีระเบิดครับ
ถามว่าทำอย่างไงเราถึงจะได้คำตอบของคำถามนี้ละ
ขั้นแรกเราติ๊กช่องที่จะมีระเบิดกันก่อน
แล้วก็จะมีตำแหน่งที่เรายังไม่รู้อีกมากนะครับ คำถามย่อยที่ขึ้นมาก็คือ (5,7) มีระเบิดหรือไม่
ถ้าเกิดมันไม่มีระเบิดเราจะสามารถใช้ผลพวงไปได้โดยง่าย
แต่ถ้าไม่ละ
ถ้าเกิดมีระเบิดละ
เราก็จะได้ผลพวงที่ตามมาจากการมีระเบิดมากมายตามรูป แล้วก็คำถามอีกข้อคือ (5,2) ละมีระเบิดหรือไม่
ถ้ามีระเบิดผลพวงที่ตามมาคือ ช่อง(2,3) ที่เราตามหา จะเป็นช่องว่างไม่มีระเบิด
แต่ถ้า ช่อง (5,2) ไม่มีระเบิดบ้างละ ก็จะมีปัญหาอยู่นิดหน่อยเพิ่มขึ้น
แต่ถ้าเราแจกแจงกรณีดูเราก็จะเห็นได้ว่าไม่มีกรณีไหนที่จะทำให้จุด (2,3) นั้นมีระเบิดโดยไม่เกิดข้อขัดแย้งกับเลขสี่ ห้า หก ทางขวานั้นได้เลย ดังนั้น
(2,3) ไม่มีจะกรณีใด มันจะเป็นช่องว่างเสมอ
Minesweeper สำคัญอย่างไร
จากตรงนี้ผมจะขอเสนอให้พวกท่านได้รู้จักกับสมการอีกซักอันหนึ่งครับนั้นคือ
หรือ
เข้าใจไหมละครับ เมือเราเอาเกม minesweeper มาใส่ความรู้คณิตศาสตร์มากๆเข้า มันก็จะกลายมาเป็นเงินล้านให้เราอย่างไงละ อ่าหลายคนเริ่มสงสัยเพิ่มขึ้นมามันจะออกมาเป็นเงินให้เราได้อย่างไง นั้น นั้นก็เพราะว่าการเล่น Minesweeper เกี่ยวพันกับปัญหาคณิตศาสตร์ ที่ยิ่งใหญ่ที่สุดปัญหาหนึ่งของยุคนี้ นั้นคือปัญหา P vs. NP หนึ่งในเจ็ดสุดยอดปัญหาคณิตศาสตร์แห่งสหัสวรรษ โดยสถาบันคณิตศาสตร์เคลย์ (Clay Mathematics Institute) ได้ตั้งรางวัลให้กับผู้ที่สามารถแก้ปัญหานี้เป็นเงินรางวัล 1 ล้านเหรียญฯสหรัฐ ปัญหานี้ สตีเฟน คุก ได้เสนอขึ้นไว้ตั้งแต่ ปี 1971 ตอนเขาอายุได้ 30 ปี
P vs. NP Problem
ปัญหาข้อนี้เป็นเรื่องของทฤษฏีปริมาณการคำนวณโดยให้ตัดสินว่า
P = NP หรือไม่
ในการแก้ไขปัญหาต่างๆ เราจะมีงานที่สามารถหาคำตอบได้โดยใช้เวลาไม่มาก เรียกว่า งานแบบ P หรือ Polynomial time หมายถึงเรามีวิธีการหาคำตอบได้แล้วอย่างมีประสิทธิภาพ ส่วน NP คือการที่เรามีเพียงวิธีการยืนยันคำตอบอย่างมีประสิทธิภาพ เพราะมันเป็นงานที่ยาก
ถ้านึกไม่ออกก็ลองตัวอย่างนี้ครับ
ถ้าเรามีปัญหาว่า 3329 คูณ 4547 ได้เท่าไร เราก็อาจจะเอาเลขมาคูณกันไปมาแล้วก็บวกกันซะเราก็จะได้ 15136963 เป็นคำตอบออกมา งานนี้เราถือเป็นงาน P เพราะมันเป็นงานง่ายๆ ต่อไปถ้าเกิดเราอยากรู้ว่าไอ้ 15136963 นั้นเกิดจากอะไรคูณกันบ้างเราก็อาจจะต้องนั้นไล่เอาเลขมาหารมันทีละตัวละตัว งานนี้เรียกว่าเป็นงานแบบ NP
โดยปกติแล้ว
แต่ปัญหานี้คือการตัดสินว่า
 |
| ตัวอย่างกรณี ต่างๆของปัญหานี้ |
ลองนึกภาพของคนคนหนึ่งที่เล่นเกม Minesweeper ด้วยคำใบ้เพียงเล็กน้อยแต่ก็สามารถบอกได้ว่า ตรงไหนเป็นที่ว่างและตรงไหนเป็นระเบิดโดยไม่ต้องเปิดเพิ่ม
ใครมีความสนใจอยากได้เงินล้านก็ลองศึกษาปัญหาต่อได้นะครับตามสบาย....แต่คนที่จะมอบรางวัลให้ยังอยู่ รึเปล่านี่ซิ ปัญหา
0 ความคิดเห็น:
แสดงความคิดเห็น