เกมกระดานปัญญาประดิษฐ์: อัลกอริทึม Minimax: 8 ขั้นตอน

2024 ผู้เขียน: John Day | [email protected]. แก้ไขล่าสุด: 2024-01-30 13:04

เคยสงสัยหรือไม่ว่าคอมพิวเตอร์ที่คุณเล่นกับหมากรุกหรือหมากฮอสถูกสร้างขึ้นมาอย่างไร? ไม่ต้องมองหาที่อื่นนอกจากคำแนะนำนี้เพราะมันจะแสดงให้คุณเห็นถึงวิธีการสร้างปัญญาประดิษฐ์ (AI) ที่เรียบง่าย แต่มีประสิทธิภาพโดยใช้อัลกอริทึม Minimax! เมื่อใช้ Minimax Algorithm AI จะวางแผนและคิดออกได้ดี (หรืออย่างน้อยก็เลียนแบบกระบวนการคิด) ตอนนี้ ฉันสามารถให้รหัสสำหรับ AI ที่ฉันสร้างกับคุณได้ แต่นั่นคงไม่สนุกแน่ ฉันจะอธิบายตรรกะที่อยู่เบื้องหลังตัวเลือกของคอมพิวเตอร์

ในคำแนะนำนี้ ฉันจะแนะนำคุณเกี่ยวกับขั้นตอนในการสร้าง AI สำหรับ Othello (AKA Reversi) ใน python คุณควรมีความเข้าใจขั้นกลางเกี่ยวกับวิธีการเขียนโค้ดใน python ก่อนดำเนินการกับโปรเจ็กต์นี้ ต่อไปนี้คือเว็บไซต์ที่ดีบางส่วนที่คุณควรดูเพื่อเตรียมคุณให้พร้อมสำหรับคำแนะนำนี้: w3schools หรือ learnpython ในตอนท้ายของคำแนะนำนี้ คุณควรมี AI ที่จะทำการเคลื่อนไหวที่คำนวณได้และควรจะสามารถเอาชนะมนุษย์ส่วนใหญ่ได้

เนื่องจาก Instructable นี้จะกล่าวถึงวิธีการสร้าง AI เป็นหลัก ฉันจะไม่อธิบายวิธีออกแบบเกมใน python ฉันจะให้รหัสสำหรับเกมที่มนุษย์สามารถเล่นกับมนุษย์คนอื่นและปรับเปลี่ยนเพื่อให้คุณสามารถเล่นเกมที่มนุษย์เล่นกับ AI

ฉันได้เรียนรู้วิธีสร้าง AI นี้ผ่านโปรแกรมภาคฤดูร้อนที่ Columbia SHAPE ฉันมีช่วงเวลาที่ดีที่นั่น ดังนั้นลองดูที่เว็บไซต์ของพวกเขาเพื่อดูว่าคุณจะสนใจหรือไม่

เมื่อเราจัดการด้านลอจิสติกส์ได้แล้ว มาเริ่มเขียนโค้ดกันเลย!

(ฉันใส่โน้ตสองสามตัวในภาพเพื่อให้แน่ใจว่าได้ดู)

เสบียง

มันง่าย:

1) คอมพิวเตอร์ที่มีสภาพแวดล้อมแบบไพธอน เช่น Spyder หรือ IDLE

2) ดาวน์โหลดไฟล์สำหรับเกม Othello จาก GitHub. ของฉัน

3) สมองของคุณพร้อมติดตั้งความอดทน

ขั้นตอนที่ 1: ดาวน์โหลดไฟล์ที่จำเป็น

เมื่อคุณเข้าสู่ GitHub ของฉัน คุณจะเห็น 5 ไฟล์ ดาวน์โหลดทั้ง 5 รายการและวางไว้ในโฟลเดอร์เดียวกัน ก่อนที่เราจะเปิดเกม ให้เปิดไฟล์ทั้งหมดในสภาพแวดล้อมของสปายเดอร์

นี่คือสิ่งที่ไฟล์ทำ:

1) othello_gui.py ไฟล์นี้สร้างบอร์ดเกมให้ผู้เล่นได้เล่น (ไม่ว่าจะเป็นคนหรือคอมพิวเตอร์)

2) othello_game.py ไฟล์นี้เล่นคอมพิวเตอร์สองเครื่องต่อกันโดยไม่มีกระดานเกม และแสดงเฉพาะคะแนนและตำแหน่งเคลื่อนที่

3) ai_template.py นี่คือที่ที่คุณจะใส่รหัสทั้งหมดของคุณเพื่อสร้าง AI. ของคุณ

4) randy_ai.py นี่คือ AI ที่สร้างไว้ล่วงหน้าซึ่งเลือกการเคลื่อนไหวแบบสุ่ม

5) othello_shared.py ฟังก์ชันที่สร้างไว้ล่วงหน้าจำนวนมากที่คุณสามารถใช้เพื่อสร้าง AI ของคุณ เช่น เพื่อตรวจสอบการเคลื่อนไหวที่มีอยู่ คะแนน หรือสถานะของกระดาน

6) ไฟล์อื่นๆ อีกสามไฟล์: Puma.py, erika_5.py และ nathan.py ที่ฉันสร้างเอง Erika และ Nathan ตามลำดับจากโปรแกรม SHAPE เหล่านี้เป็น AI ที่แตกต่างกันสามตัวที่มีรหัสเฉพาะ

ขั้นตอนที่ 2: วิธีเปิดและเล่น Python Othello

เมื่อคุณเปิดไฟล์ทั้งหมดแล้ว ที่มุมล่างขวาของหน้าจอ ให้พิมพ์ "run othello_gui.py" แล้วกด Enter ใน IPython Console หรือในเทอร์มินัล Mac พิมพ์ "python othello_gui.py" (หลังจากที่คุณอยู่ในโฟลเดอร์ที่ถูกต้องแล้ว) จากนั้นบอร์ดจะปรากฏขึ้นบนหน้าจอของคุณ โหมดนี้เป็นโหมดมนุษย์กับมนุษย์ แสงไปที่สองและมืดก่อน ดูวิดีโอของฉันหากคุณสับสน ที่ด้านบนมีคะแนนของกระเบื้องแต่ละสี ในการเล่น ให้คลิกพื้นที่เคลื่อนที่ที่ถูกต้องเพื่อวางไทล์ที่นั่น จากนั้นมอบคอมพิวเตอร์ให้กับคู่ต่อสู้ของคุณที่จะทำแบบเดียวกันและทำซ้ำ

หากคุณไม่ทราบวิธีเล่น Othello โปรดอ่านกฎเหล่านี้จากเว็บไซต์ ultra board:

สีดำจะเคลื่อนไหวก่อนเสมอ การย้ายทำได้โดยการวางแผ่นดิสก์ที่มีสีของผู้เล่นไว้บนกระดานในตำแหน่งที่ "ออกด้านข้าง" แผ่นดิสก์ของฝ่ายตรงข้ามอย่างน้อยหนึ่งแผ่น ดิสก์หรือแถวของดิสก์ถูกขนาบข้างเมื่อถูกล้อมรอบด้วยปลายด้วยจานสีตรงข้าม แผ่นดิสก์อาจขนาบข้างแผ่นดิสก์จำนวนเท่าใดก็ได้ในหนึ่งแถวขึ้นไปในทิศทางใดก็ได้ (แนวนอน แนวตั้ง เส้นทแยงมุม)…. (อ่านจบที่เว็บไซต์)

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

ตอนนี้คุณสามารถเล่นเกมกับเพื่อนได้แล้ว มาสร้าง AI ที่คุณสามารถเล่นด้วยกันเถอะ

ขั้นตอนที่ 3: อัลกอริทึมขั้นต่ำสุด: การสร้างสถานการณ์จำลอง

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

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

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

ขั้นตอนที่ 4: Minimax: การประเมินการกำหนดค่าบอร์ด

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

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

มีหลายวิธีในการทำเช่นนี้ และฉันมีการวิเคราะห์พฤติกรรมที่แตกต่างกันสามแบบเพื่อประเมินชิ้นส่วนของกระดาน ฉันสนับสนุนให้คุณสร้างฮิวริสติกในแบบของคุณเอง ฉันอัปโหลด AI ที่แตกต่างกันสามตัวไปยัง GitHub ของฉันโดยผู้ผลิตสามคน โดยมีการวิเคราะห์พฤติกรรมที่แตกต่างกันสามแบบ: Puma.py, erika5.py, nathanh.py

ขั้นตอนที่ 5: อัลกอริทึมขั้นต่ำสุด: การเลือกการเคลื่อนไหวที่ดีที่สุด

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

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

คำนิยาม: โหนดหลัก - โหนดที่ส่งผลหรือสร้างโหนดด้านล่าง; ที่มาของโหนดย่อย - โหนดที่มาจากโหนดหลักเดียวกัน

โหนดที่ว่างเปล่าแสดงถึงการย้ายที่ AI จะทำเพื่อให้ได้สถานะกระดานที่ดีที่สุด เริ่มจากการเปรียบเทียบลูกๆ ของโหนดซ้ายสุด: 10, -3, 5. เนื่องจากผู้เล่นที่กำลังขยายสูงสุดจะทำการเคลื่อนไหว มันจะเลือกท่าที่จะให้คะแนนมากที่สุด: 10. ดังนั้น เราจึงเลือกและจัดเก็บสิ่งนั้น ย้ายไปพร้อมกับคะแนนของกระดานและเขียนลงในโหนดหลัก ตอนนี้ที่ 10 อยู่ในโหนดหลัก ตอนนี้ผู้เล่นที่ย่อเล็กสุดจะเลี้ยว อย่างไรก็ตาม โหนดที่เราจะเปรียบเทียบ 10 กับนั้นว่างเปล่า เราจึงต้องประเมินโหนดนั้นก่อน ก่อนที่ผู้เล่นที่ย่อขนาดจะสามารถเลือกได้ ดังนั้นเราจึงกลับไปที่เทิร์นของผู้เล่นสูงสุดและเปรียบเทียบลูกของโหนดที่อยู่ติดกัน: 8, -2 การขยายใหญ่สุดจะเลือก 8 และเราเขียนสิ่งนั้นในโหนดหลักที่ว่างเปล่า เมื่ออัลกอริทึมเสร็จสิ้นการเติมช่องว่างสำหรับโหนดย่อยด้านบนแล้ว ผู้เล่นย่อขนาดสามารถเปรียบเทียบเด็กเหล่านั้น - 10 และ 8 และเลือก 8 จากนั้นอัลกอริทึมจะทำซ้ำขั้นตอนนี้จนกว่าต้นไม้ทั้งหมดจะเต็ม ในตอนท้ายของตัวอย่างนี้ เรามีคะแนน 8 ซึ่งเป็นสถานะกระดานสูงสุดที่ AI สามารถเล่นได้ โดยถือว่าคู่ต่อสู้เล่นอย่างเหมาะสมที่สุด ดังนั้น AI จะเลือกการเคลื่อนไหวแรกที่นำไปสู่สถานะกระดาน 8 และหากคู่ต่อสู้เล่นอย่างเหมาะสม AI ควรเล่นทุกการเคลื่อนไหวเพื่อเข้าสู่สถานะกระดาน 8 (ทำตามหมายเหตุในภาพของฉัน)

ฉันรู้ว่ามันเยอะมาก หากคุณเป็นคนประเภทหนึ่งที่ต้องการให้ใครสักคนคุยกับคุณเพื่อทำความเข้าใจ ต่อไปนี้คือวิดีโอสองสามรายการที่ฉันดูเพื่อช่วยให้ฉันเข้าใจแนวคิดเบื้องหลังสิ่งนี้: 1, 2, 3

ขั้นตอนที่ 6: อัลกอริทึม Minimax: Pseudocode

หลังจากที่คุณเข้าใจตรรกะที่อยู่เบื้องหลังอัลกอริทึม minimax แล้ว ให้ดูที่ pseudocode (ฟังก์ชันที่เป็นสากลสำหรับรหัสทั้งหมด) จากวิกิพีเดีย:

ฟังก์ชั่น minimax(โหนด, ความลึก, maximizingPlayer) is

ถ้าความลึก = 0 หรือโหนดเป็นโหนดปลายทางแล้ว

ส่งคืนค่าฮิวริสติกของโหนด

ถ้า maximizingPlayer แล้ว

ค่า:= −∞

สำหรับแต่ละลูกของโหนด do

ค่า:= max(value, minimax(child, depth − 1, FALSE))

ค่าส่งคืน

อื่น ๆ (* ย่อขนาดผู้เล่น *)

ค่า:= +∞

สำหรับแต่ละลูกของโหนด do

ค่า:= min(value, minimax(child, depth − 1, TRUE))

ค่าส่งคืน

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

pseudocode นี้กำลังทำซ้ำกระบวนการที่ฉันอธิบายไว้ในสองขั้นตอนก่อนหน้า ตอนนี้ มาทำขั้นตอนต่อไปและถูกต้องในโค้ดหลาม

ขั้นตอนที่ 7: สร้าง AI ด้วย Ai_template.py

ก่อนที่จะดูโค้ด Minimax AI ของฉัน ให้ลองสร้าง AI ของคุณเองด้วยไฟล์ ai_template.py และรหัสเทียมที่เราพูดถึงในขั้นตอนสุดท้าย มีสองฟังก์ชันในเทมเพลต ai ที่เรียกว่า: def minimax_min_node(board, color) และ def minimax_max_node(board, color) แทนที่จะให้ฟังก์ชัน minimax เรียกตัวเองซ้ำๆ เรามีสองฟังก์ชันที่แตกต่างกัน ซึ่งเรียกกันและกัน ในการสร้างฮิวริสติกเพื่อประเมินสถานะของบอร์ด คุณจะต้องสร้างฟังก์ชันของคุณเอง มีฟังก์ชันที่สร้างไว้ล่วงหน้าในไฟล์ othello_shared.py ที่คุณสามารถใช้สร้าง AI ของคุณได้

เมื่อคุณมี AI แล้ว ให้ลองใช้กับ randy_ai.py ในการรันสอง ais ต่อกัน ให้พิมพ์ "python othello_gui.py (ใส่ชื่อไฟล์ ai).py (ใส่ชื่อไฟล์).py" ใน terminal ของ mac หรือพิมพ์ "run othello_gui.py (insert ai file name).py (ใส่ชื่อไฟล์).py" และตรวจสอบให้แน่ใจว่าคุณอยู่ในไดเร็กทอรีที่ถูกต้อง ดูขั้นตอนที่แน่นอนในวิดีโอของฉันด้วย

ขั้นตอนที่ 8: ถึงเวลาสร้าง AI Fight

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