Maven (Scrabble) - Maven (Scrabble)

Maven bu sun'iy intellekt Scrabble Brayan Sheppard tomonidan yaratilgan o'yinchi. U rasmiy litsenziyada ishlatilgan Xasbro Scrabble o'yinlari.

Algoritmlar

O'yin bosqichlari

Mavenning o'yin o'yinlari uchta bosqichga bo'lingan: "O'rtacha o'yin" bosqichi, "o'yin oldidan" va "so'nggi o'yin" bosqichi.

"O'yinning o'rtasi" bosqichi o'yin boshidan to to'qqiz yoki undan kamroq plitka qolguncha davom etadi. Dastur berilgan tokchadan barcha mumkin bo'lgan o'yinlarni topish uchun tezkor algoritmdan foydalanadi, so'ngra dasturning "kibitser" deb nomlangan qismi ularni oddiy sifat tartibiga ajratish uchun oddiy evristikadan foydalanadi. Keyinchalik eng istiqbolli harakatlar "simming" bilan baholanadi, unda dastur plitkalarning tasodifiy chizilishini simulyatsiya qiladi, belgilangan miqdordagi o'yinlarni namoyish etadi va harakatlar natijalarining tarqalish nuqtalarini taqqoslaydi. Minglab tasodifiy rasmlarni simulyatsiya qilish orqali dastur turli xil o'yinlarga juda aniq miqdoriy baho berishi mumkin. (Monte-Karloda qidirish paytida Maven foydalanmaydi Monte-Karlo daraxtlarini qidirish chunki u o'yin daraxtlarini o'yin oxirigacha o'ynashni emas, balki faqat 2 qavatli chuqurlikda baholaydi va chuqurroq o'rganish uchun istiqbolli novdalarga taqsimlamaydi; yilda mustahkamlashni o'rganish Mavenni qidirish strategiyasini "qisqartirilgan Monte-Karlo simulyatsiyasi" deb hisoblash mumkin. Haqiqiy MCTS strategiyasi kerak emas, chunki so'nggi o'yinni hal qilish mumkin. Maven muallifining ta'kidlashicha, sayoz qidiruv[1] sumkasidagi harflarning tez aylanishi tufayli, odatda 2 qavatli chuqurlikdan foydaliroq emas, chunki o'rniga chuqurroq ko'rinadigan bo'lsa, masalan. 4 qavatli, dispersiya mukofotlar kattaroq bo'ladi va simulyatsiyalar bir necha marta ko'proq vaqt oladi, shu bilan birga bir nechta ekzotik vaziyatlarda yordam beradi: "Agar biz to'rt qavatli simulyatsiya qiymatini ko'rish uchun CACIQUE kabi o'ta og'ir vaziyatni talab qiladigan bo'lsak, unda ular bunga loyiq emas deb o'ylaymiz qilish. " Bunday taxta qiymati Scrabble-da juda yuqori aniqlik bilan baholanishi mumkin, chunki bu kabi o'yinlardan farqli o'laroq Boring, chuqurroq simulyatsiyalar dastlabki bahoni o'zgartirishi mumkin emas.)

"O'yin oldidan" bosqichi deyarli "o'rtamiyona" bosqichi bilan ishlaydi, faqat bu o'yin oxiridagi vaziyatni keltirib chiqarishga qaratilgan.

"Endgame" bosqichi sumkada plitka qolmasligi bilanoq boshlanadi. Ikki o'yinchi o'yinlarida, bu endi futbolchilar dastlabki harflar taqsimotidan bir-birining tokchasidagi aniq plitkalarni chiqarib olishlari mumkin degan ma'noni anglatadi. Maven foydalanadi B yulduzcha qidirish algoritmi so'nggi o'yin bosqichida o'yin daraxtini tahlil qilish.

Avlodni ko'chirish

Maven harakatlanishni yaratish uchun bir nechta algoritmlardan foydalangan, ammo u qolgani DAWG algoritm. The GADDAG algoritmi tezroq, ammo Shimoliy Amerika ingliz tili uchun DAWG atigi 0,5 MB, GADDAG uchun esa taxminan 2,5 MB. Bu o'yinlarni yuklab olish uchun sezilarli farq qiladi, ammo tezlikning afzalligi muhim emas. (E'tibor bering, ahamiyatsiz narsa bu farq kichikligini anglatmaydi, shunchaki foydalanuvchilar farqni ayta olmaydilar. GADDAG ehtimol ikki baravar tezroq, lekin ikkala algoritm ham tezdir.)

Rackni baholash

Mavenning birinchi (1986) versiyasida javonlarni baholash uchun 100 ga yaqin naqshlardan foydalanilgan. Har bir plitkaning qiymati bor edi (27 naqsh). Har bir dublikatning qiymati bor edi (22 ta naqsh). Uch nusxada naqshlar va sumkada etarlicha tasavvurga ega bo'lgan harflar uchun to'rtburchaklar mavjud edi. Nihoyat, QU kombinatsiyasi naqsh edi.

Birinchi versiyadan ko'p o'tmay, Maven unli / undosh balansi va Q / U taqsimoti uchun javonlarni baholash shartlarini sotib oldi. Unli / undosh balansi - bu tokchada qolgan unli va undoshlar soniga qarab jadvalni qidirish. Q / U taqsimoti Q va U qiymatlarini har birining qancha qismi sumkada qolganligi bo'yicha indekslangan jadvalni qidirish yordamida o'zgartirdi.

Ko'p o'tmay, Maven plitka nusxasini baholovchi vositani sotib oldi. Ikkala nusxani chizish imkoniyatiga qarab, javonni o'zgartirish kerak edi. Masalan, A plitka sifatida mendan ko'ra yaxshiroqdir, lekin agar sumkada 7 A va faqat 2 I qolgan bo'lsa, unda biz I ni saqlashni afzal ko'rishimiz kerak.

Parametrlarni o'rnatish kelajakdagi ballarning umumiy miqdorini taxmin qilish uchun qiymatlarni sozlash orqali amalga oshirildi. Hozirgi kunda bu shunday nomlanadi Vaqtinchalik farqni o'rganish.

Ushbu javonni baholash dizayni Maven uchun o'ziga xos edi. Bu kunning inson chempionlari bilan raqobatlashishda juda muvaffaqiyatli bo'ldi.

Keyinchalik dizayn boshqa tadqiqotchilar tomonidan kengaytirildi. Mark Uotkins "kafel sinergiya naqshlari" deb atagan narsaning chempioni bo'ldi. Bular ko'p sonli so'zlarga asos bo'lgan ADES singari birikma. Bu o'yinni sezilarli darajada yaxshilaydigan dizaynning tabiiy kengaytmasi. Maven naqshlari to'plami asta-sekin 100 taglik to'plamdan 400 tagacha kengayib bordi.

O'shandan beri Maven Jon O'Laughlin tomonidan taklif qilingan va amalga oshirilgan butunlay boshqacha arxitekturaga o'tdi Quackle. Bu "to'liq" arxitektura, bu erda dastur 0 dan 7 tagacha plitalarning har bir 3 million mumkin bo'lgan birikmalarining har biri uchun har xil rack baholash parametrlariga ega. So'nggi o'n yil ichida kompyuter quvvatining rivojlanishi bilan bunday katta parametrlar to'plamini sozlash mumkin bo'ldi.

To'liq yondashuvdan foydalanishning salbiy tomoni shundaki, Maven sumkada qolgan plitkalar funktsiyasi sifatida har xil baholash qobiliyatini yo'qotdi. Gap shundaki, to'liq raf baholovchisida raf qiymatini sumkadan tortib olinadigan tortishish bilan bog'laydigan atamalar mavjud emas.

Mavenning to'liq javonlarni baholash versiyasi ushbu qobiliyatni qo'shdi. Mavenda har bir tokchada o'z laynerlari baholovchisi mavjud bo'lib, u erda ushbu tokchaning qiymati dublikat, unli va Q va U chizish imkoniyatlari funktsiyasi sifatida o'zgarib turadi. Ushbu tizim 5 parametrga ega har bir raf uchun, taxminan 15 million parametr uchun.

Simulyatsiya

Buyuk inson chempioni Ron Tiekert Scrabble-ni o'nlab marotaba individual pozitsiyalarni o'ynab va natijalarni sarhisob qilib o'rgangan. U Mavenning tezligi bilan bir kecha-kunduzda ushbu jarayonni avtomatlashtirish imkoniyati bo'lishi kerakligini taklif qildi. Brayan Sheppard bu jarayonni "simulyatsiya" deb nomladi, garchi u "tavla" va Go-da "playout" nomi bilan yursa.

Jarayon ball + rack evristikasi yordamida N nomzod harakatlarini tanlash edi. Keyin ushbu harakatlarni yuzlab yoki minglab marta o'ynab, qaysi nomzod eng yaxshi natijalarga erishishini bilib oling. Siz o'zingizning maqsadingizga muvofiq o'yinni chuqurligini o'zgartirishingiz mumkin; nuqta farqi haqida yaxshi fikrga ega bo'lish uchun oldinda ikki yoki to'rtta harakatni bajaring yoki g'alaba qozonish imkoniyatini o'lchash uchun o'yin oxirigacha o'ynang.

1990-yillarning o'rtalariga kelib kompyuterlar etarlicha tezlasha boshladilar, shuning uchun Maven simulyatsiya yordamida musobaqa vaqtini boshqarish ostida raqobatbardosh o'yinlarda harakatlarni tanlashni qo'lladi. Algoritmik takomillashtirish ushbu maqsad uchun simulyatsiya hajmini oshirish uchun muhim ahamiyatga ega edi. Eng muhim yangilik, nomzodlarga beriladigan sinovlar sonini turlicha o'zgartirish edi, shunda muvaffaqiyat qozongan nomzodlar ko'proq kuch sarflashadi. Nomzodlarning barcha harakatlari bir xil, xolis tarqatishga qarshi namuna olinishi uchun javonlarni boshqarish ham foydali bo'ldi.

Mavenning simulyatsiya dvigateli o'ynagan o'yinlarning tahlili shuni ko'rsatadiki, Maven inson chempionlarining mahorat darajasidan oshib ketgan.

Endgame

Scrabble so'nggi o'yinlarida kuchli o'yin ko'rinishga qaraganda ancha qiyin. Nazariy jihatdan, so'nggi o'yinlar mukammal ma'lumot o'yinidir, shuning uchun Alfa-beta bilan kesish algoritm ishlashi kerak. Ammo amalda Alpha Beta Scrabble-da yomon ishlaydi.

Alpha Beta bilan bog'liq muammo shundaki, ba'zi Scrabble o'yinlari o'ynash uchun 14 ta harakatni talab qiladi va buni chuqur izlash mumkin emas. Bu shunchaki nazariy imkoniyat emas. Agar bitta o'yinchi plitka bilan "yopishib" qolsa, qolgan barcha plitalarni ijro etish mumkin emas. Bunday vaziyatda har ikki tomon uchun eng maqbul strategiya odatda har bir burilishda bitta plitka o'ynashdir.

Maven boshqa yondashuvni qo'llaydi. The B * qidiruv algoritmi - bu har bir pozitsiyaning qiymatlari bo'yicha yuqori va pastki chegaralarni hisoblash mumkin bo'lganda, ikkita o'yinchi o'yinlariga optimal echimlarni topishni kafolatlaydigan tanlangan chuqurlik, kengayib boruvchi algoritm.

Endgame pozitsiyalarida yuqori va pastki chegaralarni taxmin qilish mumkin ekan. Ushbu chegaralar pozitsiyalarning katta qismi uchun to'g'ri (ya'ni haqiqiy qiymat oraliqda joylashgan). B * chegaradagi kichik foizli xatolar mavjud bo'lganda oqilona mustahkam bo'lgani uchun, Maven boshqa yondashuvlar qila olmaydigan so'nggi o'yinlarni hal qilishi mumkin.

Keyinchalik takomillashtirish Mavenning so'nggi o'yin echimlarini xatolar mavjud bo'lganda ham asemptotik jihatdan maqbul qiladi. Agar B * qidiruvi bir harakat eng yaxshi ekanligiga ishora bilan tugasa va hali vaqt qolgan bo'lsa, u holda Maven hisob-kitoblarini 1 punktga kengaytiradi va yana qidiradi. Ushbu qayta qidirishlar odatda juda tezkor bo'ladi, chunki avvalgi qidiruvdagi daraxt hali ham amal qiladi. Ushbu siyosatdan takroriy foydalanish, eng kichik (va ehtimol katta ehtimollik bilan) xatolardan boshlab, bosqichma-bosqich xatolarni aniqlaydi.

To'liq oldingi o'yin

Torbada faqat 1 yoki 2 ta plitka qolganda ("PEG-1" yoki "PEG-2"), davlat makonini to'liq qidirish mumkin.

PEG-1 ishi muhim, chunki barcha o'yinlarning deyarli yarmi shu holatdan o'tadi. Maven deyarli barcha holatlarda bunday holatlarni to'liq namoyish etishi mumkin. Ya'ni, barcha qonuniy harakatlar uchun Maven paydo bo'lgan so'nggi o'yinlarni o'ynashi mumkin (har bir qonuniy harakat uchun 8 tagacha) va har bir holatda qaysi tomon o'yinda g'alaba qozonishini hisoblab chiqishi mumkin. Qo'shimcha kuch talab qiladigan ba'zi holatlar (masalan, ikkita bo'shliq, Q-ga yopishtirilgan) mavjud bo'lganligi sababli, hisoblash bosqichma-bosqich amalga oshiriladi. Ya'ni, Maven avval qaror yaqin va dolzarb bo'lgan joyda tahlilini kengaytiradi.

PEG-2-da, odatda, barcha harakatlanish ketma-ketligini to'liq tekshirish mumkin emas, shuning uchun Maven mavjud bo'lgan vaqt ichida imkon qadar boradi.

Ushbu past darajadagi holatlarning bir xususiyati shundaki, qonuniy harakatlar ro'yxatini xavfsiz tarzda kesish juda qiyin. Masalan, eng maqbul o'yin 50% dan ortiq harakatlarning orqasida, 1% dan ko'proq vaqt davomida skor + rack evristikasi bilan ajralib turadi.

Ushbu siyosat nazariy jihatdan mukammal o'yinni ishlab chiqarmaydi, chunki ko'rilmagan plitalarning haqiqiy dastlabki taqsimoti qanday bo'lishi mumkinligini bilish mumkin emas. Bir xil taqsimotni yaxshi deb hisoblasak, va bu taxminni sezilarli darajada yaxshilaydigan ko'rinmaydigan plitkalar haqida xulosalarni hisoblash mumkin.

Yana bir cheklov shundaki, Maven bunday vaziyatlarning "yashirin ma'lumot" tomoniga murojaat qilmaydi. Ya'ni, nazariy jihatdan, o'yinchilar taxminiylikni ehtimollik taqsimotiga qarab tasodifiy tanlash orqali kutishni maksimal darajaga ko'taradigan holatlar mavjud. Maven har bir tugunda sof strategiyalarni tanlamoqda.

Adabiyotlar

  1. ^ pg14, ​​Sheppard 2002 yil
  • Sheppard, Brayan (2002). "Jahon chempionati-kalibrli Scrabble" (PDF). Sun'iy intellekt. 134 (1–2): 241–275. doi:10.1016 / S0004-3702 (01) 00166-7.

Tashqi havolalar