จำนวนแชนนอน

จำนวนแชนนอน (อังกฤษ: Shannon Number) ตั้งชื่อตามนักคณิตศาสตร์ชาวอเมริกัน คล็อด แชนนอน ว่าด้วยเรื่องการเชื่อมโยงลึกที่สุดของ เกมทรีคอมเพลกซิตี ในเกมหมากรุกสากล ที่มีจำนวน 10¹²⁰ โดยอยู่บนฐานของค่าเฉลี่ยจำนวนช่องที่เลื่อนได้ที่ 10³ อันเริ่มด้วยสีขาวเลื่อนตามด้วยสีดำ และเกมส่วนใหญ่จะจบในการเลื่อน 40 ตา

คล็อด แชนนอน

บทนำ

ในปี ค.ศ. 1950 บทความของคล็อด แชนนอน ที่ตีพิมพ์ใน นิตยสาร ฟิโลโซฟิคอล เรื่อง "Programming a Computer for Playing Chess" (การสั่งการคอมพิวเตอร์ให้เล่นหมากรุก) เป็นบทความที่เขียนเกี่ยวกับวิธีการโปรแกรมคอมพิวเตอร์สำหรับการเล่นหมากรุก เขาศึกษาความซับซ้อนของเกม โดยพยายามประมาณจำนวนรูปแบบการเล่นของเกมหมากรุกสากลที่เป็นไปได้ทั้งหมด และมีผู้ตั้งชื่อจำนวนนี้ในภายหลังว่า "จำนวนแชนนอน" เพื่อเป็นเกียรติแก่ท่าน

แชนนอน ให้เหตุผลว่าหมากรุกเกมหนึ่ง ผู้เล่นแต่ละคนจะเล่นประมาณ 40 ตา โดยแต่ละตา ผู้เล่นมีทางเลือกประมาณ 30 ทาง (ที่จริงแล้ว สถานการณ์ในแต่ละตาจะมีทางเลือกที่แตกต่างกันตั้งแต่ 0 ทาง ถึง 218 ทาง) ดังนั้นค่าประมาณจำนวนการเล่นหมากรุกที่เป็นไปได้คือ (30 x 30)40 หรือประมาณ 10¹²³ การเล่นเลยทีเดียว ซึ่งถือเป็นจำนวนที่มากกว่าจำนวนอะตอมทั้งหมดในจักรวาลรวมกัน (ประมาณระหว่าง 4x 10⁷⁹ และ 10⁸¹) เสียอีก

โดยแชนนอนได้เขียนไว้ว่า “ a machine operating at the rate of one variation per micro-second would require over 10⁹⁰ years to calculate the first move!”

จะขอนำเสนอรายละเอียดของบทความเรื่อง Programming a Computer for Playing Chess ที่เขียนโดย คล็อด แชนนอนอย่างคร่าว ๆ ดังต่อไปนี้

ข้อคิดเบื้องต้น

ตำแหน่งของตัวหมากนั้นสามารถแปลให้ตรงกับข้อมูลเบื้องล่างได้ดังนี้

(1) คำแถลงเรื่องตำแหน่งของตัวหมากทั้งหมดบนกระดาน

(2) คำแถลงเรื่องฝ่ายไหนเป็นฝ่ายได้เดินหมาก สีขาวหรือดำ

(3) คำแถลงว่าขุนหรือเรือได้เดินแล้ว นี่สำคัญเนื่องจากการเดินตัวเรือจะทำให้หมดสิทธิในการมีปราการในด้านนั้นจะหมดไป

(4) คำแถลงเรื่องการเดินในตาสุดท้าย นี่จะทำให้รู้ว่าจะสามารถทำการกินหมากแบบกินผ่าน (en passant) ได้หรือไม่ เนื่องจากสิทธินี้จะถูกระงับหลังจากหนึ่งตา

(5) คำแถลงเรื่องจำนวนตาที่เดินหลังจากที่มีการเคลื่อนเบี้ยตัวสุดท้ายหรือเบี้ยตัวสุดท้ายถูกกิน

นี่สำคัญเนื่องจากกฎการเสมอเมื่อเดิน 50 ตา เพื่อความง่ายต่อการเข้าใจเราจะละเว้นกฎเรื่องการเดินหมากซ้ำสามครั้งสำหรับหนึ่งตำแหน่ง

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

(1) ตำแหน่งที่ชนะสำหรับสีขาว นั้นคือสีขาวสามารถบังคับชนะได้ไม่ว่าสีดำจะป้องกันอย่างไร

(2) ตำแหน่งเสมอ สีขาวสามารถบังคับให้ผลออกมาเสมอได้ไม่ว่าสีดำจะเล่นอย่างไร และสีดำก็สามารถบังคับเสมอได้ไม่ว่าสีขาวจะเล่นอย่างไร หากทั้งสองฝ่ายเล่นเกมอย่างถูกต้อง ผลจะออกมาเสมอกัน

(3) ตำแหน่งที่ชนะสำหรับสีดำ นั้นคือสีดำสามารถบังคับชนะได้ไม่ว่าสีขาวจะป้องกันอย่างไร

และนี่เป็นทฤษฎีการมีอยู่เพื่อใช้สำหรับกรณีทั่วไป ไม่มีหลักการใดที่จะทำให้รู้ว่าตำแหน่งๆหนึ่งควรอยู่ในหมวดไหน ถ้าเป็นหมากรุกจะทำให้เสียความน่าสนใจของเกมไป เราสามารถกำหนดได้ว่าตำแหน่งแรกจะเป็นตำแหน่งที่ชนะ เสมอ หรือแพ้สำหรับสีขาว หรือผลของเกมระหว่างคู่ต่อสู้จะออกมาอย่างไรนั้นมาจากการรู้ทฤษฎีในการเลือกตำแหน่งแรก เช่นตำแหน่งแรกเป็นตำแหน่งเสมอ ทุกเกมจะจบลงด้วยการเสมอ เป็นสิ่งที่น่าสนใจว่าการเปลี่ยนแปลงกฎของหมากรุกไปนิดหน่อยสามารถทำให้สีขาวสามารถชนะหรือเสมอได้ในตำแหน่งแรก ในบางเกมมีฟังชั่นการประเมินผล F(P) ที่สามารถใช้กับตำแหน่ง P ได้และสามารถรู้ได้ว่าผลจะออกมาเป็นชนะ แพ้หรือเสมอ ในเกมของนิม (ฮาร์ดีและไรต์ 1938) ตำแหน่งสามารถรู้ได้จากการเขียนจำนวนไม้ขีดตามแบบสัญกรณ์ฐานสอง ตัวเลขเหล่านี้สามารถเรียงเป็นแถวแนวตั้ง หากจำนวนเลขหนึ่งในแถวเป็นเลขคู่ผลจะเป็นการแพ้สำหรับผู้เล่นที่กำลังจะเดินหมาก หากไม่ใช่ผลคือชนะ หากสามารถหาการประเมินโดยใช้ฟังชั่นการประเมินผลได้ก็จะสามารถเขียนเครื่องที่สามารถเล่นเกมที่ไม่มีจุดบอดได้ เครื่องจะไม่มีการแพ้หรือเสมอในตำแหน่งที่ชนะ และไม่มีทางแพ้หรือเสมอในตำแหน่งที่เสมอหรือเวลาที่คู่แข่งเดินหมากพลาดไป ยกตัวอย่างเช่น

F (P) =+1 คือตำแหน่งชนะ

F (P) = 0 คือตำแหน่งเสมอ

F (P) =-1 คือตำแหน่งแพ้

ในตาของเครื่อง เครื่องจะเป็นผู้คำนวณ F(P) สำหรับตำแหน่งต่างๆที่ได้มาจากตำแหน่งปัจจุบันเพื่อหาตำแหน่งที่สามารถเคลื่อนไปได้ เครื่องจะเลือกตำแหน่งการเดินหมากที่ให้ค่า F สูงที่สุด ในกรณีของนิมที่รู้ฟังก์ชันนั้น เครื่องสามารถเล่นเกมที่ไม่มีจุดบอดได้ ในเชิงทฤษฎีแล้ว ในหมากรุกเราสามารถที่จะเล่นเกมที่ไม่มีจุดบอดได้หรือสั่งให้เครื่องทำดังต่อไปนี้คือ การหาตำแหน่งที่เป็นไปได้ทั้งหมดและหาตำแหน่งที่เป็นไปได้ทั้งหมดของคู่แข่งจนถึงสิ้นสุดเกม เกมต้องจบหลังจากที่เดินหมากไปแล้วกี่ครั้งเท่านั้น (กฎการเดินหมาก 50 ครั้ง) แต่ละความเป็นไปได้จะจบลงด้วยการชนะ แพ้หรือเสมอ การคำนวณย้อนหลังจะทำให้สามารถรู้ได้ว่าจะสามารถบังคับชนะ แพ้หรือเสมอในตำแหน่งนั้นๆ แต่ก็สามารถแสดงได้อย่างง่ายดาย แม้ว่าจะมีความเร็วในการประมวลผลสูง การคำนวณทางคอมพิวเตอร์ก็ทำไม่ได้จริง
ในการเล่นหมากรุกทั่วไปจะมีกฎการเดินหมาก 30 ตา ตัวเลขนี้คงที่จนกว่าจะเกมใกล้จะจบ กราฟที่สร้างจากข้อมูลที่ได้จากเดอ กรูต (De Groot) ที่ประมาณจำนวนการเดินหมากที่ถูกต้องตามกฎในการเล่นหมากรุกแบบมืออาชีพ อธิบายว่าการเดินหมากของสีขาวและตามด้วยสีดำหนึ่งครั้งจะมีความเป็นไปได้ทั้งหมด 103 ครั้ง เครื่องที่ทำงานด้วยอัตราหนึ่งความเป็นไปได้ต่อหนึ่งเสี้ยววินาทีจะต้องใช้เวลา 109 ปีในการคำนวณเพียงแค่ตำแหน่งแรก หรืออีกหนึ่งวิธีการที่เป็นไปไม่ได้เช่นกันคือการเขียนความเป็นได้ทั้งหมดของตัวหมากแต่ละตัวออกมาและบอกตำแหน่งที่ถูกต้องโดยใช้การคำนวณอย่างกล่าวไปหรือการให้ตำแหน่งจากผู้คุมเกม ในตาของเครื่อง เครื่องจะเพียงหาตำแหน่งการเดินที่ถูกต้องและเดินหมากตามนั้น โดยความเป็นไปได้ที่มีคือ 64! / 32! (8!)2(2!)6 หรือ 1043 ซึ่งทำให้ไม่สามารถใช้ทฤษฎีนี้ได้ เห็นได้ชัดว่าปัญหาไม่ได้อยู่ที่การออกแบบเครื่องที่จะเล่นเกมหมากรุกที่ไม่มีจุดบอดได้หรือเครื่องที่เล่นหมากรุกที่ถูกต้องได้เท่านั้น เราต้องการเครื่องที่สามารถเล่นเกมอย่างมีประสิทธิภาพอย่างที่ผู้เล่นที่เป็นคนสามารถทำได้ แนวทางการเล่นคือขั้นตอนการเลือกตำแหน่งการเดินหมากในจุดใดก็ตาม หากขั้นตอนนั้นสามารถเลือกการเดินหมากแบบเดิมในตำแหน่งเดิมได้ทุกครั้งเราจะเรียกว่าเป็นแนวทางที่บริสุทธิ์ หากแนวทางรวมไปถึงขั้นตอนทางสถิติและไม่ได้เลือกการเดินหมากแบบเดิมทุกครั้งเราจะเรียกว่าแนวทางผสม ต่อไปเป็นตัวอย่างของแนวทางง่ายๆ

1. จำนวนการเดินหมากที่เป็นไปได้ในตำแหน่ง P ตามขั้นตอนมาตรฐาน เลือกตัวแรกของรายการ นี่คือแนวทางแบบบริสุทธิ์

2. จำนวนการเดินหมากที่ถูกต้องและเลือกมาหนึ่งแบบอย่างสุ่ม นี่คือแนวทางแบบผสม

ทั้งสองแนวทางนั้นเป็นแนวทางที่ไม่ได้ผล เพราะไม่มีความพยายามในการเลือกการเดินหมากที่ดี ปัญหาของเราคือการหาแนวทางที่ดีเพื่อเลือกตำแหน่งการเดินหมาก

ฟังก์ชันการประเมินผลโดยประมาณ

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

(1) จำนวนโดยคร่าวของควีน เรือ ขุน ม้า เบี้ย คือ 9, 5, 3, 2, 1 ตามลำดับ ดังนั้นเมื่ออย่างอื่นเท่าเดิม หากเราเพิ่มจำนวนตัวหมากตามเลขเหล่านี้ ด้านที่มีจำนวนเยอะกว่าจะอยู่ในตำแหน่งที่ดีกว่า

(2) เรือควรถูกวางในที่ที่ไม่ตัน เพื่อความสามารถในการเคลื่อนไหวที่มากกว่าและจะมีเกมที่ดีกว่า

(3) เบี้ยที่ถอยหลัง อยู่แยกออกมาตัวเดียว หรืออยู่เป็นคู่คือเบี้ยที่อ่อนแอ

(4) โคนที่มีช่องเปิดคือจุดอ่อนแอ จนกว่าจะถึงตอนจบของเกม

แนวทางเหล่านี้ได้มาจากประสบการณ์และเกมที่ผ่านการสำรวจเท่านั้น และทุกทฤษฎีของหมากรุกสามารถถูกขัดแย้งได้จากตัวอย่างที่เจาะจงแบบใดแบบหนึ่ง แต่จากทฤษฎีเหล่านี้เราจะสามารถสร้างฟังก์ชันการประเมินผลได้ เช่น

$(P)=200(K-K')+9(Q-Q')+5(R-R')+3(B-B'+N-N')+(P-P')-0.5(D-D'+S-S'+I-I')+0.1(M-M')+...$

โดยที่

(1) K,Q,R,B,B,P คือ จำนวนของโคน เม็ด เรือ ขุน ม้า เบี้ย สีขาวบนกระดาน

(2) D,S,I คือเบี้ยที่ถอยหลัง อยู่แยกออกมาตัวเดียว หรืออยู่เป็นคู่

(3) M คือความสามารถในการเคลื่อนตัวของสีขาวหรือจำนวนการเคลื่อนหมากที่ถูกต้อง โดยค่าของสีดำเช่นเดียวกับสีขาว

ค่า 0.5 และ0.1 เป็นเพียงการประมาณของผู้เขียน นอกจากนี้ยังควรมีค่าอีกมากมายที่ต้องรวมเข้าไป

กลยุทธ์ตามฟังก์ชันการประเมินผล

จุดที่สำคัญมากจุดหนึ่งเกี่ยวกับฟังก์ชันการประเมินผลและทฤษฎีการเล่นหมากรุกที่ได้กล่าวไว้ข้างต้นคือจะสามารถใช้ได้กับตำแหน่งที่สงบ ยกตัวอย่างเช่นในการแลกเปลี่ยนเม็ด สีขาวกล่าวว่า เม็ดแลกเม็ด และสีดำจะโต้ตอบทันทีโดยในขณะที่สีขาวกำลังมีเม็ดนำหน้าอยู่สีดำก็จะแก้ไขโดยทันที และไม่มีความหมายในการหาฟังชั่นการประเมินผลในการแลกเปลี่ยนตัวหมาก ความหมายอื่นๆอาจถูกเพิ่มเข้าไปในF(P) เพื่อการแลกเปลี่ยนตัวหมากโดยการสำรวจค่า นี่เป็นวิธีที่ผู้เล่นหมากรุกใช้คำนวณ ความเป็นไปได้หลายอย่างจะถูกคิดไปเรื่อยๆจนกว่าจะหาตำแหน่งที่สงบได้ และจะมีการประเมินเพื่อสรุปผล ผู้เล่นเลือกความเป็นไปได้ที่มีค่ามากที่สุดและตำแหน่งที่คาดว่าคู่แข่งจะเสียเปรียบ ขั้นตอนนี้สามารถถูกกล่าวในเชิงคณิตศาสตร์ได้ เราทิ้งความจริงที่ว่าF(P) ควรใช้กับตำแหน่งที่สงบเท่านั้น ในการหากลยุทธ์จากF(P) เราใช้ค่า M1, M2, M3, ..., Ms เป็นความเป็นไปได้ของการเคลื่อนหมากจากจุด P และให้ M1P, M2P เป็นตำแหน่งสิ้นสุดจากการเคลื่อนเมื่อใช้ M1, M2 กับตำแหน่ง P หลังจากนั้นจึงเลือกค่า Mmหรือค่าที่มากที่สุดของ (MmP). กลยุทธ์ที่เหนือกว่านั้นจะคำนวณถึงการตอบสนองของคู่ต่อสู่ด้วย โดยให้ Mi1, Mi2, ..., Mis เป็นการโต้ตอบที่เป็นไปได้จากสีดำ หากสีขาวเลือกที่จะเล่น Mi สีดำก็จะเล่นเพื่อตอบสนองให้ค่าของตนมากที่สุด ดังนั้นหากสีขาวเล่น Mi สีดำก็ควรจะเล่น Mij เพื่อที่จะได้ค่า f(Mij MiP) ที่เป็นค่าน้อยที่สุด สีขาวควรจะเล่นตำแหน่งแรกที่มีค่า f มากที่สุดหลังจากที่สีดำโต้ตอบอย่างดีที่สุด ดังนั้นสีขาวจึงควรเล่นที่ค่ามากที่สุดของ Mi

min f(Mij MiP)

Mij

ในทางเดียวกัน กลยุทธ์แบบการเดินหมากสองตาสามารถแสดงได้โดย

max min max min f(Mijkl Mijk Mij MiP)

Mi Mij Mijk Mijkl

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

การปรับปรุงกลยุทธ์

ข้อเสียก็คือเครื่องที่ทำงานโดยใช้กลยุทธ์แบบที่กล่าวมา จะเป็นผู้เล่นที่ช้าและไม่เก่ง มันจะช้าเนื่องจากแต่ละการเดินหมากจะต้องถูกคำนวณในเวลาเสี้ยววินาที และมีการคำนวณทั้งหมด 109 ครั้งสำหรับการเดินหมากสามตาต่อหนึ่งฝั่ง ดังนั้นจะต้องใช้เวลาทั้งหมดกว่า16นาทีเพื่อเดินหมากหนึ่งตา หรือ10ชมในการเล่นเกมที่มีการเดินหมาก40ครั้ง เครื่องยังทำงานแบบที่ไม่มีประสิทธิภาพเนื่องจากจะคำนวณค่าสามตาแล้วหยุดไม่ว่าจะอยู่ในตำแหน่งอะไรก็ตาม ผู้เล่นที่เป็นคนที่เก่งจะดูแค่เพียงความเป็นไปได้ไม่กี่จุดที่เลือกมาและจะทำตามโดยหยุดแค่เพียงในจุดที่สมควร
คำกล่าวของ Reuben Fine (Fine 1942) ผู้เล่นหมากรุกชาวอเมริกันที่เก่งกาจนั้นน่าสนใจมาก เขากล่าวว่า "บ่อยครั้งที่ผู้คนจะมีความคิดว่าผู้เชี่ยวชาญนั้นเห็นทุกอย่างหรือเกือบทุกอย่าง เช่นเมื่อเล่น h3 ที่การเดินที่ 13 จะเห็นล่วงหน้าว่าต้องเหลือช่องโหว่ให้โคนที่ 20 ตาต่อมา หรือเมื่อเล่นที่ 1. E4 พวกเขาจะทำโดยมีความคิดที่ว่าจะกัน Nd5 ในการเดินตาที่12 ของสีดำ หรือทุกอย่างถูกคำนวณทางคณิตศาสตร์หมด แน่นอนว่าทั้งหมดนี้เป็นเพียงเรื่องหลอก วิธีที่ดีที่สุดคือการเห็นผลกระทบใหญ่ๆในตาสองตาล่วงหน้าแต่พยายามหาความเป็นไปได้ระหว่างที่เล่นไป” การเลือกโดยเซียนหมากรุกนั้นถูกศึกษาโดย De Groot (1946, b) เขาแสดงความเป็นไปได้หลายแบบสำหรับตำแหน่งให้เซียนหมากรุกดูและขอให้พวกเขาเลือกการเดินหมากที่ดีที่สุดและพูดการวิเคราะห์ที่คิดไว้ออกมา การทำแบบนี้สามารถทำให้รู้ความลึกของการคิดวิเคราะห์ได้ จากสิ่งเหล่านี้การจะพัฒนาความเร็วและความเก่งในการเล่นเครื่องจะต้อง

(1) หาความเป็นไปได้ให้ไกลที่สุดแต่วิเคราะห์เฉพาะตำแหน่งที่สมควร

(2) เลือกความเป็นไปได้ที่จะสำรวจโดยวิธีการบางอย่างที่จะไม่ต้องเสียเวลาคำนวณทั้งหมด

โดยเริ่มจากการให้นิยามฟังชั่น g(P) สำหรับตำแหน่งที่จะหาว่าไม่มีตัวหมากอยู่ มีรายละเอียดโดยคร่าวๆ ดังนี้

g(P) = 1 หากหมากบางตัวโดยโจมตีโดยหมากที่มีค่าน้อยกว่าหรือฝ่ายตรงข้ามมีหมากมากกว่าหรือมีการเตรียกรุก

g(P) = 0 นอกเหนือจากกรณี g(p) = 1

การใช้ฟังก์ชันนี้จะทำให้สามารถสำรวจความเป็นไปได้เรื่อยๆจน g(P)=0 โดยไปอย่างต่ำครั้งละ 2 ตาการเดินหมากและไม่เกิน 10 ตา การปรับปรุงอย่างที่สองต้องการฟังก์ชัน H(P, M) เพื่อหาว่าการเดินหมาก M ในตำแหน่ง P นั้นควรแก่การสำรวจหรือไม่ นี่สำคัญมากเนื่องจากการประเมินนี้ไม่ควรตัดการเดินหมากที่ดูแย่ในตอนแรกเช่น การสละหมาก การรุกฆาตคือการเดินหมากแบบรุนแรง การโต้ตอบของฝ่ายตรงข้ามจะถูกจำกัดโดยไม่สามารถจะโต้ตอบโดยการโจมตีกลับได้ นี่หมายถึงการคำนวณความเป็นไปได้ในการรุกฆาตจะทำได้ดีกว่าอย่างอื่นเนื่องจากมีจำนวนการโต้ตอบที่จำกัดและควรต้องถูกคำนวณไม่ว่าการเดินนั้นจะดูแย่ในตอนต้นหรือไม่ ดังนั้น h(P,M) ควรได้รับค่ามากสำหรับการเดินหมากที่รุนแรงและการเดินหมากเพื่อพัฒนา ค่าปานกลางสำหรับการเดินหมากเพื่อตั้งรับและค่าน้อยสำหรับการเดินหมากอื่นๆ ในการหาความเป็นไปได้ h(P,M) จะถูกคำนวณเนื่องจากเครื่องจะคำนวณและเลือกความเป็นไปได้บางส่วนเท่านั้น เมื่อไปเรื่อยๆในความเป็นไปได้ความต้องการของ h จะมากขึ้นเพื่อให้เหลือตัวเลือกน้อยลงเรื่อยๆ ดังนั้นจะเป็นการเริ่มคำนวณการเดินหมากแรกด้วยตัวเองสำหรับการเดินหมากแบบรุกฆาต การทำเช่นนี้จะเพิ่มประสิทธิภาพของเครื่อง เราเชื่อว่าคอมพิวเตอร์ที่รวมเอาการปรับปรุงเหล่านี้เข้าไปจะเล่นเกมที่ดีและเร็วพอประมาณที่เทียบกับความเร็วของมนุษย์ได้

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

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

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

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

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

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

ภาคผนวก:ฟังก์ชันการประเมินผลของหมากรุก

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

(1) ความได้เปรียบทางจำนวนหมาก

(2) ตำแหน่งของเบี้ย

(a) ถอยหลัง อยู่แยกออกมา หรือเบี้ยคู่

(b) ควบคุมจุดกลางอยู่ (เบี้ยที่ e4, d4, c4)

(c) ความอ่อนแอของเบี้ยที่อยู่ใกล้โคน เช่น เบี้ยเดินหน้าที่ g

(d) เบี้ยที่อยู่ในช่องสีตรงข้ามกับขุน

(e) เบี้ยที่ถูกกินแล้ว

(3) ตำแหน่งของตัวหมาก

(a) บิชอปที่อยู่ด้านหน้า (ที่ e5, d5, c5, f5, e6, d6, c6, f6) โดยเฉพาะหากโดนปกป้องโดยเบี้ยและไม่ต้องกังวลการโดนโจมตี โดยเบี้ย

(b) เรือที่มีช่องโหว่เปิดกว้างหรือกึ่งกว้าง

(c) เรือที่อยู่ที่เจ็ด

(d) เรือคู่

(4) ตัวเลือกในการโจมตี

(a) หมากที่มีหน้าที่ในการป้องกันมีความรับผิดชอบและมีความเป็นไปได้ในการเคลื่อนไหวต่ำ

(b) การโจมตีหมากที่ทำให้ผู้เล่นได้แลกเปลี่ยนหมาก

(c) การโจมตีช่องที่ติดกับโคน

(d) การถูกตรึง เราหมายถึงการไม่สามารถเดินหมากได้ซึ่งค่าของตัวหมากที่ถูกตรึงไม่ได้มากกว่าหมากที่ตรึงอยู่ เช่นม้าถูกตรึง โดยขุน

(5) ความสามารถในการเคลื่อนไหว

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

อ้างอิง

CLAUDE E. SHANNON, March 1950, XXII. Programming a Computer for Playing Chess, Philosophical Magazine