คอมพิวเตอร์สามารถเล่นเกมหมากฮอสได้อย่างไร้ที่ติ การคำนวณที่เริ่มขึ้นเมื่อเกือบ 2 ทศวรรษที่แล้วแสดงให้เห็นว่าหากผู้เล่นทั้งสองฝ่ายเคลื่อนไหวได้สมบูรณ์แบบ เกมจะเสมอกันทุกครั้ง ความสำเร็จนี้ทำให้หมากฮอสเป็นเกมที่ซับซ้อนที่สุดที่ได้รับการแก้ไขอย่างสมบูรณ์คอมพิวเตอร์สามารถเอาชนะผู้คนด้วยหมากฮอสได้ตั้งแต่ปี 1994 เมื่อรายการชื่อ Chinook ชนะการแข่งขันหมากฮอสชิงแชมป์โลก โปรแกรมนี้เขียนโดยนักวิทยาศาสตร์คอมพิวเตอร์ Jonathan Schaeffer จาก University of Alberta ใน Edmonton ใช้กฎทั่วไปในการเดาท่าที่ดีที่สุด ซึ่งเป็นวิธีการเลียนแบบวิธีการเล่นของผู้คน ตอนนี้ Schaeffer ได้ขจัดการคาดเดาด้วยโปรแกรมที่ตรวจสอบทุกตำแหน่งที่เป็นไปได้ที่อาจเกิดขึ้นบน
กระดานหมากรุกเพื่อค้นหาการเคลื่อนไหวที่ดีที่สุดทุกครั้ง
การคำนวณกำลังเดรัจฉานภายใต้โปรแกรมใหม่นั้นมีแนวคิดที่เรียบง่ายแต่มีความต้องการด้านลอจิสติกส์ เนื่องจากตัวตรวจสอบมีตำแหน่งที่เป็นไปได้ประมาณ 5 แสนล้านตำแหน่ง (5 x 10 20 ) ผู้เล่นแต่ละคนเริ่มต้นด้วย 12 ชิ้นบนกระดานหมากรุกขนาด 8 คูณ 8 และเขาหรือเธอย้ายชิ้นส่วนโดยเลื่อนไปข้างหน้าและทแยงมุมหนึ่งช่อง ชิ้นส่วนจับศัตรูโดยการกระโดดในแนวทแยงข้ามเข้าไปในช่องสี่เหลี่ยม ผู้เล่นคนสุดท้ายที่มีชิ้นส่วนบนกระดานเป็นผู้ชนะ
เริ่มต้นในปี 1989 Schaeffer ใช้คอมพิวเตอร์มากถึง 200 เครื่องพร้อมกันเพื่อขจัดปัญหา เขาเริ่มต้นด้วยการจบเกมโดยวางเพียงสองส่วนบนกระดานและคำนวณผลลัพธ์ที่เป็นไปได้ทั้งหมดสำหรับแต่ละตำแหน่งที่พวกเขาอาจคิด จากนั้นเขาก็ทำแบบเดียวกันสำหรับสามชิ้น สี่ชิ้น และต่อไปเรื่อยๆ จนถึง 10 ชิ้น ณ จุดนั้น มีความเป็นไปได้ถึง 39 ล้านล้านตำแหน่ง
แต่ละขั้นตอนในกระบวนการนี้ใช้เวลามากกว่าขั้นตอนก่อนหน้าถึง 10 เท่า ดังนั้นการดำเนินการด้วยวิธีนี้จึงไม่สามารถทำได้ แชฟเฟอร์หันไปที่จุดเริ่มต้นของเกมแทน โดยคำนวณตำแหน่งทั้งหมดที่อาจเป็นผลจากการเคลื่อนไหวหนึ่งครั้ง จากนั้นสองการเคลื่อนไหว
จากนั้นสามการเคลื่อนไหว และต่อไปเรื่อยๆ โปรแกรมดำเนินเกมต่อไปจนเหลือเพียง 10 ชิ้น
จากนั้นจึงตรวจสอบฐานข้อมูลของ endgames เพื่อหาผลลัพธ์ ในท้ายที่สุด การวิเคราะห์รวมตำแหน่งตัวตรวจสอบระหว่าง 100 ล้านล้านถึงสี่ล้านล้านตำแหน่ง Schaeffer และเพื่อนร่วม งานของเขารายงานผลลัพธ์ของพวกเขาในวารสารScience ฉบับวันที่ 14 กันยายน
“เรากำลังผลักดันขอบเขตของสิ่งที่คอมพิวเตอร์สามารถแก้ปัญหาได้” Schaeffer กล่าว “ถ้าเรารอสัก 10 หรือ 20 ปี เครื่องจักรจะเร็วขึ้น” ทำให้ปัญหาง่ายขึ้น เหมือนเดิม เขาและทีมของเขาต้องคิดค้นวิธีที่ชาญฉลาดในการจัดเก็บและค้นหาข้อมูล
ตั้งแต่ดาราศาสตร์ไปจนถึงสัตววิทยา
สมัครรับข้อมูลข่าววิทยาศาสตร์เพื่อสนองความกระหายใคร่รู้ของคุณสำหรับความรู้สากล
ติดตาม
ตัวอย่างเช่น พวกเขาจัดเก็บผลลัพธ์สำหรับตำแหน่งที่เป็นไปได้ 39 ล้านล้านตำแหน่งสำหรับ endgames ในพื้นที่เก็บข้อมูลคอมพิวเตอร์เพียง 237 กิกะไบต์ โดยเฉลี่ย 154 ตำแหน่งต่อไบต์ ขณะนี้นักคณิตศาสตร์กำลังใช้เทคนิคเหล่านี้กับชีวสารสนเทศ โดยมองหาวิธีจัดการข้อมูลจำนวนมหาศาลที่เกิดจากการจัดลำดับจีโนม
“มันเป็นงานจำนวนมหาศาล” เคน ทอมป์สัน แห่งเมาน์เทนวิว รัฐแคลิฟอร์เนีย ซึ่งตั้งอยู่ที่กูเกิล ซึ่งในปี 1983 ได้พัฒนาโปรแกรมคอมพิวเตอร์หมากรุกระดับมาสเตอร์โปรแกรมแรก Thompson กล่าวว่าการแก้หมากฮอสทำให้คอมพิวเตอร์เข้าใกล้ความสามารถในการแก้เกมที่ซับซ้อนมากขึ้น เช่น หมากรุกหรือโกะ อย่างไรก็ตาม เขาคาดการณ์ว่างานเหล่านั้นจะใช้เวลาอีก 100 ปีจึงจะสำเร็จ หมากรุกมีตำแหน่งประมาณ10-20เท่าของหมากฮอส Schaeffer กล่าว
แนะนำ : ข่าวดารา | กัญชา | เกมส์มือถือ | เกมส์ฟีฟาย | สัตว์เลี้ยง
