Такта оюну Жасалма интеллект: Minimax алгоритми: 8 кадам

2024 Автор: John Day | [email protected]. Акыркы өзгөртүү: 2024-01-30 10:40

Шахмат же шашки боюнча ойногон компьютерлер кантип жасалат деп ойлонуп көрдүңүз беле? Бул Нускамадан ары караңыз, анткени ал Minimax Алгоритмин колдонуу менен жөнөкөй, бирок эффективдүү жасалма интеллектти (AI) кантип жасоону көрсөтөт! Minimax алгоритмин колдонуу менен, AI жакшы пландалган жана ойлонулган кыймылдарды жасайт (же жок дегенде ой процессин туурайт). Эми мен сизге AI жасаган кодду бере алам, бирок бул кызыктуу болбойт. Мен компьютердин тандоосунун логикасын түшүндүрөм.

Бул Нускамада мен сизге питондогу Отелло (АКА Реверси) үчүн AI кантип жасоо боюнча кадамдарды айтып берем. Бул долбоорду чечүүдөн мурун, сиз pythonдо кантип кодировка кылууну орто деңгээлде түшүнүшүңүз керек. Мына ушул бир нече жакшы веб -сайттар, бул Нускамага даярдануу үчүн: w3schools же learnpython. Бул Нускаманын аягында, сизде эсептелген кыймылдарды жасай турган AI болушу керек жана адамдардын көбүн жеңе алышы керек.

Бул Нускамада биринчи кезекте AIди кантип жасоо керек экендиги айтылгандыктан, мен оюнду питондо кантип жасоону түшүндүрбөйм. Анын ордуна, мен адам башка адамга каршы ойной турган оюндун кодун берем жана аны адам AIге каршы ойногон оюнду ойной алгыдай кылып өзгөртөм.

Колумбия SHAPEдеги жайкы программа аркылуу бул AIди кантип жасоону үйрөндүм. Мен ал жерде жакшы убакыт өткөрдүм, андыктан алардын веб -сайтын карап көрүңүз, эгер сизди кызыктырбаса.

Эми логистиканы жолго койгондон кийин, коддоону баштайлы!

(Мен сүрөттөргө бир нече жазууларды койгом, аларды карап көрүңүз)

Жабдуулар

Бул оңой:

1) Spyder же IDLE сыяктуу питон чөйрөсү бар компьютер

2) Отелло оюнунун файлдарын менин GitHubдан жүктөп алыңыз

3) Сабырдуулук менен мээңиз орнотулган

1 -кадам: Керектүү файлдарды жүктөп алыңыз

Менин GitHubга киргенде, сиз 5 файлды көрүшүңүз керек. Баарын жүктөп алып, бардыгын бир папкага салыңыз. Оюнду иштетүүдөн мурун, бардык файлдарды spyder чөйрөсүндө ачыңыз.

Бул жерде файлдар эмне кылат:

1) othello_gui.py бул файл оюнчулар үчүн ойноочу тактаны түзөт (адам болобу же компьютер болобу)

2) othello_game.py бул файл оюн тактасы жок эки компьютерди бири -бирине каршы ойнойт жана бир гана упайларды көрсөтүп, позицияларын жылдырат

3) ai_template.py бул жерде сиз AIди жасоо үчүн бардык кодуңузду коёсуз

4) randy_ai.py бул кокусунан кыймылын тандай турган алдын ала даярдалган AI

5) othello_shared.py, сиз интеллектуалдык интеллектуалдык системаңызды жеткиликтүү кыймылдарды, упайларды же такталардын абалын текшерүү үчүн колдоно турган көптөгөн функцияларды.

6) Башка үч файл: Puma.py, erika_5.py жана nathan.py, мен, Эрика жана Натан тарабынан SHAPE программасынан жасалган, бул уникалдуу коддору бар үч башка AI

2 -кадам: Python Отеллону кантип ачуу жана ойноо

Бардык файлдар ачылгандан кийин, экрандын оң жак бурчуна "run othello_gui.py" деп териңиз жана IPython Console'го киргизиңиз. Же Mac терминалында "python othello_gui.py" деп териңиз (албетте туура папкада болгондон кийин). Андан кийин экраныңызда такта пайда болушу керек. Бул режим адамдык жана адамдык режим. Жарык экинчи, караңгы биринчи кетет. Эгер түшүнбөй жатсаңыз менин видеомду караңыз. iAt үстүндө, ар бир түстүү плитканын эсеби бар. Оюн ойноо үчүн, жарактуу орунду чыкылдатып, плитканы ошол жерге коюңуз, анан компьютерди атаандашыңызга бериңиз, ал ошону кылат жана кайталайт.

Эгерде сиз Отеллону кантип ойногонду билбесеңиз, бул эрежелерди ультра такталар сайтынан окуңуз:

Кара дайыма биринчи кыймылга келет. Кыймыл оюнчунун түсү дисктин доскага бир же бир нече дисктерин "сыртка караткан" абалда коюу аркылуу жасалат. Диск же катар дисктер анын учунда карама -каршы түстөгү дисктер менен курчалганда сыртка чыгып кетет. Диск каалаган багытта (горизонталдуу, вертикалдуу, диагоналдуу) бир же бир нече катардагы дисктердин санынан ашып кетиши мүмкүн. (алардын веб -сайтында окуп бүтүрүү)

Түпнуска оюндун бул питон оюнунан айырмасы, бир оюнчу үчүн жарактуу кыймылдар калбай калганда, оюн бүтөт

Эми сиз оюнду досуңуз менен ойной аласыз, келиңиз, сиз ойной турган AI жасайбыз.

3 -кадам: Minimax Алгоритм: Сценарийлерди түзүү

Муну коддо кантип жазуу жөнүндө сүйлөшүүдөн мурун, анын артындагы логиканы карап көрөлү. Minimax алгоритми-бул чечим кабыл алуу, артка көз салуу алгоритми жана адатта эки оюнчуга, кезекке негизделген оюндарда колдонулат. Бул AIнын максаты - бул оюнду утуп алганга чейин кийинки эң мыкты кадамды жана кийинки эң мыкты кыймылдарды табуу.

Эми алгоритм кайсы кыймыл эң жакшы кадам экенин кантип аныктайт? Токтоп, кийинки кадамды кантип тандайм деп ойлон. Көпчүлүк адамдар эң көп упай бере турган кадамды тандайт, туурабы? Же алар алдын ала ойлонушса, алар андан да көп упай топтой турган кырдаалды түзө турган кадамды тандашмак. Акыркы ой жүгүртүү ыкмасы - бул Minimax Алгоритминин кандай ой жүгүртүүсү. Бул келечектеги тактайдын бардык түзүлүштөрүн карап турат жана эң көп упайга алып келе турган кадамды жасайт.

Мен муну артка кайтуу алгоритми деп атадым, анткени ал келечектеги башкармалыктын бардык мамлекеттерин байланышкан баалуулуктары менен түзүүдөн жана баалоодон башталат. Бул алгоритм оюндун ар бир сценарийи ойногонго чейин оюнду канча керек болсо, ошончо ойной турганын (өзү жана каршылашы үчүн кыймылдарды жасоо) билдирет. Тактадагы бардык абалдарды (сценарийлерди) көзөмөлдөө үчүн, биз дарак чийе алабыз (сүрөттөрдү караңыз). Жогорудагы сүрөттөгү дарак Connect 4 оюнунун жөнөкөй мисалы. Ар бир тактанын конфигурациясы тактанын абалы деп аталат жана анын дарактагы орду түйүн деп аталат. Дарактын түбүндөгү бардык түйүндөр бардык кадамдарды жасагандан кийинки акыркы такталар. Албетте, кээ бир такталар штаттары бир оюнчу үчүн экинчисине караганда жакшыраак. Ошентип, азыр биз AIге кайсы штатка жетүүнү каалаганын тандашыбыз керек.

4 -кадам: Minimax: Board Configurations баалоо

Башкаруу штаттарына баалуулуктарды берүү үчүн, биз ойногон оюндун стратегиясын үйрөнүшүбүз керек: бул учурда Отеллонун стратегиялары. Бул оюн атаандашыңыздын жана сиздин дисктериңизди оодарып салгылашуу болгондуктан, дисктердин эң жакшы позициясы - бул туруктуу жана аларды оодарууга болбойт. Бурч, мисалы, дисктин башка түскө өзгөртүлбөгөн жери. Ошентип, бул жер абдан баалуу болмок. Башка жакшы позицияларга көп таштарды алууга мүмкүндүк бере турган тактайдын капталдары кирет. Бул веб -сайтта дагы стратегиялар бар.

Эми биз ар бир коллегиянын штаттык коллегиясынын позициясына баалуулуктарды дайындай алабыз. Качан бир позиция AIдин бөлүгүн ээлесе, анда сиз позицияга жараша белгилүү бир упай бересиз. Мисалы, AIтин бөлүгү бурчта турган такта мамлекети, сиз 50 упай бонус бере аласыз, бирок эгер ал жагымсыз жерде болсо, анда бөлүк 0 мааниге ээ болушу мүмкүн. позицияларды, сиз коллегиянын абалына баа бересиз. Мисалы, эгер AI бурчта бир кесимге ээ болсо, тактанын абалы 50 баллга ээ болушу мүмкүн, ал эми AIнин бөлүгү ортосунда башка тактайдын абалы 10 баллга ээ.

Муну жасоонун көптөгөн жолдору бар, менде тактанын бөлүктөрүн баалоо үчүн үч башка эвристика бар. Мен сизди өзүңүздүн эвристикалык түрүңүздү жасоого чакырам. Гитубума үч башка эвристика менен үч башка AIди жүктөдүм: Puma.py, erika5.py, nathanh.py.

5 -кадам: Minimax алгоритми: Мыкты кыймылды тандоо

Эми 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 Алгоритм: Псевдокод

Minimax алгоритминин логикасын түшүнгөндөн кийин, википедиядан бул псевдокодду (бардык коддорго универсалдуу болгон функцияларды) карап көрүңүз:

minimax функциясы (түйүн, тереңдик, maximizingPlayer)

эгер тереңдик = 0 же түйүн терминалдык түйүн болсо

түйүндүн эвристикалык маанисин кайтаруу

анда maximizingPlayer

мааниси: = -∞

түйүндүн ар бир баласы үчүн

маани: = максимум (балл, минимакс (бала, тереңдик - 1, ЖАЛГАН))

кайтаруу мааниси

башка (* оюнчуну азайтуу *)

мааниси: = +∞

түйүндүн ар бир баласы үчүн

маани: = мин (маани, минимум (бала, тереңдик - 1, ЧЫН)

кайтаруу мааниси

Бул рекурсивдүү функция, башкача айтканда, ал өзүн токтоочу жерге жеткенге чейин кайра -кайра чакырат. Биринчиден, функция үч маанини алат, түйүн, тереңдик жана кимдин кезеги. Түйүндүн мааниси - бул программанын издөөнү каалаган жери. Тереңдик - бул программанын канчалык алыс издөө керектиги. Мисалы, менин дарактын мисалында ал 3 тереңдикке ээ, анткени ал 3 тактадан кийин бардык такталардын абалын издеген. Албетте, биз AIдин ар бир штаттын абалын текшерип, утушту тандап алышын каалайбыз, бирок миллиондогон такталар конфигурациялары бар көпчүлүк оюндарда сиздин үйдөгү ноутбугуңуз бул конфигурациялардын бардыгын иштете албайт. Ошентип, биз AIнын издөө тереңдигин чектеп, аны эң жакшы такта абалына жеткиребиз.

Бул псевдокод мен мурунку эки кадамда түшүндүргөн процессти кайталап жатат. Эми муну дагы бир кадам жасайлы жана муну python кодунда оңдойлу.

7 -кадам: AIди Ai_template.py менен жасоо

Менин Minimax AI кодумду карап көрүүдөн мурун, ai_template.py файлы жана акыркы кадамда биз айткан псевдо-код менен өзүңүздүн AIди жасоого аракет кылыңыз. Ай шаблондо эки функция бар: def minimax_min_node (такта, түс) жана def minimax_max_node (такта, түс). Минимакс функциясы өзүн рекурсивдүү деп атоонун ордуна, бизде бири -бирин чакырган эки башка функция бар. Такта абалын баалоо үчүн эвристикти түзүү үчүн, сиз өзүңүздүн функцияны түзүшүңүз керек болот. Othello_shared.py файлында интеллектуалдык интеллектти куруу үчүн колдоно турган алдын ала даярдалган функциялар бар.

AIге ээ болгондон кийин, ага каршы иштетип көрүңүз, randy_ai.py. Эки AISти бири -бирине каршы иштетүү үчүн, Mac терминалына "python othello_gui.py (ai файлдын атын киргизиңиз).py (файлдын атын киргизиңиз).py" териңиз же "run othello_gui.py (ai файлдын атын киргизиңиз).py" териңиз. (файлдын атын киргизиңиз).py "жана туура каталогдо экениңизди текшериңиз. Ошондой эле, так кадамдар үчүн менин видеомду караңыз.

8 -кадам: AI менен күрөшүүгө убакыт келди

Эми компьютериңиздин көптөгөн досторун таап, аларды өздөрүнүн AI дизайнын түзүңүз! Андан кийин сиз атаандаштык түзүп, интеллектуалдык оюңузду чыгарсаңыз болот. Балким, эгер сиз өзүңүздүн интеллектуалдык оюңузду кура албасаңыз да, сиз minimax алгоритми кандай иштээрин түшүнө алдыңыз. Эгерде сизде кандайдыр бир суроолор болсо, төмөндөгү комментарийлерде кандайдыр бир суроолорду жазуудан тартынбаңыз.