«Пакман» ўйинини сунъий интеллект фанларида қўлланиш

Мақолада сунъий интеллект фанларини ўқитишда пакман ўйини қўлланиш масаласи қараб чиқилади.

Калит сўзлар: сунъий интеллект, пакман, dfs, bfs.

В статье рассматривается использование игры «Пакман» в уроках по искусственному интеллекту.

Ключевые слова: искусственный интеллект, пакман, dfs, bfs.

Сунъий интеллект соҳаси бу бугунги кундаги энг тез ривожланиб бораётган соҳалардан бири бўлиб ҳисобланади. У инсониятнинг барча жавҳаларига кириб бормоқда. Натижада инсонлар сунъий интеллектни интеллектуал масалаларни ечишда қўлланилиб келмоқда. Шундай экан бу соҳа бўйича етук мутахассисларни тайёрлаш муҳим вазифалардан бирига айланади. Олий таълим муассасаларида сунъий интеллект соҳаси бўйича таълим берилади. Бу фанларни ўқитишда талабаларга сифатли билим бериш учун инструментал қуролларни қўлланиш мақсадга мувофиқ. Ушбу мақола айнан шундай қурол сифатида ҳаммага таниш бўлган Пакман ўйинини сунъий интеллект фанларида қўлланишга бағишланади.

Сунъий интеллект бу интеллектуал машиналарни айниқса интеллектуал комьпютер дастурларини яратиш технологияси бўлиб ҳисобланади. Интеллектуал тизимларнинг хосияти бу инсонга хос ижодий амалларни бажариш бўлиб ҳисобланади [2]. Сунъий интеллект соҳасида интеллектуал агент тушунчаси мавжуд, бу шундай дастур бўлиб, дастурнинг ўзи мустақил равишда фойдаланувчи кўрсатмасига кўра қўйилган топшириқни бажаради. Бундай агентларга берилган графларда манзилга олиб борувчи йўлни мустақил равишда қидириб топишни мисол қилиб олиш мумкин. Яъни агент ўз сенсорлари орқали маълумот олади ва ўзи мустақил равишда қарор қабул қилади. Пакман ўйинида шундай графларда қидириш алгоритмларини қўллаш имконияти мавжуд.

Графларда манзилга элтувчи йўлни топиш масаласи ҳозирги кундаги энг муҳим масалалардан бири бўлиб ҳисобланади. Бундай қидириш усуллари йўлни кўрсатувчи навигаторларда кенг қўлланилиб келмоқда. Сунъий интеллект соҳасида бундай қидириш усулларининг бир қанча турлари мавжуд, масалан, чуқурликга қидириш, энига қидириш, эвристик қидириш, А* кидириш ва бошқа усуллар. Биз ушбу мақолада чуқурликга қидириш ва энига қидириш усулларини қўллашни кўриб чиқамиз.

Чуқурликга қидириш (depth-first search) — бу усулда бутун қидириш жараёни қидириш дарахтининг жорий чўққисидан бошлаб унинг энг чуқур чўқкисига қараб чиқишдан иборат [1]. Яъни қидириш дарахтида биринчи чўққи олинади ва шундан кейин турган чўққига ўтилади. Бу жараён энг охирги чўққигача давом этади. Кейин эса бир қадам орқага қайтиб ёнидаги чўққига ўтилади ва жараён давом этилади. Ҳар бир юришда чўққи манзил чўқки эканлиги текширилиб ва юришлар ёзиб борилади, агар чўққи манзил бўлса қидирув тўхтатилади. Ёзиб борилган манзиллар эса юриш йўли бўлиб ҳисобланади. Қидириш дарахтида манзилга олиб борувчи йўллар бир нечта бўлиши мумкин, бу усул эса фақат улардан бирини аниқлайди холос, лекин энг яқин йулни аниқлай олмайди, бунинг учун бошқа усуллардан фойдаланилади. Энди бу усулни Пакман ўйинида қўллаймиз [3]. Берклидаги Калифорния университети томонидан сунъий интеллектни талабаларга ўргатиш мақсадида очиқ кодли Пакман лойихаси ишлаб чиқилган. Бу дастурда ўйин дастурида қидириш алгоритмини дастурини ёзиш ва натижани текшириб имконияти мавжуд. Ўйин дастур Python дастурлаш тилида ёзилган, дастурни университетнинг сунъий интеллект курси саҳифасидан юклаб олиш мумкин. Қидиришни амалга ошириш учун бизга дастурдаги search.py файли керак бўлади. Бу файлда бир нечта қидириш усулларининг бўш методлар келтирилган. Масалан depthFirstSearch() методи бу чуқурликга қидириш усули учун мўлжалланган. Бизнинг вазифамиз шу метод кодини ёзишдан иборат.

Ўйин лабиринтида бошланғич нуқта ва манзил белгиланган бўлади. Натижани олиш учун depthFirstSearch() методи йўллар кетма-кетлиги кўрсатилган массивни метод натижаси сифатида қайтариши лозим. Масалан, ўнга, чапга, ўнга, ўнга, …. Бошланғич нуқта координатасини аниқлаш учун getStartState() функциясидан фойдаланилади. Белгиланган нуқтадан юриш мумкин бўлган координаталарни аниқлаш учун эса getSuccessors() функциясидан фойдаланилади. Бу функция қайтарадиган қиймат 3 та: координата, йуналиш, кадамлар сони, масалан, (3,4), West, 1. Белгиланган нуқта манзилини текшириш учун isGoalState() функцияси қўлланилади. Қидиришни амалга оширишда маълумотлар структурасидан фойдаланиш мақсадга мувофиқ. Шу сабабли дастурнинг ўзида стек, навбат структуралари амалга оширилган, бу маълумотлар структуралари util.py файлида келтирилган. Демак, биз чуқурликга кидириш усулини қўллашимизда қуйидагича кетма-кетликдан фойдаландик:

– стекнинг биринчи ячейкасига жорий яъни бошланғич нуқта координатаси ёзилади,

– стек бўшагунча давом этувчи цикл эълон қилинади,

– биринчи ячейкадаги маълумотлар ўчирилиб алоҳида ўзгарувчиларга кўчирилади,

– юриш мумкин бўлган йўллар сонигача давом этувчи цикл эълон қилинади,

– хар бир юриш мумкин бўлган нуқта текширилиб чиқилади, яъни, агар жорий нуқта олдин юрилмаган бўлса ва ушбу нуқта манзил нуқта бўлмаса шу нуқта стекга қўшилади ва қидириш давом этади.

– агар манзил нуқта аниқланса натижа қайтарилади ва қидириш тўхтатилади.

Стекнинг ишлаш хосияти бу охирги бўлиб киритилган маълумот биринчи бўлиб стекдан чиқиб кетади, шу сабабли чуқурликга қидириш усулида стекдан фойдаланиш қулай усул бўлиб ҳисобланади. Масалан, бизда қидириш дарахтида иккита А ва Б юриш мумкин бўлган чўққилар мавжуд бўлсин. А ва Б чўққилари текширилади, агар манзил аниқланмаса, энг охирги киритилган Б чўққиси стекдан чиқарилиб шундан кейинги турган чўққилар текширилади ва шу кўринишда қидириш давом эттирилади. Чуқурликга қидириш алгоритмининг дастурдаги коди 1-расмда келтирилган.

1-расм. Чуқурликга кидириш алгоритми Python дастурлаш тилидаги реализацияси

Бу қидириш натижаси яъни юриш лозим бўлган йўллар way стекида ёзилиб борилиб, манзилга етиб борилганда қидириш тўхтатилиб шу стек натижа сифатида қайтарилади. Дастур эса шу йўналиш бўйича юрилади ва натижа баҳоланади. Юришни визуал кўриш имконияти мавжуд бўлиб бунинг учун дастурни махсус қўшимча параметрлар орқали ишга тушириш лозим. Бу ҳақида commands файлида батафсил маълумот келтирилган. Юришларнинг визуал кўриниши 2-расмда келтирилган.

2-расм. Чуқурликга қидириш алгоритми бўйича юришларнинг визуал кўриниши

Энига қидириш (breadth-first search) — бу усул чуқурликга қидириш усулига ўхшаш бўлиб, фарқи шундаки, бунда чуқурликга қидириш усулига қараганда энг яхши натижа қидирилиб топилади. Бу усулда қидириш дарахтида аввал жорий чўққидан юриш мумкин бўлган барча чўққилар кўриб чиқилади, кейин энг четги чўққи олиниб ундан юриш мумкин бўлган барча чўққилар қараб чиқилади ва шу кўринишда манзилга етгунча қидириш давом эттирилади. Бу усулни дастурда амалга ошириш учун breadthFirstSearch() методи ажратилган. Энига қидириш усулини амалга ошириш учун биз юқорида кўрсатилган чуқурликга қидириш алгоритми қўлланилади, фақат стек ўрнига навбатдан фойдаланилади. Навбатнинг стекдан фарқи бу биринчи киритилган маълумот биринчи бўлиб чиқарилади. Масалан, бизда жорий чўққидан иккита А ва Б кейинги чўққи мавжуд бўлсин, иккита чўққи текширилади агар манзил аниқланмаса, биринчи киритилган А чўққи навбатдан чиқарилиб шундан кейинги мавжуд бўлган чўққилар текширилади. Агар манзил аниқланмаса, демак, Б чўққига ўтилади ва қидириш давом эттирилади.

Дастурда навбатни қўллаш учун Queue маълумотлар структураси ишлатилади, дастурнинг коди 3-расмда кўрсатилган.

3-расм. Энига қидириш алгоритмининг Python дастурлаш тилидаги реализацияси

Пакман лойиҳасида натижаларни текшириш учун уч хил лабиринт(tinyMaze, mediumMaze, bigMaze) келтирилган, улар бир-бири билан ўлчами билан фарқ қилади. Иккита қидириш усули натижаларини солиштириб кўрилгандаги олинган натижалар 1-жадвалда келтирилган.

1 Жадвал

MediumMaze яъни ўртача хажмдаги лабиринтдаги натижалар

Натижадан кўриниб турибдики, энига қидириш усули чуқурликга қидириш усулига қараганда кўпроқ чўққиларни қараб чиқиш эвазига энг қисқа масофани қидириб топади.

1. Стюарт Рассел, Питер Норвиг. Искусственный интеллект: современный подход / Artificial Intelligence: A Modern Approach. — 2-е изд. — М.: «Вильямс», 2007.
2. Аверкин А. Н., Гаазе-Рапопорт М. Г., Поспелов Д. А. Толковый словарь по искусственному интеллекту. — М.:Радио и связь, 1992.
3. The Pac-Man Projects. Berkeley AI Materials:. — URL: http://ai.berkeley.edu/project_overview.html (дата обращения: 31.05.2020).