Wall of Text #7: ทหารล้อมเมือง

เวลาเครียดๆ ขอแนะนำให้อ่านปัญหา Computer Science แก้เครียด

ปัญหาวันนี้มีอยู่ว่า พม่ายกทัพมาปิดล้อมกรุงศรีไว้ แบ่งเป็นสองกองทัพอยู่คนละฝั่งของเมือง

ทีนี้แม่ทัพพม่าต้องการให้บุกเข้าตีเมืองพร้อมกันทั้งสองด้าน เพราะถ้าบุกอยู่ข้างเดียวกรุงศรีอาจจะตั้งรับได้ แล้วทั้งสองกองทัพจะนัดเวลาเข้าตีกันอย่างไรดี?

วิธีการง่ายๆ ก็คือแม่ทัพที่อยู่ฝั่งซ้ายให้ทหารขี่ม้าถือสาส์นไปหากองทัพฝั่งขวา บอกว่าเวลาสองยามคืนนี้ให้บุกเข้าตี

ปรากฏว่ามันไม่ได้ง่ายอย่างนั้น เพราะทหารขี่ม้าไปก็อาจจะถูกข้าศึกจับระหว่างทางก็เป็นได้ ฝั่งขวาก็จะไม่ได้รับสาส์น ฝั่งซ้ายก็บุกอยู่ฝั่งเดียว

เพื่อความชัวร์ เราก็อาจจะกำหนดว่าถ้าได้รับสาส์นแล้วให้ทหารขี่ม้ากลับมาบอกด้วยว่าได้รับแล้ว วิธีนี้กลับยิ่งสร้างปัญหาใหม่อีก นั่นคือถ้าทหารขี่ม้าขากลับถูกจับ กลายเป็นว่าฝั่งขวาบุกเข้าตีอยู่ฝั่งเดียวแทน

แล้วเราจะแก้ปัญหานี้ให้แม่ทัพอย่างไรดี?


ปัญหานี้ใน Computer Science เรียกว่า Two Generals’ Problem ซึ่งเมื่อเราพิสูจน์ออกมาแล้วก็จะพบว่าเป็นไปไม่ได้ที่ทั้งสองกองทัพจะตกลงกันได้ เพราะไม่ว่าส่งสาส์นไปเท่าไรก็มีโอกาสจะถูกจับทั้งสิ้น

วิธีหนึ่งที่เราจะพอจัดการกับปัญหานี้ได้คือออกแบบระบบโดยคำนึงถึงความไม่แน่นอนเอาไว้ด้วย เช่น ถ้าคิดว่าไม่มีทางที่ทหารจะถูกจับไม่เหลือรอดเลยสักคน เราก็อาจจะส่งทหารแยกกันไปหลายๆ คน (ยังไงก็น่าจะถึงผู้รับสักคน) แล้วไม่ว่าจะได้รับคำตอบหรือไม่ก็จะบุกตามเวลาที่นัดหมายไว้

อีกวิธีหนึ่งคือเพิ่มขั้นตอนการยึนยันเข้าไปอีก นั่นคือเมื่อฝั่งขวารับสาส์นแล้วให้ส่งทหารกลับไปฝั่งซ้ายยึนยันว่าได้รับแล้ว ฝั่งซ้ายก็จะต้องส่งสาส์นกลับไปอีกทีหนึ่งว่าได้รับคำยึนยันแล้ว แล้วก็อาจจะตกลงกันไว้ก่อน เช่น ยึนยันครบ 4 ครั้งจึงจะบุก

วิธีนี้ก็พอช่วยได้เช่นกัน แต่ก็ไม่ได้ถูกต้อง 100% เช่น ถ้าสาส์นยึนยันครั้งสุดท้ายหายไป ฝั่งหนึ่งจะยึนยันแค่ 3 ครั้ง แม่ทัพก็ต้องเสี่ยงดวงอยู่ดีว่าจะบุกหรือไม่


ปัญหาบุกล้อมเมืองนี้ยังไม่จบ เพราะเรายังมีภาคต่อ

ภาคนี้บอกว่า กองทัพเมือง Byzantine ยกกองทัพปิดล้อมเมืองข้าศึกไว้ แต่คราวนี้ยกมาถึง 9 กองทัพ นายพลของแต่ละกองทัพก็ได้ตั้งทัพไว้ตามที่ต่างๆ นอกเมือง

คำถามยังคล้ายเดิมคือ นายพล 9 คนนี้จะต้องตกลงกันว่าจะบุกเข้าตีหรือจะถอย

ข้อจำกัดคือตามเงื่อนไขเดิม การส่งสาส์นระหว่างกองทัพ ผู้นำสาส์นอาจถูกจับและทำให้ไม่ได้รับสาส์นก็ได้

แล้วปรากฏว่า นายพลทั้ง 9 คนนั้นกลับมีบางคนเป็นไส้ศึก ซึ่งเราก็ไม่อาจรู้ได้ว่าใครอยู่พวกใด คนที่เป็นไส้ศึกนั้นอาจจะลงคะแนนเสียงขัดแย้งกับความเป็นจริงก็ได้ เช่น ถ้าข้าศึกมีกำลังมากกว่า ไส้ศึกก็จะบอกให้บุกเข้าไปตายกันหมด

แล้วนายพลทั้ง 9 จะตกลงกันอย่างไรดี?


ปัญหานี้มีชื่อตามเนื้อเรื่องคือเรียกว่า Byzantine generals’ problem ซึ่งวิธีแก้ที่ง่ายที่สุดก็คือกำหนดให้ 1 คนเป็นหัวหน้าแล้วนายพลที่เหลือต้องทำตามคำสั่งของหัวหน้าเสมอ แต่ถ้าบังเอิญดันได้ไส้ศึกมาเป็นหัวหน้า กองทัพก็วินาศ

ถ้าเราอยากได้ระบบที่ไม่ต้องพึ่งผู้นำที่เชื่อถือได้ วิธีที่เหมาะสมก็คงเป็นประชาธิปไตย คือนายพลทุกคนส่งสาส์นหากันหมด เพื่อลงคะแนนเสียงของตัวเอง ถ้าหากไส้ศึกมีไม่ถึงครึ่งหนึ่งก็ยังสามารถเชื่อตามเสียงส่วนมากได้ กรณีที่ผู้นำสาส์นถูกจับ ก็กำหนดให้ถือว่าไม่ได้ลงคะแนน แล้วเตี๊ยมกันล่วงหน้าว่าเสียงส่วนใหญ่ไม่ได้ลงคะแนนจะบุกหรือจะถอย

ปัญหา Byzantine นี้เป็นปัญหาที่พบเจอได้ทั่วไป เช่นบนเครื่องบินมักจะมีระบบอ่านค่าหลายชุดเพื่อป้องกันกรณีอุปกรณ์ล้มเหลว ถ้าหากระบบควบคุมแต่ละระบบอ่านค่าได้ไม่ตรงกัน ก็จะต้องมีการกำหนดวิธีแก้ไขสถานการณ์

หรือ Bitcoin เองก็เป็นปัญหาแบบนี้เช่นกัน โดยเปรียบผู้ใช้แต่ละคนเป็นนายพล ซึ่งบางคนก็ตั้งใจจะโกงเงินที่มีในระบบ จึงต้องมีระบบการขุด Bitcoin ใครขุดได้ก่อนและเสียงส่วนมากของระบบยอมรับผลนั้น ผู้นั้นก็จะได้กำหนดการทำธุรกรรมบนระบบ