← งานวิจัย COINล้างคิวEnglish
COINCIDENCE Algorithm · Live experiment

Knight’s Tour
Learning Lab

สังเกต Edge COIN เรียนรู้ความสัมพันธ์ของการเดินระหว่างช่องบนกระดานหมากรุก ระบบใช้ NumPy/Numba engine ที่ผ่าน parity tests และส่งเฉพาะผลสรุปที่จำเป็นมายังเบราว์เซอร์

63เยี่ยมครบ 64 ช่อง · open tour สมบูรณ์64เดินกลับจุดเริ่มได้อีกหนึ่งครั้ง · closed tour
สถานะ
ready
รุ่นที่0
คะแนนดีที่สุด
เวลาที่ใช้0.00s

เส้นทางที่ดีที่สุด

ความก้าวหน้าการเรียนรู้

BestAverage

เมทริกซ์ Edge coincidence ล่าสุด

บริบทงานวิจัย · การทบทวนวรรณกรรม

COIN อยู่ตรงไหนในงานค้นหา Knight’s Tour

Knight’s Tour มีทั้งวิธีสร้างคำตอบโดยตรง ฮิวริสติก backtracking วิวัฒนาการ neural network และ ant colony แต่เวลาที่รายงานนำมาเทียบตรง ๆ ไม่ได้ทั้งหมด เพราะบางวิธีใช้ความรู้เฉพาะหมากรุกเพื่อสร้างหนึ่งคำตอบ ขณะที่บางวิธีเรียนรู้จากประชากรหรือมุ่งสร้างคำตอบที่หลากหลาย

สร้างคำตอบโดยตรง

Warnsdorff & Parberry

Warnsdorff เลือกทางเดินที่ถูกกติกาและเหลือทางไปต่อน้อยที่สุด ส่วน Parberry เสนอวิธี divide-and-conquer เวลา O(n²) สำหรับ closed tour ทั้งสองแนวทางเร็วมาก แต่ตอบคนละคำถามกับเรา เพราะฝังโครงสร้างเฉพาะของ Knight’s Tour ไว้ในตัวสร้างคำตอบ ไม่ได้ให้ตัวเรียนรู้ permutation อเนกประสงค์ค้นพบโครงสร้างเอง

Parberry, 1997 ↗
การค้นหาเชิงวิวัฒนาการ

GA + repair

Gordon และ Slocum ประเมินสายคำตอบที่ผ่าน repair 1,000,000 ตัว ตลอด 20,000 generations ต่อรอบ GA พบคำตอบใน 94% ของรอบและพบคำตอบไม่ซ้ำเฉลี่ย 89 เส้น โดย repair เป็นองค์ประกอบสำคัญ เพราะ GA ที่ไม่มี repair ไม่พบ complete tour ในการทดลองนั้น ส่วน COIN ไม่ใช้ทั้ง repair และ local search

Gordon & Slocum, 2004 ↗
การเรียนรู้แบบฝูง

Ant Colony Optimization

Hingston และ Kendall รายงานคำตอบไม่ซ้ำเฉลี่ย 488,245 เส้น ซึ่งเป็น closed tour 9,192 เส้น จาก 100,000 cycles ที่มี 64 ants จึงเป็น baseline ที่แข็งแรงมากสำหรับ solution bank อย่างไรก็ตาม ant แต่ละตัวเลือกได้เฉพาะปลายทางที่ถูกกติกาและยังไม่เคยเยี่ยม ขณะที่ COIN สุ่ม complete permutation ก่อน แล้วรับรู้กติกาผ่าน fitness เท่านั้น

Hingston & Kendall, 2004 ↗
โมเดลแบบขนาน

Neural computation

Takefuji และ Lee สร้างแบบจำลอง neural network แบบขนานสำหรับ closed tour งานนี้สำคัญในเชิงประวัติศาสตร์ แต่ neural dynamics สมมติฐานด้านฮาร์ดแวร์ และการวัดการหยุด ไม่เท่ากับ population evaluations ของ COIN จึงไม่ควรเทียบเวลาโดยตรงหากยังไม่ได้รันบน implementation และเครื่องเดียวกัน

Takefuji & Lee, 1992 ↗
สิ่งที่แตกต่างของงานนี้

ตัวเรียนรู้ที่นำกลับไปใช้ได้—not a repaired or hand-guided generator

ใน configuration ที่เราทดลอง (population 400) COIN มี observed success rate 100% พบ complete tour แรกก่อน generation 300 ทุกครั้ง และค่าต่ำสุดที่สังเกตได้คือ generation 102 หรือประมาณ 40,800 ถึงน้อยกว่า 120,000 candidate evaluations ระบบยังพบ closed tour และเมื่อเดินต่อจนครบ 1,000 generations จะเพิ่มคำตอบไม่ซ้ำหลายรายการลงใน solution bank แบบถาวร

  • ไม่ใช้ repair operator, backtracking, local search หรือ Warnsdorff guidance
  • permutation encoding รับประกันว่าไม่ใช้ช่องซ้ำ แต่ความถูกต้องของ knight move ยังเป็นสัญญาณที่โมเดลต้องเรียนรู้
  • COIN library เดียวกันขยายไปยัง TSP, Flow Shop, Sudoku, RNA และ Linear Ordering ได้

ขอบเขตการกล่าวอ้าง: ตัวเลขข้างต้นเป็นผลที่สังเกตจากการทดลองปัจจุบัน ไม่ใช่การประกาศว่า COIN เป็น Knight’s Tour algorithm ที่เร็วที่สุดในทุกเงื่อนไข การเปรียบเทียบขั้นยืนยันต้องใช้ฮาร์ดแวร์ seed กติกาการหยุด นิยาม open/closed และ evaluation budget เดียวกัน

COIN Infinite Knight’s Tour บนกระดานหมากรุกสามมิติที่หมุนชมได้
จากงานวิจัยสู่ศิลปะการคำนวณ

เมื่อเส้นทางที่เรียนรู้ได้กลายเป็นการแสดงที่ไม่รู้จบ

ทุกคำตอบใน solution bank สามารถออกจากห้องทดลองไปเป็นการเคลื่อนไหว แสง สี มุมกล้อง และเสียง COIN Art อ่านคำตอบที่บันทึกไว้แล้วนำ Knight’s Tour แต่ละเส้นมาแสดงต่อเนื่องในพื้นที่สามมิติ ผลลัพธ์ของอัลกอริทึมจึงไม่จบอยู่ที่คะแนน แต่กลายเป็นวัตถุดิบของศิลปะการคำนวณ

ใช้ GPU ของคุณ—not ours. เบราว์เซอร์วาดฉาก 3 มิติบนอุปกรณ์ของผู้ชม เซิร์ฟเวอร์ของเราส่งเพียงข้อมูลเส้นทางขนาดเล็ก มือถือหรืออุปกรณ์ที่ใช้แบตเตอรี่อาจอุ่นขึ้นได้
เพลิดเพลินแบบเต็มจอ ↗