AI -тэй Arduino дээрх Tic Tac Toe (Minimax алгоритм): 3 алхам

2024 Зохиолч: John Day | [email protected]. Хамгийн сүүлд өөрчлөгдсөн: 2024-01-30 11:04

Энэхүү гарын авлагад би Arduino ашиглан хиймэл оюун ухаан ашиглан Tic Tac Toe тоглоомыг хэрхэн яаж хийхийг танд үзүүлэх гэж байна. Та Arduino -ийн эсрэг тоглох эсвэл Arduino -ийн эсрэг тоглолтыг үзэх боломжтой.

Би "minimax алгоритм" гэж нэрлэгддэг алгоритмыг ашиглаж байгаа бөгөөд үүнийг зөвхөн Tic Tac Toe -д хиймэл оюун ухаан бүтээхэд ашиглаж болохоос гадна дараалан дөрөв, даам, бүр шатар гэх мэт бусад олон тоглоомд ашиглаж болно. Шатар гэх мэт тоглоомууд нь маш нарийн төвөгтэй бөгөөд алгоритмын илүү нарийн хувилбаруудыг шаарддаг. Манай Tic Tac Toe тоглоомын хувьд бид алгоритмын хамгийн энгийн хувилбарыг ашиглаж болох боловч энэ нь үнэхээр гайхалтай юм. Үнэндээ хиймэл оюун ухаан нь маш сайн тул Arduino -г ялах боломжгүй юм!

Тоглоомыг бүтээхэд хялбар байдаг. Танд хэдхэн бүрэлдэхүүн хэсэг, миний бичсэн ноорог хэрэгтэй болно. Хэрэв та энэ алгоритм хэрхэн ажилладагийг ойлгохыг хүсч байвал би илүү дэлгэрэнгүй тайлбарыг оруулсан болно.

Алхам 1: Бүтээх, тоглох

Tic Tac Toe тоглоомыг бүтээхийн тулд танд дараах бүрэлдэхүүн хэсгүүд хэрэгтэй болно.

• Arduino Uno
• 9 WS2812 RGB LED
• 9 товчлуур
• зарим утас ба холбогч кабель

Fritzing ноорог дээр үзүүлсэн шиг бүрэлдэхүүн хэсгүүдийг утсаар холбоно. Дараа нь кодыг Arduino -д байршуулна уу.

Анхдагч байдлаар Arduino эхний ээлжийг авдаг. Аливаа зүйлийг илүү сонирхолтой болгохын тулд эхний алхамыг санамсаргүй байдлаар сонгоно. Эхний алхам хийсний дараа Arduino хамгийн сайн алхамыг тодорхойлохын тулд minimax алгоритмыг ашигладаг. Та Arduino -г дахин тохируулснаар шинэ тоглоом эхлүүлэх болно.

Та Arduino -ийн Цуваа мониторыг нээж "бодохыг" үзэх боломжтой. Боломжит алхам бүрийн хувьд алгоритм нь энэхүү алхам нь Arduino -ийн хожил (10 -ийн утга) эсвэл алдагдал (-10 -ийн утга) болох эсэхийг харуулсан үнэлгээг тооцоолно.

Та зургийн эхэнд "#define DEMO_MODE" гэсэн мөрийг тайлбарлахгүйгээр Arduino -ийн эсрэг тоглолтыг үзэх боломжтой. Хэрэв та өөрчилсөн ноорог байршуулах юм бол Arduino эхний алхамыг санамсаргүй байдлаар хийж, дараа нь минимакс алгоритмыг ашиглан тоглогч бүрийн хувьд хамгийн сайн алхамыг тодорхойлдог.

Та Arduino -г хожиж чадахгүй гэдгийг анхаарна уу. Алдаа гарвал тоглолт бүр тэнцэх эсвэл хожигдох болно. Энэ нь алгоритм нь үргэлж хамгийн боломжит алхамыг сонгож авдагтай холбоотой юм. Хоёр тоглогч хоёулаа алдаа гаргаагүй бол Tic Tac Toe -ийн тоглолт үргэлж тэнцээгээр дуусах болно гэдгийг та мэдэж байгаа байх. Демо горимд тоглоом бүр тэнцээгээр төгсдөг, учир нь бидний мэдэж байгаагаар компьютер хэзээ ч алдаа гаргадаггүй;-)

Алхам 2: Minimax алгоритм

Алгоритм нь үнэлгээний функц ба хайлтын стратеги гэсэн хоёр бүрэлдэхүүн хэсгээс бүрдэнэ. Үнэлгээний функц нь самбарын байрлалд тоон утгыг өгдөг функц юм. Хэрэв байрлал нь эцсийн байрлал бол (өөрөөр хэлбэл цэнхэр тоглогч эсвэл улаан тоглогч хоёулаа хожсон эсвэл тоглогч хоёулаа хожоогүй байрлал) үнэлгээний функц маш энгийн байдаг: Ардуино цэнхэр, хүний тоглогч улаан тоглодог гэж бодъё.. Хэрэв энэ байрлал нь цэнхэр өнгөөр ялсан байрлал бол функц нь тухайн байрлалд 10 гэсэн утгыг өгдөг; Хэрэв энэ нь улаанаар ялсан байрлал бол функц нь байрлалд -10 гэсэн утгыг өгдөг; хэрэв байрлал тэнцсэн бол функц нь 0 гэсэн утгыг өгдөг.

Arduino -ийн ээлж ирэхэд үнэлгээний функцын үнэ цэнийг хамгийн их байлгах алхамыг сонгохыг хүсдэг. Учир нь үнэ цэнийг нэмэгдүүлэх нь тэнцээнээс (10 нь 0 -ээс их) хожихыг илүүд үзэж, хожигдохоос илүү тэнцэхийг зөвшөөрнө гэсэн үг юм. 0 нь -10 -аас их). Үүнтэй төстэй аргументаар өрсөлдөгч нь үнэлгээний функцын үнэ цэнийг багасгахын тулд тоглохыг хүсдэг.

Эцсийн бус байрлалын хувьд алгоритм нь үнэлгээний функцын утгыг рекурсив хайлтын стратегиар тооцоолно. Одоогийн байрлалаас эхлэн цэнхэр тоглогч, улаан тоглогчийн хийж болох бүх хөдөлгөөнийг ээлжлэн дуурайдаг. Үүнийг диаграмм дээрх шиг мод хэлбэрээр дүрсэлж болно. Эцсийн байрлалд ирмэгц үнэлгээний функцын утгыг доод рекурсын түвшингээс дээд рекурсын түвшинд хүргэж, ухарч эхэлдэг. Энэ нь үнэлгээний функцын утгыг доод рекурсын түвшингээс байрлал дахь байрлал хүртэлх хамгийн их (хэрэв харгалзах рекурсын алхамд цэнхэр тоглогчийн ээлж бол) эсвэл хамгийн бага (хэрэв харгалзах рекурсын алхамд улаан тоглогчийн ээлж бол) оноодог. рекурсын түвшин өндөр. Эцэст нь, алгоритм нь ухарч дуусаад одоогийн байрлалдаа дахин очсоны дараа үнэлгээний функцын хамгийн их утгатай тэр алхамыг (эсвэл нэг алхамыг) авна.

Энэ нь жаахан хийсвэр сонсогдож магадгүй ч үнэндээ тийм ч хэцүү биш юм. Диаграмын дээд хэсэгт үзүүлсэн байрлалыг анхаарч үзээрэй. Эхний давталтын алхамд цэнхэр өнгийн гурван өөр алхам хийх боломжтой. Цэнхэр нь үнэлгээний функцын үнэ цэнийг нэмэгдүүлэхийг хичээдэг. Цэнхэр өнгийн хөдөлгөөн бүрийн хувьд улаан хийх хоёр алхам байдаг. Улаан нь үнэлгээний функцын үнэ цэнийг багасгахыг хичээдэг. Баруун дээд буланд цэнхэр өнгө тоглохыг анхаарч үзээрэй. Хэрэв улаан нь төвийн хайрцагт тоглодог бол улаан хожсон болно (-10). Нөгөө талаас, улаан нь доод талын доод хайрцагт тоглодог бол дараагийн алхамд хөх ялах болно (10). Тиймээс, хэрэв цэнхэр баруун дээд буланд тоглодог бол улаан нь төвийн хайрцагт тоглодог, учир нь энэ нь үнэлгээний функцийн утгыг бууруулдаг. Үүний нэгэн адил, хэрэв цэнхэр нь доод талын хайрцагт тоглодог бол улаан нь төвийн хайрцагт дахин тоглох болно, учир нь энэ нь үнэлгээний функцийг багасгадаг. Нөгөөтэйгүүр цэнхэр өнгийг төвийн хайрцагт тоглодог бол улаан нь ямар алхам хийх нь хамаагүй, цэнхэр үргэлж ялах болно (10). Цэнхэр нь үнэлгээний функцийг хамгийн дээд хэмжээнд байлгахыг хүсдэг тул энэ нь бусад хайрцаг (-10) -аас илүү үнэлгээний функц (10) -ийг илүү ихээр үнэлдэг тул төвийн хайрцагт тоглодог.

Алхам 3: Алдааг олж засварлах, цаашдын алхамууд

Хэрэв та товчлуурыг дарж, товчлуураас өөр LED асдаг бол A0-A2 эсвэл 4-6 зүү дээрх утсыг хольсон эсвэл LED-ийг буруу дарааллаар холбосон байх магадлалтай.

Алгоритм нь Arduino -г аль болох хурдан ялах боломжийг олгодог алхамыг үргэлж сонгодоггүй гэдгийг анхаарна уу. Үнэн хэрэгтээ, Arduino нь ялах алхам хийх алхамыг сонгоогүй тул би алгоритмыг дибаг хийхэд хэсэг хугацаа зарцуулсан. Үүний оронд дараа нь нэг алхам хожих нь баталгаатай алхамыг сонгосон гэдгээ ойлгох хүртлээ хэсэг хугацаа зарцуулсан. Хэрэв та хүсвэл алгоритмыг өөрчлөхийг оролдож болно, ингэснээр хожиж хожихоосоо хожих алхамыг үргэлж илүүд үзэх болно.

Энэхүү төслийн өргөтгөл нь 4x4 эсвэл бүр 5x5 хэмжээтэй Tic Tac Toe хиймэл оюун ухаан бүтээх алгоритмыг ашиглах явдал юм. Гэсэн хэдий ч алгоритмыг шалгах шаардлагатай албан тушаалын тоо маш хурдацтай өсч байгааг анхаарна уу. Тухайн байрлал нь тухайн тоглогчийн хувьд сайн эсвэл муу байх магадлалд үндэслэн эцсийн биш байр сууринд үнэлэмж өгөх замаар үнэлгээний функцийг илүү ухаалаг болгох арга замыг хайж олох хэрэгтэй болно. Хэрэв та өөр алхам хийхээс илүү хайгуул хийх нь зохисгүй гэж үзвэл рекурсыг эрт зогсоох замаар хайлтыг илүү ухаалаг болгохыг оролдож болно.

Санах ой хязгаарлагдмал тул Arduino нь ийм өргөтгөл хийх хамгийн сайн платформ биш байж магадгүй юм. Рекурци нь програмыг гүйцэтгэх явцад стекийг өсгөх боломжийг олгодог бөгөөд хэрэв стек хэт их өсвөл энэ нь програмын санах ойг гэмтээж улмаар сүйрэлд хүргэж болзошгүй юм. Би энэ төсөлд зориулж Arduino -г сонгосон бөгөөд энэ нь иймэрхүү асуудлыг шийдэх хамгийн сайн сонголт биш юм.