WikiDer > Kompyuter Arimaa
![]() | Ushbu maqolada bir nechta muammolar mavjud. Iltimos yordam bering uni yaxshilang yoki ushbu masalalarni muhokama qiling munozara sahifasi. (Ushbu shablon xabarlarini qanday va qachon olib tashlashni bilib oling) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)
|
Kompyuter Arimaa ning o'ynashiga ishora qiladi o'yin Arimaa tomonidan kompyuter dasturlari.
2002 yilda hindistonlik amerikalik kompyuter muhandisi Omar Syed Arimaa-ga qoidalarni e'lon qildi va har uchta eng yaxshi dasturni mag'lub etishga qodir bo'lgan birinchi kompyuter dasturi (standart, ishlab chiqarilgan qurilmalar uchun) 2020 yilgacha har yili taqdim etiladigan $ 10,000 mukofotini e'lon qildi. uch o'yindan iborat seriyadagi inson o'yinchilari.[1] Sovrinni 2015-yilda, uchta inson o'yinchisiga qarshi kompyuter dasturi 7: 2 hisobida o'ynaganida olishgan.[2] O'yin bir nechta mavzularga aylandi tadqiqot ishlari.
Arimaa davlat maydoni
Ochilish
O'yin boshida har bir o'yinchi o'z qismlarini o'rnatishi mumkin bo'lgan turli xil usullar soni:
O'yinchi 16 ta kvadratga 8 ta quyon qo'yishi mumkin, so'ngra qolgan 8 ta maydonga 2 ta mushuk, 6 ta qolgan kvadratga 2 ta it, qolgan to'rtta kvadratga 2 ta ot, qolgan ikkita kvadratchadan biriga bitta tuya va fil qo'yishi mumkin. oxirgi foydalanilmagan maydonda.
Har bir o'yinchi o'yinni 64,864,800 ochilish sozlamalaridan biri bilan boshlashi mumkinligi sababli, ochilish uchun umumiy holat maydoni:
Magistrlik dissertatsiyasida Krist-Yan Koks aytganidek, mumkin bo'lgan boshlang'ich holatlar soni juda ko'p bo'lganligi sababli, "[ochilish harakatlarining to'liq ma'lumotlar bazalarini yaratish juda qiyin".[3]
Sun'iy intellekt texnikasi
Materiallarni baholash
Kompyuter uchun doskadagi buyumlarning qiymatini baholash imkoniyati bo'lishi kerak, shunda u qo'lga olish yoki almashinish maqsadga muvofiqligini yoki yo'qligini baholay oladi. Parchalarning nisbiy qiymatini baholash - bu Arimaa tadqiqotining doimiy yo'nalishi. Hozirda ishlatiladigan ba'zi tizimlar DAPE va FAME.
Arimaa botlarida ishlatiladigan usullar
Arimaa o'ynaydigan sun'iy intellekt dasturlarining bir qismi yoki barchasi quyidagi usullardan foydalanadi:
- Bitboardlar
- Transpozitsiya jadvallari
- Zobristni xeshlash
- Minimaks va Alfa beta Azizillo
- Qotil harakat qiladi va rad etish jadvallari
- Statik baholash funktsiyasi
- Tinchlikni qidirish
- Monte-Karlo daraxtlarini qidirish
- UCT
Arimaa botlarida kamdan kam qo'llaniladigan usullar
Kompyuterning ishlashi
Ushbu bo'lim uchun qo'shimcha iqtiboslar kerak tekshirish. (2010 yil mart) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) |
Arimaa-ning bir nechta jihatlari kompyuter dasturlari yaxshi inson o'yinchilarini engishni qiyinlashtiradi. Chunki kuchlilarni rivojlantirish uchun juda ko'p kuch sarflandi shaxmat o'ynash dasturi, nima uchun Arimaa uchun shaxmat uchun qo'llaniladigan texnikaning samarasi pastligini tushunish juda muhimdir.
Qo'pol kuch bilan qidirish
An'anaviy shaxmat dasturlari foydalanish qo'pol kuch bilan qidirish moddiy mulohazalar ustun bo'lgan statik pozitsiyani baholash bilan birgalikda. Ular juda ko'p mumkin bo'lgan harakatlarni ko'rib chiqadilar, lekin ular bir qatorda boshqa tomonga qaraganda ko'proq bo'laklarga ega bo'lmaguncha, ketma-ket harakatlar oxirida kim g'olib chiqishini aniqlashda yaxshi emas (odamlar bilan taqqoslaganda). Xuddi shu narsa Arimaa dasturlari uchun ham amal qiladi, ammo ularning natijalari amalda unchalik yaxshi emas.
Arimaa-ga qo'pollik bilan qidirish qo'llanilganda, qidiruv chuqurligi har bir o'yinchi har bir burilishda juda ko'p imkoniyatlar bilan cheklanadi. Hisoblash jihatidan o'yinchi uchun mavjud bo'lgan variantlar soni o'ynashning turli yo'llarini kamaytiradi. Bu sifatida tanilgan dallanma omili. Shaxmat o'yinidagi o'rtacha dallanma faktori 35 ga teng,[4] Arimaada esa 17000 ga yaqin.[5]
Ushbu turli xil dallanuvchi omillar shuni anglatadiki, shaxmatda har bir o'yinchi uchun sakkiz burilish chuqurligini qidira oladigan kompyuter Arimaadagi har bir o'yinchi uchun atigi uch burilish chuqurligini qidirishi mumkin:
Alfa-beta bilan kesish
Shaxmat dasturlari uchun qo'pol kuch qidirish chuqurligi deyarli ikki baravarga oshadi alfa-beta Azizillo, bu dasturiy ta'minot kuchsiz harakatning har qanday davomini o'rganmasdan turib, bir harakat boshqasidan yaxshiroq degan xulosaga kelish imkonini beradi. Agar raqib ma'lum bir harakatni bitta javob bilan ezib tashlasa, boshqa javoblarni tekshirish shart emas, bu esa qidiruv tezligini keskin oshiradi. Biroq, Arimaada harakatlanish tomoni har to'rt qadamda bir marta aylanadi, bu esa bosqichma-bosqich qidirishda mavjud bo'lgan uzilishlar sonini kamaytiradi.
Bundan tashqari, alfa-beta qirqishning foydaliligi harakatlarni ko'rib chiqish tartibiga juda bog'liq. Yomonlarni e'tiborsiz qoldirish uchun yaxshi harakatlar yomon harakatlardan oldin ko'rib chiqilishi kerak. Xususan, harakatlarni tekshirish va ushlash Azizillo uchun kalit hisoblanadi, chunki ular ko'pincha boshqa harakatlarga qaraganda ancha yaxshi. Arimaa dasturida alfa-beta bilan kesish tezligi kamroq, chunki suratga olish juda kam. Arimaa.com saytida o'ynaladigan baholangan o'yinlarda faqatgina 3% qadamlar qo'lga kiritishga olib keladi, aksincha shaxmat harakatlarining taxminan 19% ushlashga olib keladi.
Ko'pgina Arimaa pozitsiyalarida, ayniqsa, o'yin boshida, taxta hali ham gavjum bo'lgan paytda, vakolatli o'yinchi keyingi ikki burilish davomida hech qanday buyumni yo'qotishdan saqlanishi mumkin. Arimaa shaxmat bilan taqqoslaganda, har qanday o'yinchiga suratga olishni uzoqroq kechiktirishga imkon beradi. Darhaqiqat, shaxmatda birinchi qo'lga kiritishning o'rtacha harakatlanish raqami 6-chi, Arimaada esa 12-chi. Bu kurash dastlab Arimaada ko'proq pozitsiyali bo'lib, kelajakda biron bir nuqtada qo'lga kiritishni muqarrar qilib qo'yadi. Bu moddiy bo'lmagan yo'llar bilan kim yutib borayotganini to'g'ri baholash muhimligini oshiradi. Shunday qilib, kompyuter dasturlarining kuchliligi (millionlab pozitsiyalarni o'rganish) ularning kuchsizligi kabi muhim emas (pozitsiyani kimning ko'pligi borligidan tashqari).
Dastlabki bosqichlarda Arimaa dasturlarining kuchsizligi, sozlash bosqichida yanada kuchayadi. Shaxmatda har bir o'yin bir xil pozitsiyadan boshlanadi. O'yin oldidan barcha standart ochilish harakatlariga zaxiralarning javoblari ro'yxatini tuzib, shaxmat dasturlari "o'ylashni" boshlashdan oldin ko'pincha o'nlab yoki undan ko'p ajoyib harakatlarni amalga oshirishi mumkin. Odamlar xuddi shunday qilishadi, lekin teshiklarni kichikroq va ishonchli xotiraga ega, bu esa odamlarni shaxmatda nisbatan yomon ahvolga solib qo'yadi. Arimaa, aksincha, birinchi qism harakatlanishidan oldin ham qismlarni o'rnatish uchun millionlab usullarga ega. Bu dasturlarning mazmunli ochilish kitobiga ega bo'lishiga yo'l qo'ymaydi.
O'yin davom etar ekan, almashinuvlar va quyonlarning rivojlanishi pozitsiyani yanada ochiq va taktikaga aylantiradi. Arimaa dasturlari odatda bunday pozitsiyada yaxshiroq o'ynaydi, chunki ular taktik kadrlarni odamlar e'tiborsiz qoldiradilar. Biroq, odatda, odamlar konservativ o'yinlar bilan keng pozitsiyalardan qochishlari va kompyuterlar yomonroq bo'lgan strategik pozitsiyalarni tanlashlari mumkin. Konservativ raqibga qarshi Arimaadagi pozitsiyani ochish deyarli mumkin emas, shaxmatda bu shunchaki qiyin. Himoya o'yinlarini dasturlar unchalik yaxshi bo'lmagan kichik, uzoq muddatli afzalliklarni to'plash orqali engish kerak.
Arimaaga taalluqli bo'lmagan qo'shimcha kompyuter shaxmat usullaridan biri so'nggi o'yin stollari. Magistr darajasidagi shaxmat o'yinlari ba'zida bir nechta bo'laklardan iborat noaniq so'nggi o'yinlarga aylanadi, masalan qirol va ritsar, qirol va rouk. Tomonidan qurish mumkin retrograd tahlil, ushbu holatlarning barchasida to'g'ri harakatlarning to'liq jadvali. Dasturlarda yangitdan "o'ylash" o'rniga, oldindan yaratilgan jadval bilan maslahatlashish kerak, bu ularga nisbatan odamlarga nisbatan ustunlik beradi. Arimaa, aksincha, kamdan-kam hollarda so'nggi o'yinlarga duch keladi. Shaxmat bilan taqqoslaganda buyumlarning teng almashinuvi kamroq uchraydi, shuning uchun Arimaa o'yinida "savdo-sotiq qilish" kamdan-kam uchraydi va hanuzgacha noaniq. O'rtacha Arimaa o'yinida atigi sakkizta o'yin bor (shaxmat bo'yicha o'n etti), va eng yaxshi odamlar ko'pincha Arimaa-dagi eng yaxshi dasturlarni biron bir parchani yo'qotmasdan mag'lub qilishlari mumkin. 2014 yilgi Challenge uchrashuvining ikkinchi o'yini. Kam tortishish zichligining yana bir misoli 2012 yilgi jahon chempionatining ushbu yarim final o'yini, faqat bitta qo'lga olish, maqsadli fil qurbonligi bilan.
Omar Syed umid qiladi, chunki an'anaviy sun'iy intellekt texnikasi Arimaa uchun o'rtacha darajada samarali bo'ladi, dasturchilar kuchli Arimaa-o'yin dasturini yaratish uchun yangi sun'iy intellekt usullaridan foydalanishga majbur bo'lishadi. Jahon chempionati-kalibrli shaxmat dasturini yaratish bo'yicha muvaffaqiyatli izlanishlar muvaffaqiyatli o'yin o'ynash uchun ko'plab usullarni yaratdi, ammo umuman umumiy fikrlashga hech narsa yordam bermadi; aslida, ba'zi bir ta'riflardan shaxmat o'ynash dasturlarining texnikasi chiqarib tashlangan sun'iy intellekt; Arimaa uchun maqsad shundaki, uni o'ynash texnikasi sun'iy intellektning katta maqsadlariga yordam beradi.
Syedning mashinaga qarshi kurashidagi tuzilmasi AI dasturiy ta'minotidagi yutuqlarni mukofotlashga qaratilgan bo'lib, apparatdagi yutuqlarga emas. Yillik chaqiriqda dasturlar Syed o'zi tanlagan va taqdim etgan mashinalarda, odatiy, arzon va tayyor uy kompyuterlari mezoniga muvofiq amalga oshiriladi. Qiymat ko'p protsessorli mashinalarni talab qiladigan, masalan, yuqori darajadagi shaxmatchilarga qarshi kurashda ishlatiladigan mashinalar talab qilinadigan har kim uchun ochiq bo'lmasligi mumkin, bu juda kam narsa - bu maxsus tayyorlangan superkompyuter kabi. Moviy moviyArimaa ixtirosini ilhomlantirgan ushbu apparat talab qiladigan yondashuvning muvaffaqiyati bo'lsa ham. Syedning fikricha, hatto 2004 yilgi chaqiriqlar o'yinida foydalanilgan kompyuter (Pentium 4 2,4 gigagertsli tizim, 512 Mb operativ xotiraga ega), agar u faqat tegishli dasturiy ta'minot bilan ishlayotgan bo'lsa, unda sovrinni yutib olish uchun etarli qo'shimcha qurilmalar mavjud. Superkompyuterlar allaqachon Arimaa-ni odatiy sun'iy intellektli dasturiy ta'minot yordamida qo'pol kuch bilan zabt etish qobiliyatiga ega bo'lishlari mumkin edi, va agar qo'shimcha qurilmalar hozirgi tezlikda rivojlanib boraversa, oxir-oqibat shaxsiy kompyuterlar ham shunday bo'ladi. Shuning uchun Arimaa chaqiruv mukofoti dastlab faqat 2020 yilgacha taqdim etilgan.
Arimaa Challenge-ni shaxmat muammolari bilan taqqoslash
![]() | Ushbu bo'lim ehtimol o'z ichiga oladi original tadqiqotlar. (2015 yil aprel) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) |
Ushbu bo'lim emas keltirish har qanday manbalar. (2015 yil aprel) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) |
Arimaa Challenge-da kompyuter shaxmat bo'yicha jahon chempionini mag'lub etdi, ammo insonni mag'lub etmadi (2015 yilgacha) olti sabab bilan:
- Arimaa - bu yangi o'yin. Shuning uchun Arimaa kompyuteriga ajratilgan dasturchilar soni va vaqti kompyuter shaxmatiga qaraganda ancha kam. Kompyuter shaxmatida Arimaa kompyuteriga qaraganda minglab dasturchilar va 40 yil ko'proq bo'lgan. Keyinchalik va kichikroq harakat kompyuter Arimaa-da kamroq va sekinroq rivojlanishga olib keldi.
- Arimaa Challenge qoidalari kompyuterdan shaxmat o'yinlari qoidalariga qaraganda yuqori o'ynash qobiliyatini ko'rsatishni talab qildi. Arimaa Challenge-da kompyuter uchta o'yinda uchta inson o'yinchisini mag'lub qilishi kerak. Shaxmat o'yinlarida kompyuter bitta odam o'yinchisiga qarshi bitta o'yinda g'alaba qozonishi kerak.
- Arimaa Challenge-da g'olib bo'lish uchun kompyuter jami ochkolarning 2/3 qismini to'plashi kerak. Shaxmat o'yinlarida kompyuter g'alaba qozonish uchun jami ochkolarning 1/2 qismidan ko'pini to'plashi kerak.
- Arimaa Challenge-da kompyuter saralash o'yinida g'alaba qozonishi kerak. Odamlarga kompyuterning zaif tomonlarini topish uchun kompyuterning avvalgi o'yinlarini o'rganishga ruxsat beriladi. Shaxmatda saralash o'yinlari mavjud emas va kompyuterning avvalgi o'yinlari jamoatchilikka ochiq bo'lishi shart emas.[shubhali ]
- Arimaa Challenge-da, o'yinlar o'rtasida kompyuterni takomillashtirish mumkin emas. Shaxmatda o'yinlar o'rtasida kompyuter takomillashtirildi.
- Arimaa Challenge-da qoidalar 1000 dollardan yuqori bo'lgan kuchli yoki buyurtma asosida ishlab chiqarilgan kompyuterlarni rad etadi. Biroq, kuchli buyurtma asosida ishlab chiqarilgan kompyuter shaxmat bo'yicha jahon chempionini mag'lub etdi.
Biroq, Arimaa jamoatchiligi ushbu dalilni har bir nuqtada tortishmoqda. Birinchi nuqtada, Arimaa - bu yangi o'yin, shuning uchun o'yin jamoatchiligi hali ham kichik va hatto eng yaxshi o'yinchilar ham professional futbolchilar emas va bu o'yinni bir necha yil davomida o'ynashgan. Shunday qilib, Arimaa Challenge-dagi odam o'yinchilari shaxmat bo'yicha odamlarning o'yinlariga qaraganda ancha zaifroq. Inson o'yinchilarining zaifligi Arimaa Challenge-ni zabt etishni shaxmatga qaraganda osonlashtirishi kerak, bu esa ishlab chiquvchilarga muammoni qisqa vaqt ichida o'rganganliklari uchun kompensatsiya beradi.
Qolgan beshta nuqta Arimaa Challenge-ni faqat Kasparov va Deep Blue bilan taqqoslaydi, chunki kompyuterlar ustun bo'lgan boshqa barcha odamlarga qarshi mashinalar va shaxmat o'yinlari. Arimaa Challenge uchrashuvi bilan taqqoslash mumkin bo'lgan shaxmat musobaqasi Man vs Machine World Team Chempionati. 2004 va 2005 yillarda bir guruh odamlar kompyuter raqiblari jamoasiga qarshi o'ynashdi. Ikki yilda ham kompyuterlar katta farq bilan g'alaba qozonishdi. 2005 yilda uchala odam ham yutqazdi, kompyuterlar jami ochkolarning 2/3 qismini qo'lga kiritdi, shaxmat dvigatellari odamlarning o'rganishi uchun tijorat sifatida mavjud edi va ishlatilgan dastgohlar superkompyuter emas, aksincha Arimaa Challenge-da ishlatiladigan uskunalar bilan taqqoslanadi. .
2005 yildan beri shaxmat-shashka o'yinlarida kompyuterlar tobora kuchayib borayotganligini ko'rsatmoqda. Masalan, 2006 yil Deep Fritz va Vladimir Kramnik va 2007 yil Rybka va Yaan Ehlvest o'yinlari inson o'yinchisiga qo'shimcha afzalliklarni berdi, ammo baribir kompyuterlar (tovar uskunasida ishlaydigan) ustunlik qildi.
Dastur ishlab chiquvchilar uchun manbalar
The Arimaa dvigatel interfeysiBrayan Xaskin tomonidan ishlab chiqilgan bo'lib, Arimaa dvigatelining boshqaruvchi bilan aloqa qilishiga imkon beradigan protokolni belgilaydi.
Hujjatlarga ko'ra: "Dvigatel bu Arimaa o'yinining holatini olish va qonuniy harakatni tanlashga qodir dasturdir. Nazoratchi - bu dvigatel bilan aloqa qilishni va boshqarishni istagan har qanday narsa. Bu oddiy skriptdan boshqa narsa bo'lishi mumkin. Dvigatelda GUI dasturining bitta pozitsiyasini tahlil qilishni, bu o'yinni odamlar yoki boshqa dvigatellar bilan o'ynashga imkon beradi. "[6]
Arimaa Engine interfeysi dvigatelni boshqarish va protokolni, hujjatlarni va turli xil skriptlarni o'z ichiga oladi, bu protokolni qo'llab-quvvatlaydigan har qanday veb-saytda, shu jumladan rasmiy Arimaa veb-saytida o'yin o'ynash.[7][8]
Ilmiy ishlar
- Vu, Devid J. (2015). "Arimaa-ning yutuqli dasturini loyihalashtirish" (PDF). ICGA jurnali. 38 (1): 19–40. doi:10.3233 / ICG-2015-38104.
- Arimaa challenge - alfa-beta usullariga nisbatan MCTS-ni taqqoslash o'rganish
Tomas Yakl tomonidan tezis (Charlz universiteti, Praga) 2011 yil oktyabr - Arimaa o'yinidagi reyting va baholarni siljiting
Devid Jian Vu tomonidan dissertatsiya (Garvard kolleji, Kembrij, Massachusets shtati, AQSh) 2011 yil may - Arimaa, sun'iy intellekt uchun yangi choralar
Stefano Karlini tomonidan tezis (Modena universiteti va Regjio Emiliya, Italiya) 2010 yil aprel - MCTS usullari va Arimaa o'yini
Tomas Kozelek tomonidan tezis (Praga Charlz universiteti, Chexiya) 2009 yil dekabr - Arimaa o'yinini lingvistik geometriya bilan modellashtirish
Xoseoberto Merkado Vega va Zvi Retchkiman Kösberg tomonidan nashr etilgan (Instituto Politéico Nacional-dan, 5-sonli hisoblash intellekti va o'yinlari bo'yicha xalqaro konferentsiya materiallari, Milano, Italiya) - Arimaa-ni o'ynash uchun kompyuter agentini o'rganish va amalga oshirish
Sem Millerning dissertatsiyasi (Sautgempton universiteti, Buyuk Britaniya) 2009 yil may - Yuqori tanlangan qidiruvga rahbarlik qiladigan rejalar, naqshlar va harakat toifalari
Gerhard Trippen tomonidan yozilgan maqola (2009 yilgi yutuqlar, Computer Games 12 anjumanida, Pamplona, Ispaniya) May 2009 - Arimaa, haqiqiy razvedka o'yini?
prezentatsiya Nikolas A. Barriga tomonidan (Tecnica Federico Santa Mariya universiteti, Chili) 2006 yil avgust - Arimaa o'yinini tahlil qilish va amalga oshirish va B ilova
Krist-Yan Koksning tezisi (Maastrixt universiteti, Bilim va agentlik texnologiyalari instituti), 2006 yil mart - Arimaa-ning kuchli dasturini yaratish
Haizhi Zhong tomonidan dissertatsiya (Alberta universiteti, hisoblash fanlari bo'limi) 2005 yil sentyabr - Jahon chempioni Arimaa dasturini yaratish
Devid Fotlandning qog'ozi (www.Smart-Games.com) 2004 yil - Arimaa - Kompyuterlar uchun qiyin bo'lgan yangi o'yin
Omar Syed va Amir Syed tomonidan yozilgan qog'oz; Xalqaro kompyuter o'yinlari assotsiatsiyasi jurnali; Iyun 2003
Izohlar
- ^ Seyid, Umar; Syed, Amir (2003). "Arimaa - kompyuterlar uchun qiyin bo'lishi uchun mo'ljallangan yangi o'yin". Xalqaro kompyuter o'yinlari assotsiatsiyasi jurnali. 26: 138–139.
- ^ Arimaa: O'yin tugadimi?
- ^ http://www.arimaa.com/arimaa/papers/CoxThesis/Cox_thesis1.pdf
- ^ François Dominic Laramée. "Shaxmatni dasturlash IV qism: asosiy qidiruv". GameDev.net. Arxivlandi asl nusxasi 2007 yil 14 mayda. Olingan 2007-05-01.
- ^ Brayan "Janzert" Xaskin. "Arimaa filialining omiliga qarash". janzert.com/. Arxivlandi asl nusxasidan 2009 yil 7-noyabrda. Olingan 2009-11-25.
- ^ http://arimaa.janzert.com/aei/aei-protocol.html
- ^ http://arimaa.janzert.com/aei/readme.txt
- ^ http://arimaa.com/arimaa/challenge/devBot.html