Tic Tac Toe บน Arduino พร้อม AI (Minimax Algorithm): 3 ขั้นตอน

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

ในคำแนะนำนี้ ฉันจะแสดงวิธีสร้างเกม Tic Tac Toe ด้วย AI โดยใช้ Arduino คุณสามารถเล่นกับ Arduino หรือดู Arduino เล่นกับตัวเอง

ฉันใช้อัลกอริธึมที่เรียกว่า "minimax Algorithm" ซึ่งไม่เพียงแต่ใช้เพื่อสร้าง AI สำหรับ Tic Tac Toe เท่านั้น แต่ยังสามารถใช้สำหรับเกมอื่นๆ ที่หลากหลาย เช่น Four in a Row หมากฮอส หรือแม้แต่หมากรุก เกมอย่างหมากรุกนั้นซับซ้อนมากและต้องใช้อัลกอริธึมเวอร์ชันที่ละเอียดกว่านี้มาก สำหรับเกม Tic Tac Toe ของเรา เราสามารถใช้อัลกอริธึมเวอร์ชันที่ง่ายที่สุด ซึ่งถึงกระนั้นก็ค่อนข้างน่าประทับใจ อันที่จริง AI นั้นดีมากจนไม่สามารถเอาชนะ Arduino ได้!

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

ขั้นตอนที่ 1: สร้างและเล่น

ในการสร้างเกม Tic Tac Toe คุณจะต้องมีส่วนประกอบต่อไปนี้:

• Arduino Uno
• 9 WS2812 RGB LEDs
• ปุ่มกด 9 ปุ่ม
• สายไฟและสายจัมเปอร์

ต่อส่วนประกอบตามที่แสดงในร่าง Fritzing จากนั้นอัปโหลดรหัสไปยัง Arduino ของคุณ

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

คุณสามารถรับชม Arduino "คิด" ได้โดยเปิด Serial Monitor สำหรับทุกการเคลื่อนไหวที่เป็นไปได้ อัลกอริทึมจะคำนวณคะแนนที่ระบุว่าการเคลื่อนไหวนี้จะนำไปสู่การชนะ (ค่า 10) หรือการสูญเสีย (ค่า -10) สำหรับ Arduino หรือเสมอ (ค่า 0)

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

โปรดทราบว่าคุณไม่สามารถเอาชนะ Arduino ได้ ทุกเกมจะจบลงด้วยผลเสมอหรือแพ้ หากคุณทำพลาด เนื่องจากอัลกอริทึมจะเลือกการเคลื่อนไหวที่ดีที่สุดเสมอ อย่างที่คุณอาจทราบ เกมของ Tic Tac Toe จะจบลงด้วยผลเสมอหากผู้เล่นทั้งคู่ไม่ผิดพลาด ในโหมดสาธิต ทุกเกมจบลงด้วยการเสมอกัน เพราะอย่างที่เราทุกคนทราบกันดีว่าคอมพิวเตอร์ไม่เคยทำผิดพลาด;-)

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

อัลกอริทึมประกอบด้วยสององค์ประกอบ: ฟังก์ชันการประเมินและกลยุทธ์การค้นหา ฟังก์ชันการประเมินเป็นฟังก์ชันที่กำหนดค่าตัวเลขให้กับตำแหน่งบอร์ด หากตำแหน่งนั้นเป็นตำแหน่งสุดท้าย (เช่น ตำแหน่งที่ผู้เล่นสีน้ำเงินหรือผู้เล่นสีแดงชนะหรือไม่มีผู้เล่นคนใดชนะ) ฟังก์ชันการประเมินนั้นง่ายมาก: สมมติว่า Arduino เล่นสีน้ำเงินและผู้เล่นที่เป็นมนุษย์เล่นเป็นสีแดง. หากตำแหน่งนั้นเป็นตำแหน่งที่ชนะสำหรับสีน้ำเงิน ฟังก์ชันจะกำหนดค่า 10 ให้กับตำแหน่งนั้น หากเป็นตำแหน่งที่ชนะสำหรับสีแดง ฟังก์ชันจะกำหนดค่า -10 ให้กับตำแหน่งนั้น และถ้าตำแหน่งเสมอกัน ฟังก์ชันจะกำหนดค่าเป็น 0

เมื่อถึงตาของ Arduino มันต้องการเลือกการเคลื่อนไหวที่เพิ่มมูลค่าของฟังก์ชันการประเมินให้สูงสุด เพราะการเพิ่มมูลค่าสูงสุดหมายความว่ามันจะชอบที่จะชนะมากกว่าเสมอ (10 มากกว่า 0) และให้การเสมอมากกว่าการแพ้ (0 มากกว่า -10) โดยการโต้แย้งที่คล้ายคลึงกัน ฝ่ายตรงข้ามต้องการเล่นในลักษณะที่เธอลดค่าของฟังก์ชันการประเมิน

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

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

ขั้นตอนที่ 3: การแก้ไขปัญหาและขั้นตอนเพิ่มเติม

หากคุณกดปุ่มและไฟ LED อื่นที่ไม่ใช่ปุ่มที่ตรงกับปุ่มนั้นติดสว่าง อาจเป็นเพราะสายไฟบนพิน A0-A2 หรือ 4-6 ปะปนกัน หรือคุณเชื่อมต่อ LED ในลำดับที่ไม่ถูกต้อง

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

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

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