Ширээний тоглоом хиймэл оюун ухаан: Minimax алгоритм: 8 алхам

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

Таны шатар эсвэл даамын эсрэг тоглодог компьютерууд хэрхэн бүтээгдсэн талаар та бодож байсан уу? Зааварчилгааг бүү хайгаарай, энэ нь Minimax алгоритмыг ашиглан энгийн боловч үр дүнтэй хиймэл оюун ухаан (AI) хэрхэн хийхийг танд үзүүлэх болно. Minimax алгоритмыг ашигласнаар хиймэл оюун ухаан нь сайтар төлөвлөж, бодож боловсруулсан алхамуудыг хийдэг (эсвэл наад зах нь бодлын үйл явцыг дуурайдаг). Одоо би танд хиймэл оюун ухааны кодоо өгөх болно, гэхдээ энэ нь хөгжилтэй биш байх болно. Би компьютерийн сонголтын логикийг тайлбарлах болно.

Энэхүү зааварчилгааны номонд би Отелло (AKA Reversi) хиймэл оюун ухааныг питон дээр хэрхэн хийх талаар алхам алхмаар тайлбарлах болно. Та энэ төслийг шийдвэрлэхээс өмнө python дээр хэрхэн код бичих талаар дунд зэргийн ойлголттой байх ёстой. Энэхүү зааварчилгаанд бэлтгэхийн тулд үзэх хэрэгтэй хэдэн сайн вэбсайтууд энд байна: w3schools эсвэл learnpython. Энэхүү зааварчилгааны төгсгөлд та тооцоолсон алхам хийх AI -тэй байх ёстой бөгөөд ихэнх хүмүүсийг ялж чаддаг байх ёстой.

Энэхүү заавар нь үндсэндээ хиймэл оюун ухаан хэрхэн хийх тухай байх тул би питон дээр тоглоом хэрхэн зохиох талаар тайлбарлахгүй. Үүний оронд би хүн өөр хүний эсрэг тоглох боломжтой тоглоомын кодыг өгч, үүнийг хийснээр та хүн хиймэл оюун ухааны эсрэг тоглодог тоглоом тоглох болно.

Би энэ хиймэл оюун ухааныг хэрхэн бүтээхийг зуны Columbia SHAPE хөтөлбөрөөр дамжуулан сурсан. Би тэнд сайхан өнгөрөөсөн тул тэдний вэбсайтыг үзээд сонирхож магадгүй эсэхийг үзээрэй.

Логистикийг тасалдуулсны дараа кодчилолоо эхлүүлцгээе!

(Би зураг дээр хэд хэдэн тэмдэглэл оруулсан тул заавал үзээрэй.)

Хангамж

Энэ амархан:

1) Spyder эсвэл IDLE зэрэг питон орчинтой компьютер

2) Отелло тоглоомын файлуудыг миний GitHub дээрээс татаж аваарай

3) Таны тархи тэвчээртэй суулгасан

Алхам 1: Шаардлагатай файлуудыг татаж авах

Та миний GitHub руу орохдоо 5 файл харах ёстой. 5 -ийг бүгдийг нь татаж аваад нэг хавтсанд байрлуул. Тоглоомыг ажиллуулахаасаа өмнө тагнуулын орчинд байгаа бүх файлыг нээнэ үү.

Файлууд юу хийдэг вэ:

1) othello_gui.py энэ файл нь тоглогчид тоглох тоглоомын самбарыг бий болгодог (хүн эсвэл компьютер)

2) othello_game.py энэ файл нь тоглоомын самбаргүйгээр бие биенийхээ эсрэг хоёр компьютер тоглодог бөгөөд зөвхөн оноо, байрлалыг харуулдаг

3) ai_template.py бол та AI -ээ хийхийн тулд бүх кодоо оруулах болно

4) randy_ai.py бол санамсаргүй байдлаар хөдөлгөөнөө сонгодог хиймэл оюун ухаан юм

5) othello_shared.py-ийг ашиглан хиймэл оюун ухаанаа хийж болох боломжтой хөдөлгөөнүүд, оноо, самбарын төлөв зэргийг шалгах гэх мэт урьдчилан ашиглаж болох олон тооны функцүүд.

6) SHAPE програмаас миний, Эрика, Натан нарын хийсэн Puma.py, erika_5.py, nathan.py гэсэн гурван өөр файлууд нь өвөрмөц кодтой гурван өөр AI юм.

Алхам 2: Python Othello -г хэрхэн нээх, тоглох талаар

Бүх файлыг нээсний дараа дэлгэцийн баруун доод буланд "run othello_gui.py" гэж бичээд IPython консол руу оруулна уу. Эсвэл Mac терминал дээр "python othello_gui.py" гэж бичнэ үү (мэдээж зөв хавтсанд орсны дараа). Дараа нь самбар таны дэлгэц дээр гарч ирэх ёстой. Энэ горим нь хүн ба хүний горим юм. Гэрэл хоёрдугаарт, эхлээд харанхуй болдог. Хэрэв та эргэлзэж байвал миний видеог үзээрэй. iДээд талд өнгөт хавтан бүрийн оноо байдаг. Тоглохын тулд хүчин төгөлдөр нүүлгэх зайг дарж тэнд плита байрлуулаад дараа нь компьютераа өрсөлдөгчдөө өг, тэр үүнийг давтаж хийнэ.

Хэрэв та Отелло хэрхэн тоглохоо мэдэхгүй байгаа бол эдгээр дүрмийг хэт самбарын вэбсайтаас уншина уу.

Хар үргэлж хамгийн түрүүнд хөдөлдөг. Тоглогчийн өнгөт дискийг самбар дээр байрлуулж, өрсөлдөгчийнхөө нэг буюу хэд хэдэн дискийг "хажуу тийш" байрлуулах замаар алхам хийдэг. Диск эсвэл эгнээний дискийг үзүүрийг нь эсрэг талын өнгөтэй дискээр хүрээлэх үед хажуугийн хажуу талтай байдаг. Диск нь аль ч чиглэлд (хэвтээ, босоо, диагональ) хэд хэдэн дискийг нэг буюу хэд хэдэн эгнээнд байрлуулж болно. (вэбсайтаас уншиж дуусгах)

Анхны тоглоом ба энэ питон тоглоомын хоорондох ялгаа нь нэг тоглогчид хүчинтэй хөдөлгөөн үлдэхгүй бол тоглоом дуусна

Одоо та найзтайгаа тоглоом тоглож болох тул та түүнтэй хамт тоглох боломжтой AI хийцгээе.

Алхам 3: Minimax алгоритм: Хувилбар үүсгэх

Үүнийг кодоор хэрхэн бичих талаар ярихаасаа өмнө түүний логикийг авч үзье. Minimax алгоритм нь шийдвэр гаргах, эргэж харах алгоритм бөгөөд ихэвчлэн хоёр тоглогчийн ээлжээр тоглох тоглоомд ашиглагддаг. Энэхүү хиймэл оюун ухааны зорилго бол дараагийн шилдэг алхам, дараагийн шилдэг алхамыг олох бөгөөд энэ нь тоглоомыг ялах хүртэл болно.

Алгоритм нь аль алхам нь хамгийн сайн алхам болохыг хэрхэн тодорхойлох вэ? Та зогсоод дараагийн алхамаа хэрхэн сонгохоо бодож үзээрэй. Ихэнх хүмүүс хамгийн их оноо өгөх алхамыг сонгох байсан, тийм үү? Эсвэл тэд урьдаас бодож байсан бол тэд илүү оноо авах нөхцөл байдлыг бүрдүүлэх алхамыг сонгох байсан. Сүүлчийн сэтгэлгээний арга бол Минимакс алгоритмын хэрхэн бодох арга юм. Энэ нь ирээдүйн самбарын бүх тохиргоог харж, хамгийн их оноо авах алхамыг хийх болно.

Би үүнийг буцах алгоритм гэж нэрлэсэн, учир нь энэ нь ирээдүйн самбарын бүх төлөв байдлыг холбогдох утгуудаар нь үүсгэж, үнэлэхээс эхэлдэг. Энэ нь алгоритм нь тоглоомын бүх хувилбар тоглох хүртэл тоглоомыг шаардлагатай хэмжээгээр тоглуулах болно гэсэн үг юм. Самбарын бүх төлөв байдлыг (сценарийг) хянахын тулд бид мод зурж болно (зургуудыг харна уу). Дээрх зураг дээрх мод бол Connect 4 тоглоомын энгийн жишээ юм. ТУЗ -ийн бүх тохиргоог самбар төлөв гэж нэрлэдэг бөгөөд мод дээрх байрлалыг зангилаа гэж нэрлэдэг. Модны ёроолд байгаа бүх зангилаа нь бүх хөдөлгөөнийг хийсний дараа самбарын эцсийн төлөв юм. ТУЗ -ийн зарим мужууд нэг тоглогчийн хувьд нөгөөгөөсөө илүү сайн байдаг нь ойлгомжтой. Тиймээс, одоо бид хиймэл оюун ухаанд аль зөвлөлийн мужид очихыг сонгох ёстой.

Алхам 4: Minimax: ТУЗ -ийн тохиргоог үнэлэх

Удирдах зөвлөлд үнэ цэнэ өгөхийн тулд бид тоглож буй тоглоомын стратеги, энэ тохиолдолд Отеллогийн стратегиудыг сурах ёстой. Энэ тоглоом нь өрсөлдөгчийн болон таны дискийг эргүүлэх тулаан тул хамгийн сайн дискний байрлал нь тогтвортой бөгөөд эргүүлэх боломжгүй байдаг. Жишээлбэл, булан нь дискийг байрлуулахдаа өөр өнгөөр сольж болохгүй газар юм. Тиймээс энэ газар маш үнэ цэнэтэй байх болно. Бусад сайн байрлалд олон тооны чулуу авах боломжийг олгодог самбарын хажуу талууд орно. Энэ вэбсайт дээр илүү олон стратеги байдаг.

Одоо бид удирдах зөвлөлийн удирдах зөвлөл бүрийн албан тушаалыг үнэлж болно. Хэрэв хиймэл оюун ухааны хэсэг байр сууриа эзэлсэн бол тухайн байрлалаас хамааран тодорхой тооны оноо өгнө. Жишээлбэл, хиймэл оюун ухааны хэсэг буланд байгаа самбарын төлөвт та 50 онооны урамшуулал өгөх боломжтой боловч хэрэв энэ нь тааламжгүй газар байсан бол тухайн хэсэг нь 0 гэсэн утгатай байж болно. албан тушаал, Та ТУЗ -ийн төлөв үнэ цэнийг оноож. Жишээлбэл, хиймэл оюун ухаан нь буланд байгаа бол самбарын төлөв 50 оноотой байж болно, харин хиймэл оюун ухааны хэсэг дунд байгаа өөр самбар төлөв 10 оноотой байна.

Үүнийг хийх олон арга бий, надад самбарын хэсгүүдийг үнэлэх гурван өөр эвристик бий. Би чамайг өөрийн гэсэн эвристик хэлбэртэй болгохыг зөвлөж байна. Би Puma.py, erika5.py, nathanh.

Алхам 5: Minimax алгоритм: Шилдэг хөдөлгөөнийг сонгох

Хэрэв хиймэл оюун ухаан хамгийн өндөр оноо авсан самбар руу орох бүх алхамыг сонговол сайхан байх болно. Гэхдээ хиймэл оюун ухаан нь самбарын бүх төлөвийг гаргахдаа өрсөлдөгчийнхөө алхамыг сонгож байсныг санаарай, хэрэв өрсөлдөгч ухаалаг бол хиймэл оюун ухааныг хамгийн өндөр оноо авахыг зөвшөөрөхгүй. Үүний оронд ухаалаг өрсөлдөгч хиймэл оюун ухааныг удирдах зөвлөлийн хамгийн доод төлөвт шилжүүлэх алхам хийх болно. Алгоритмд бид хоёр тоглогчийг хамгийн их байлгах тоглогч, багасгах тоглогч гэж нэрлэдэг. AI нь хамгийн их оноо авахыг хүсч байгаа тул хамгийн их тоглогч байх болно. Өрсөлдөгч нь хиймэл оюун ухаан хамгийн бага оноо авах алхам хийхийг оролдож байгаа тул өрсөлдөгч нь багасгах тоглогч байх болно.

Самбарын бүх төлөвийг үүсгэж, утгыг самбар дээр хуваарилсны дараа алгоритм нь самбарын төлөвийг харьцуулж эхэлдэг. Зураг дээр би алгоритм нь түүний хөдөлгөөнийг хэрхэн сонгохыг харуулах модыг бүтээсэн. Салбар дахь хуваагдал бүр нь хиймэл оюун ухаан эсвэл өрсөлдөгчийн тоглох өөр өөр алхам юм. Зангилааны эгнээний зүүн талд би тоглуулагчийг томруулах эсвэл багасгах гэж байгаа эсэхийг бичсэн. Доод эгнээнд самбар дээрх бүх үнэт зүйлсийн жагсаалт байна. Эдгээр зангилаа бүрийн дотор тоонууд байдаг бөгөөд эдгээр нь самбар бүрт оноо өгдөг: тэдгээр нь өндөр байх тусам хиймэл оюун ухаантай байх нь илүү дээр юм.

Тодорхойлолтууд: эцэг эхийн зангилаа - түүний доорх зангилаа үүсгэдэг эсвэл үүсгэдэг зангилаа; хүүхдийн зангилааны гарал үүсэл - нэг эцэг эхийн зангилаанаас үүссэн зангилаа

Хоосон зангилаа нь хиймэл оюун ухааны хамгийн сайн төлөвт хүрэхийн тулд ямар алхам хийхийг харуулдаг. Энэ нь хамгийн зүүн талын зангилааны хүүхдүүдийг харьцуулахаас эхэлнэ: 10, -3, 5. Томруулах тоглогч энэ алхамыг хийх тул түүнд хамгийн их оноо өгөх хөдөлгөөнийг сонгох болно: 10. Тиймээс бид үүнийг сонгоод хадгална. самбарын оноогоор хөдөлж, эцэг эхийн зангилаа дээр бичнэ үү. Одоо 10 нь эцэг эхийн зангилаа дээр байгаа тул одоо тоглогчдыг багасгаж байна. Гэсэн хэдий ч бидний 10 -ыг харьцуулах зангилаа хоосон байгаа тул багасгах тоглуулагч сонгохоос өмнө бид эхлээд энэ зангилааг үнэлэх ёстой. Тиймээс бид тоглогчийн хамгийн их эргэлт рүү буцаж очоод зэргэлдээх зангилааны хүүхдүүдийг харьцуулна уу: 8, -2. Томруулах нь 8 -г сонгох бөгөөд үүнийг хоосон эцэг эхийн зангилаан дээр бичнэ. Одоо алгоритм нь дээрх зангилааны хүүхдүүдийн хоосон зайг бөглөж дууссаны дараа багасгах тоглогч эдгээр хүүхдүүдийг 10 ба 8 -ыг харьцуулж 8 -ийг сонгож болно. Дараа нь алгоритм модыг бүхэлд нь дүүргэх хүртэл энэ үйлдлийг давтана. Энэ жишээний төгсгөлд бид 8 оноо авсан болно. Энэ бол хиймэл оюун ухаан нь өрсөлдөгчөө оновчтой тоглож байгаа гэж таамаглахын тулд тоглох хамгийн өндөр төлөв юм. Тиймээс хиймэл оюун ухаан нь 8 самбарын төлөвт хүргэх эхний алхамыг сонгох бөгөөд хэрэв өрсөлдөгч оновчтой тоглох юм бол хиймэл оюун ухаан 8 -р төлөвт хүрэхийн тулд бүх хөдөлгөөнийг хийх ёстой. (Миний зурган дээрх тэмдэглэлийг дагана уу)

Энэ нь маш их байсан гэдгийг би мэднэ. Хэрэв та ямар нэгэн зүйлийг ойлгохын тулд хэн нэгэнтэй ярилцах шаардлагатай байгаа хүмүүсийн нэг бол энэ санааг ойлгоход туслахын тулд миний үзсэн хэдэн видеог энд оруулав: 1, 2, 3.

Алхам 6: Minimax алгоритм: Псевдокод

Minimax алгоритмын логикийг ойлгосны дараа энэ псевдокод (бүх кодонд түгээмэл байдаг функцууд) -ийг Wikipedia дээрээс үзээрэй.

minimax функц (зангилаа, гүн, maximizingPlayer) юм

Хэрэв гүн = 0 эсвэл зангилаа бол терминал зангилаа юм

зангилааны эвристик утгыг буцаана

if maximizingPlayer бол

утга: = ∞

зангилааны хүүхэд бүрийн хувьд хийдэг

утга: = хамгийн их (утга, хамгийн бага хэмжээ (хүүхэд, гүн - 1, ХУДАЛ))

буцаах утга

өөр (* тоглуулагчийг багасгах *)

утга: = +∞

зангилааны хүүхэд бүрийн хувьд хийдэг

утга: = мин (утга, хамгийн бага хэмжээ (хүүхэд, гүн - 1, ҮНЭН))

буцаах утга

Энэ бол рекурсив функц бөгөөд зогсох цэг хүртэл өөрийгөө дахин дахин дууддаг гэсэн үг юм. Нэгдүгээрт, функц нь зангилаа, гүн, хэний ээлж болох гэсэн гурван утгыг авдаг. Зангилааны утга нь програмыг хайж эхлэхийг хүсч буй газар юм. Гүн нь програмыг хэр хол хайхыг хүсч байгаа явдал юм. Жишээлбэл, миний модны жишээнд энэ нь 3 -ийн гүнтэй байдаг, учир нь энэ нь 3 алхам хийсний дараа самбарын бүх төлөвийг хайсан болно. Мэдээжийн хэрэг, бид хиймэл оюун ухаан нь самбар бүрийн төлөв байдлыг шалгаж, хожлын ялалтыг сонгохыг хүсч байна, гэхдээ хэдэн сая биш, хэдэн мянган самбарын тохиргоо байдаг ихэнх тоглоомд таны гэрийн зөөврийн компьютер эдгээр бүх тохиргоог боловсруулах боломжгүй болно. Тиймээс, бид хиймэл оюун ухааны хайлтын гүнийг хязгаарлаж, самбарын хамгийн сайн төлөвт оруулах болно.

Энэхүү псевдокод нь миний өмнөх хоёр үе шатанд тайлбарласан процессыг хуулбарлаж байна. Одоо үүнийг алхам алхамаар хийж, үүнийг python код дээр зөв болгоё.

Алхам 7: Ai_template.py ашиглан AI хийх

Миний Minimax AI кодыг харахаасаа өмнө ai_template.py файл болон сүүлийн алхам дээр ярьсан хуурамч кодыг ашиглан өөрийн хиймэл оюун ухаан хийхийг оролдож үзээрэй. Ai загварт def minimax_min_node (самбар, өнгө) ба def minimax_max_node (самбар, өнгө) гэсэн хоёр функц байдаг. Minimax функц өөрийгөө рекурсив гэж нэрлэхийн оронд бид бие биенээ дууддаг хоёр өөр функцтэй байдаг. ТУЗ -ийн төлөв байдлыг үнэлэх эвристикийг бий болгохын тулд та өөрийн функцийг бий болгох хэрэгтэй болно. Othello_shared.py файлд хиймэл оюун ухаанаа бүтээхэд ашиглаж болох урьдчилсан функцууд байдаг.

Та хиймэл оюун ухаантай болсныхоо дараа үүнийг ажиллуулж үзээрэй, randy_ai.py. Хоёр ais -ийг бие биенийхээ эсрэг ажиллуулахын тулд mac терминал дээр "python othello_gui.py (ai файлын нэр оруулах).py (файлын нэрийг оруулах).py" гэж бичээд "run othello_gui.py (ai файлын нэр оруулах).py гэж бичнэ үү. (файлын нэрийг оруулна уу).py "гэж бичээд зөв директорт байгаа эсэхээ шалгаарай. Мөн яг ямар алхам хийх талаар миний видеог үзээрэй.

Алхам 8: AI -тэй тэмцэх цаг боллоо

Одоо компьютерийн олон найз нөхөдтэй болж, тэднийг өөрсдийн хиймэл оюун ухааны загвар зохион бүтээгээрэй! Дараа нь та өрсөлдөөн зохиож, хиймэл оюун ухаанаа гаргуулж болно. Та өөрийн хиймэл оюун ухааныг бүтээж чадаагүй байсан ч гэсэн minimax алгоритм хэрхэн ажилладагийг ойлгож чадсан гэж найдаж байна. Хэрэв танд ямар нэгэн асуулт байвал доорхи сэтгэгдлүүд дээр ямар ч асуулт асууж болно.