จำนวนแชนนอน

บทนำ

ในปี 1950 บทความของ CLAUDE E. SHANNON ที่ตีพิมพ์ใน นิตยสาร Philosophical เรื่อง Programming a Computer for Playing Chess เป็นบทความที่เขียนเกี่ยวกับวิธีการโปรแกรมคอมพิวเตอร์สำหรับการเล่นหมากรุก ท่านศึกษาความซับซ้อนของเกม โดยพยายามประมาณจำนวนรูปแบบการเล่นของเกมหมากรุกฝรั่งที่เป็นไปได้ทั้งหมด และมีผู้ตั้งชื่อจำนวนนี้ในภายหลังว่า "จำนวน แชนนอน" เพื่อเป็นเกียรติแก่ท่าน
แชนนอน ให้เหตุผลว่าหมากรุกเกมหนึ่ง ผู้เล่นแต่ละคนจะเล่นประมาณ 40 ตา โดยแต่ละตา ผู้เล่นมีทางเลือกประมาณ 30 ทาง (ที่จริงแล้ว สถานการณ์ในแต่ละตาจะมีทางเลือกที่แตกต่างกันตั้งแต่ 0 ทาง ถึง 218 ทาง) ดังนั้นค่าประมาณจำนวนการเล่นหมากรุกที่เป็นไปได้คือ (30 x 30)40 หรือประมาณ 10^123 การเล่นเลยทีเดียว ซึ่งถือเป็นจำนวนที่มากกว่าจำนวนอะตอมทั้งหมดในจักรวาลรวมกัน (ประมาณระหว่าง 4x 10^79 และ 10^81) เสียอีก
โดยแชนนอนได้เขียนไว้ว่า “ a machine operating at the rate of one variation per micro-second would require over 10^90 years to calculate the first move!”
จะขอนำเสนอรายละเอียดของบทความเรื่อง Programming a Computer for Playing Chess ที่เขียนโดย CLAUDE E. SHANNON อย่างคร่าวๆดังต่อไปนี้

ความต่างในวิธีและสไตล์การเล่น

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

กลยุทธ์อีกแบบหนึ่ง

กลยุทธ์ที่ได้กล่าวมาข้างต้นไม่ได้ทำให้ความเป็นไปได้ที่ว่ามีกลยุทธ์อื่นๆที่ใช้ได้ดีกว่าในการลดเวลาการคำนวณของคอมพิวเตอร์ลงหายไป แม้ว่าจะรวมการปรับปรุงที่ว่าไปแล้วแต่คอมพิวเตอร์ก็ยังใช้การคำนวณอย่างเดียวมากเกินกว่าที่จะใช้การคิดวิเคราะห์ตำแหน่งแบบสมเหตุสมผล เครื่องจะเล่นเหมือนผู้เล่นใหม่ที่มีพลังในการคำนวณสูง รู้หลักบางอย่างแต่ไม่มีประสบการณ์ในการเล่น เซียนหมากรุกนั้นจะมีความรู้ถึงสถานการณ์มาตรฐานเป็นร้อยหรือพันหลัก ความเป็นไปได้ที่จำเก็บไว้ และเหตุการณ์พลิกแพลงที่เกิดขึ้นซ้ำๆในเกม เช่นการสละม้าที่ F7 หรือขุนที่ h7 การรุกมาตรฐานเช่น "Philidor Legacy" ในตำแหน่งใดตำแหน่งหนึ่งเซียนหมากรุกจะจำความใกล้เคียงกับสถานะกรณีที่คุ้นเคยได้และจะทำให้มีโอกาสสำเร็จมากกว่านี่คือเหตุผลที่ว่าทำไมโปรแกรมที่ใช้ตำแหน่งตามรูปแบบถึงใช้ไม่ได้จริง แม้ว่าจะมีการเขียนวิธีการเล่นในช่วงกลางของเกมไว้มากแต่ก็เขียนไว้เพื่อให้มนุษย์เข้าใจไม่ใช่ไว้ให้คอมพิวเตอร์ที่ใช้การคำนวณเป็นหลัก เพราะเราสามารถยกตัวอย่างสองสามอย่างประกอบทฤษฎีเพื่อให้คนเข้าใจและนำไปดัดแปลงใช้ได้แต่ไม่สามารถทำได้กับคอมพิวเตอร์ แต่ถ้าหากทำได้ก็จะสามารถเพิ่มประสิทธิภาพให้กับโปรแกรมได้
สำหรับโปรแกรม กลยุทธ์อย่างนั้นจะต้องมีการวิเคราะห์ตำแหน่งนั้นๆรวมเข้าไปในฐานข้อมูล โดยที่ข้อมูลจะกล่าวไว้เช่น หากม้าสีดำที่ f6 ถูกตรึงโดยขุน เรือสีขาวที่ e1 จะไม่สามารถออกจากแถวหลัง ได้เนื่องจากจะเปิดช่องโหว่ให้รุกฆาตที่ c1 ทำให้ม้าสีขาวที่ a4 ไม่สามารถเดินหมากได้ กล่าวง่ายๆคือข้อมูลทั้งหมดที่ผู้เล่นสามารถวิเคราะห์กลยุทธ์ได้ ข้อมูลเหล่านี้จะต้องอยู่ในฐานข้อมูลของโปรแกรมและต้องถูกปรับปรุงอยู่ตลอดเวลาการเล่นเกม ข้อมูลเชิงวิเคราะห์นั้นจะถูกใช้เพื่อเรียกใช้โปรแกรมอื่นๆตามธรรมชาติของตำแหน่ง เช่นหมากที่โดนตึงควรถูกโจมตี หากเอาเรือกันแนวหลังไว้ก็จะไม่สามารถกันเบี้ยที่อยู่ด้านหน้าได้ เครื่องจะทำงานเช่นนี้ทำให้มีตำแหน่งที่เป็นไปได้ในการสำรวจมากขึ้น ไม่ใช่ว่าเราควรที่จะวางกลยุทธ์ของเราเอง แต่ควรที่จะเป็นการแข่งความสมดุลระหว่างความสามารถมากกว่า คอมพิวเตอร์นั้นแกร่งในด้านของความเร็ว ความแม่นยำแต่อ่อนในด้านของความสามารถในการวิเคราะห์และจดจำ