เอนจิ้นหมากรุกมินิแมกซ์ที่สร้างด้วยนิพจน์ปกติ

 (nicholas.carlini.com)
4 คะแนน โดย GN⁺ 2025-01-08 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

เอนจิ้นหมากรุกมินิแมกซ์ 2 ชั้น

  • หมากรุกและนิพจน์ปกติ: ผู้เขียนได้สร้างโปรแกรมเล่นหมากรุกโดยใช้นิพจน์ปกติเท่านั้น โปรแกรมนี้ประกอบด้วยนิพจน์ปกติ 84,688 ตัวเพื่อรับสถานะกระดานหมากรุกเข้าไปและเดินที่ถูกต้อง

  • การออกแบบ CPU ด้วยนิพจน์ปกติ: การใช้นิพจน์ปกติเพื่อออกแบบการทำงานแบบไม่มีเงื่อนไขและชุดคำสั่ง SIMD (single instruction, multiple data) ช่วยให้สามารถเขียนโปรแกรมเล่นหมากรุกได้

  • โครงสร้างข้อมูล: สถานะปัจจุบันของคอมพิวเตอร์ถูกแสดงด้วยสตริงเดียวที่ประกอบด้วย "สแต็ค" ของโปรแกรมและตัวแปรทั้งหมด โดยแต่ละคำสั่งจะจัดการตัวแปรในสแต็คหรือทำการอ่าน/เขียนกับตัวแปรเฉพาะ

  • การทำงานของสแต็คพื้นฐาน:

    • คำสั่ง Push: เพิ่มค่าลงบนสุดของสแต็ค
    • คำสั่ง Pop: ลบค่าบนสุดออกจากสแต็ค

  • คำสั่งตัวแปร <-> สแต็ค:

    • การอ่านตัวแปร: โหลดเนื้อหาของตัวแปรไปยังยอดสแต็ค
    • การกำหนดตัวแปร: กำหนดค่าให้ตัวแปร และอัปเดตตัวแปรเดิมหรือสร้างตัวแปรใหม่ตามการมีอยู่ของมัน

  • คำสั่งเงื่อนไข: ใช้คำสั่งเงื่อนไขเพื่อควบคุมการไหลของโปรแกรม โดยเปิดหรือปิดส่วนหนึ่งของโปรแกรมตามเงื่อนไข

  • ความเป็นไปไม่ได้ของลูป: เนื่องจากนิพจน์ปกติไม่สามารถกำหนดลูปได้ จึงต้องแยกการคำนวณที่ซ้ำซ้อนออกล่วงหน้า

  • การรันหลายเธรดพร้อมกัน: ใช้ความสามารถ global replace ของนิพจน์ปกติเพื่อรันเธรดจำนวนมากพร้อมกันได้

  • การเขียนเอนจิ้นหมากรุก: เอนจิ้นหมากรุกถูกเขียนในลักษณะคล้ายกับภาษาโปรแกรมมิ่งอื่น ๆ และสามารถทำงานได้เร็วด้วยการขนานประมวลผล

  • การเล่นตา:

    • อ่านการเดินของผู้เล่น: อ่านการเดินที่ป้อนเข้ามาและตรวจสอบความถูกต้อง
    • การสร้างการตอบสนองของคอมพิวเตอร์: สร้างการตอบสนองทั้งหมดที่เป็นไปได้และเลือกการเดินที่ดีที่สุด

  • การค้นหามินิแมกซ์: เลือกการเดินที่ดีที่สุดผ่านการค้นหามินิแมกซ์ความลึก 2 ซึ่งกระบวนการนี้ทำงานอย่างมีประสิทธิภาพด้วยการขนานประมวลผล

โปรเจกต์นี้เป็นตัวอย่างที่แสดงการใช้นิพจน์ปกติอย่างสร้างสรรค์ในการสร้างเอนจิ้นหมากรุก และชี้ให้เห็นถึงพลังและการออกแบบคอมพิวเตอร์เชิงสร้างสรรค์ผ่านการใช้เทคนิคนี้

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-01-08
ความคิดเห็นจาก Hacker News

  • นักพัฒนาคนนี้เป็นผู้ที่พิสูจน์ว่า printf() เป็น Turing-complete และเขียนเกมยิงบุคคลที่ 1 ด้วย JavaScript ขนาด 13kB

  • โครงการนี้โดดเด่นตรงที่คำนวณตำแหน่งที่เป็นไปได้หลายตำแหน่งได้แบบขนาน

    • ใช้ Regular Expression เพื่อรันเธรดหลายตัวพร้อมกันได้

  • เรื่องบทสรุปในบล็อกนั้นไม่มีอะไรเสริมพิเศษ แต่หวังว่าคนอื่นจะลองทำโปรเจกต์ที่ดูไร้เหตุผลแบบนี้ให้มากขึ้น

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

  • เกมหมากรุกมีบั๊ก "เดินผิดกฎ, แพ้"

    • ในตัวอย่างเกมที่ให้มา เกมจบลงทั้งที่การเดินนั้นไม่ใช่การเดินผิดกฎ

  • คนที่ทำหมากรุกด้วย regex ตัวเดียวน่ากลัวกว่าคนที่ใช้ 84,688 regex

  • ได้แรงบันดาลใจและอยากให้เกียรติกับโปรเจกต์เหล่านี้มาก ๆ

  • แก้บั๊กที่เกี่ยวข้องกับการเดินไฟล์ a แล้ว

  • โครงการนี้ไม่ใช่แค่เอนจินหมากรุก แต่ยังเป็นคอมพิวเตอร์และภาษาระดับ assembly ที่ถูกสร้างขึ้นด้วย regular expression ล้วน ๆ

  • เคยมีโครงการหมากรุกที่เขียนด้วย sed มาก่อน

    • เวอร์ชัน sed ใช้คำสั่งควบคุมการทำงาน และมีการค้นหาเพียง 1ply เท่านั้น

  • เมื่อเริ่มด้วย a2a4 เกมจะไม่ยอมแพ้เร็วขนาดนั้น

  • การลองทำอะไรบางอย่างโดยไม่มีเป้าหมายที่ชัดเจนว่า 'เชิงสร้างสรรค์' อาจช่วยค้นพบบางสิ่งใหม่ ๆ และนำไปสู่ความก้าวหน้าได้

    • เอนจินมักเสียตัวหมากตั้งแต่ต้นเกม
    • หากพิมพ์ตัวอักษรตัวใหญ่ จะถูกแสดงว่าเป็นการเดินผิดกฎ

  • กำลังพยายามทำสิ่งที่เชื่อว่านวัตกรรมและให้ผลเชิงสร้างสรรค์