WordChess · อาหารสมอง

คอมพิวเตอร์เลือกคำอย่างไร

ก่อนที่ AI จะลงเล่น มันต้องหาตาเดินของตัวเองให้เจอในกองฟางที่มีคำราวหนึ่งแสนห้าหมื่นคำ แล้วจึงหยุดค้นหา

เขียนและเรียบเรียงเป็นภาษาอังกฤษ ฉบับภาษาไทยนี้จัดทำขึ้นด้วยการแปลด้วยเครื่อง ในจุดที่ความแม่นยำมีความสำคัญ ให้ถือต้นฉบับภาษาอังกฤษเป็นหลัก อ่านต้นฉบับภาษาอังกฤษ →

01 · กองฟาง

ปริภูมิที่ใหญ่เกินกว่าจะมองเห็นได้

ยื่นไทล์ WordChess ครบทั้งชุดให้คนคนหนึ่งพร้อมคำสั่งว่า “เล่นคำดี ๆ สักคำ” เขาจะบีบปัญหาให้แคบลงโดยไม่ทันรู้ตัวว่าได้ทำไปแล้ว คอมพิวเตอร์ไม่มีสัญชาตญาณเช่นนั้น บนกระดานขนาด 25×25 และถือชุดไทล์ครบหนึ่งร้อยแผ่นของตัวเอง มันอาจลองคำใดก็ได้แทบทั้งหมดจาก 148,941 คำในพจนานุกรม และแต่ละคำก็วางลงได้ในพิกัดและทิศทางที่ถูกกติกานับพันแบบ ยิ่งไปกว่านั้น การวางคำหนึ่งจะถูกกติกาก็ต่อเมื่อตัวอักษรใหม่ทุกตัวที่มันเพิ่มลงไปประกอบเป็นคำจริงด้วยในจุดที่ตัดกับสิ่งที่อยู่บนกระดานแล้ว เอาจำนวนคำคูณด้วยจำนวนตำแหน่งวาง คูณด้วยเงื่อนไขการตัดกันนั้น แล้วคุณจะได้ปริภูมิการค้นหาที่ไม่มีผู้เล่นคนใด ไม่ว่าจะทำจากซิลิคอนหรือไม่ก็ตาม สามารถไล่แจกแจงและจัดอันดับได้ครบถ้วน

นี่คือเหตุผลที่เอนจินเกมคำศัพท์ระดับจริงจัง ซึ่งรวมถึง Quackle ซอฟต์แวร์อ้างอิงแบบโอเพนซอร์ส ไม่เคยไล่ลองพจนานุกรมทั้งเล่มแบบ brute force ⁴ โครงสร้าง GADDAG ของ Steven Gordon ในปี 1994 และ DAWG ที่มีมาก่อนหน้านั้น ช่วยให้โปรแกรมต่อคำงอกออกไปจากไทล์ที่อยู่บนกระดานแล้ว และตรวจจุดตัดไปพร้อมกัน เพื่อให้กิ่งที่ผิดกติกาถูกตัดทิ้งตั้งแต่เนิ่น ๆ แทนที่จะถูกคิดคะแนนแล้วค่อยทิ้ง ¹ งานนี้ไม่ใช่ “ไล่รายการทุกคำ” แต่คือ “สร้างเฉพาะตาเดินที่มีโอกาสถูกกติกา และทำให้เร็ว”

02 · นาฬิกา

ดีพอชนะสมบูรณ์แบบ

แม้ตัวสร้างตาเดินที่กระชับที่สุดก็ยังคืนตาเดินที่เป็นตัวเลือกมามากเกินกว่าจะประเมินอย่างลึกซึ้งได้ทั้งหมด ปัญหาที่สองจึงเป็นเรื่องเวลา Maven ของ Brian Sheppard โปรแกรมแรกที่เล่นเหนือกว่าคู่แข่งมนุษย์ระดับแนวหน้า เจอปัญหานี้ตรง ๆ และแก้ด้วยสองขั้นตอน ขั้นแรก ฮิวริสติกแบบเร็วจะเรียงตาเดินดิบตามคุณภาพคร่าว ๆ แล้วเฉพาะรายชื่อสั้น ๆ ของตาเดินที่มีแววที่สุดเท่านั้นที่จะถูกศึกษาอย่างละเอียด ด้วยการจำลองเกมไปข้างหน้าหลายครั้งเพื่อดูว่าตัวเลือกใดทำผลงานได้ดีที่สุดจริง ๆ ² เกมอื่นรู้จักแนวคิดเดียวกันนี้ในชื่ออื่น คือ rollout ของแบ็กแกมมอน และ playout ของโปรแกรมหมากล้อม ส่วนใน Maven เรียกว่า simulation (การจำลอง)

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

การรู้จักพจนานุกรมเป็นส่วนที่ง่าย การรู้ว่าเมื่อไรควรหยุดค้นมันต่างหากที่ยาก

03 · ความยากอย่างซื่อตรง

ความอ่อนแอที่คุณไว้ใจได้

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

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

สี่ระดับ ปรับด้วยขีดจำกัด วัดจากบันทึกการออกแบบและการสร้างของโปรเจกต์นี้

ระดับ	ขอบเขตคำศัพท์	งบเวลาค้นหา	ความยาวคำที่นิยม
ง่าย	คำทั่วไปเท่านั้น	สั้นที่สุด	สั้น
ปกติ	คำทั่วไป + ระดับกลาง + ครึ่งหนึ่งของคำหายาก	สั้น	ผสม
ยาก	ครบทั้งหมด	ยาว	ยาวขึ้น
แกรนด์มาสเตอร์	ครบทั้งหมด	ยาวที่สุด	ไม่จำกัด

04 · คู่ต่อสู้ ไม่ใช่เครื่องคิดเลข

อะไรทำให้มันรู้สึกเหมือนมนุษย์

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

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

Sources & notes

1. Wikipedia, "GADDAG", the move-generation data structure introduced by Steven A. Gordon (1994) that grows words from placed tiles and validates crossings during generation. en.wikipedia.org/wiki/GADDAG
2. Brian Sheppard, "World-Championship-Caliber Scrabble," Artificial Intelligence 134 (2002): 241–275, describes Maven, the first program to outperform the strongest human players against human opposition, with its selective move generation and its simulations of likely game scenarios. doi.org/10.1016/S0004-3702(01)00166-7. Overview of the program: en.wikipedia.org/wiki/Maven_(Scrabble)
3. Vina Nguyen, "How to Design a Worthy Opponent: AI in Game Development", on believable difficulty, deliberately handicapping the AI, and the resentment bred by opponents that appear to cheat (source of the quoted Sid Meier / Civilization account). vinawrites.com
4. Quackle (Jason Katz-Brown, John O'Laughlin, et al.), an open-source Scrabble engine bundling a GADDAG move generator, evaluator, and simulator for any lexicon or board. Source: github.com/quackle/quackle; project page: people.csail.mit.edu/jasonkb/quackle
5. M. Zohaib, "Dynamic Difficulty Adjustment (DDA) in Computer Games: A Review," Advances in Human-Computer Interaction (2018), survey of tuning challenge by adjusting AI capability rather than cheating. onlinelibrary.wiley.com/doi/10.1155/2018/5681652
6. WordChess-specific facts, the four difficulty tiers, the time/vocabulary/word-length levers, the randomized selection, and the opening-book collapse ("MY" fifteen times), are measured from this project's design and build notes.