creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
คุณสมบัติของอัศวิน (Knight)

ผมเก็บมาเล่าจากบทความ The Mathematical Knight ของโปรเฟสเซอร์ n.d.e แห่ง harvard กับโปรเฟสเซอร์ r.p.s แห่ง mit พูดถึงการวิเคราะห์ endgame และคุณสมบัติพื้นฐาน (แต่มีความน่าสนใจอย่างยิ่งยวด) ของม้าหมากรุก หรืออัศวิน เริ่มจากรูปแบบดังรูป (สร้างโดย n.d.e)



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

ลองดูกรณีตัวอย่าง หากคิงขาวกินเบี้ย c2 อัศวินจะเดินไป d3 ดังรูป



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

1. Kc1 Nd3+
2. Kxc2 (ดูรูปที่ 2)
2. ... Nb4+
3. Kc1

ถึงทีที่ 3 นี้สภาพเป็นดังรูปที่ 3 ครับ



คงเห็นว่า ถ้าทีต่อไปขาวเป็นฝ่ายเดิน ย่อมแพ้ เพราะถูกบีบให้ออกจากสภาพที่กักคิงดำ แต่ทีต่อไปเป็นฝ่ายดำเดินย่อมเปิดโอกาสให้คิงขาวไปยัง c2 ถ้าคิงขาวสามารถเดินกลับไปกลับมาระหว่าง c1-c2 ได้โดยไม่ถูกรบกวนก็สามารถกักดำได้สำเร็จ และรูปเกมออกมาเสมอกัน คำถามคือ ม้าดำมีพื้นที่อีกมากมายทั้งกระดานให้หาเส้นทาง เป็นไปได้มั้ยที่มันจะเดินกลับมาบีบคิงขาว ตอนนี้จุดตั้งต้นของเราคือม้าอยู่ ณ b4 ส่วนคิงขาวอยู่ c1 (รูปที่ 3) ดำเดินก่อน มีขาวจะออสซิลเลตอยู่ระหว่าง c1 กับ c2 โดยอยู่จะอยู่ช่อง c1 เมื่อเดินทีที่เป็นจำนวนคู่ และอยู่ช่อง c2 เมื่อเดินทีที่เป็นจำนวนคี่ หากมีหนทางให้ม้าไปอยู่ยัง d3 ในทีที่เป็นจำนวนคู่ก็จะบีบคิงขาวได้ครับ ซึ่งตำแหน่ง d3 นี้สมมูลกันกับตำแหน่ง b3 และ e2 เพราะทั้ง 3 ช่องนี้กันคิงขาวไม่ให้เดินไปยัง c1 และแต่ละช่องเดินถึงกันได้ใน 2 หรือจำนวนคู่ที

เพื่อแก้ปัญหาดังกล่าวเราให้ม้าดำเดินไปยังตำแหน่งใด ๆ ใช้ m ที แล้วเดินกลับมายัง d3 ใช้ n ที ถ้า m+n เป็นจำนวนคู่ ดำชนะ เรามองกระดานหมากรุก 8 x 8 เป็นกราฟ G8,8 โดย vertices คือช่องทั้ง 64 ช่อง จึงมี 64 จุด และ edges คือเซ็ตของเส้นเชื่อมช่องหมากรุกในรูปแบบการเดินของม้า สามารถพิสูจน์ได้ไม่ยากว่า G8,8 เป็น connected graph เป็นกราฟที่จากจุดใด ๆ สามารถมีเส้นเชื่อมไปยังจุดอื่น ๆ ได้ทุกจุด และ G8,8 เป็น bipartite คือเซ็ตของจุดช่องดำ กับเซ็ตของจุดช่องขาว (Bipartite graph คือกราฟที่จุดสามารถแบ่งออกได้เป็น 2 กลุ่มที่ไม่มีสมาชิกร่วมกัน และทุก edge เชื่อมระหว่างจุดที่มาจากคนละกลุ่มกัน) พิสูจน์ได้จากเงื่อนไขของ edge ที่บอกว่าเป็นเส้นเชื่อมช่องทางเดินของม้า ทุกครั้งที่ม้าเดินจะเปลี่ยนสีช่องที่มันยืน เมื่อ G8,8 เป็น bipartite การเดินเป็นวงกลับมาสู่สีเดิมของมันจึงไม่มีวงเลขคี่ หรือการเดินไปสู่จุดที่อยู่คนละกลุ่มกัน (คนละช่องสี) ไม่มีวงที่เป็นเลขคู่ ดังนั้น m+n เป็นจำนวนคี่เสมอครับ นั่นหมายความว่าเกมนี้ม้าไม่สามารถบีบบังคับคิงจากการเดินกลับไปกลับมาระหว่าง c1 กับ c2 ได้ เสมอกันครับ






Create Date : 12 พฤษภาคม 2551
Last Update : 12 พฤษภาคม 2551 14:13:23 น. 1 comments
Counter : 1325 Pageviews.

 
คุณศลยังจำDiscreteได้แม่นจิงๆ ผมเพิ่งเรียนไปปีเดียว ลืมสนิท


โดย: roninkung (Roninkung ) วันที่: 23 กรกฎาคม 2551 เวลา:14:10:15 น.  

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.