O'yin daraxti - Game tree

O'yin daraxti uchun u o'yin nazariyasida ishlatiladi (emas kombinatorial o'yin nazariyasi ), qarang Keng qamrovli o'yin.

Yilda o'yin nazariyasi, a o'yin daraxti a yo'naltirilgan grafik kimning tugunlar a-dagi pozitsiyalar o'yin va kimning qirralar harakatlar. The to'liq o'yin daraxti o'yin uchun boshlang'ich holatidan boshlanadigan va har bir pozitsiyadan barcha mumkin bo'lgan harakatlarni o'z ichiga olgan o'yin daraxti; to'liq daraxt - olingan daraxt bilan bir xil daraxt keng ko'lamli o'yin vakillik.

Oyoq daraxtining tik-tac-barmog'i uchun dastlabki ikkita qatlami.

Diagrammada dastlabki ikki daraja yoki qatlamlar, uchun o'yin daraxtida barmoq uchi. Pozitsiyalarning aylanishi va aks etishi tengdir, shuning uchun birinchi o'yinchi uchta harakatlanish imkoniyatiga ega: markazda, chekkada yoki burchakda. Ikkinchi o'yinchi javob uchun ikkita tanlovga ega, agar birinchi o'yinchi markazda o'ynagan bo'lsa, aks holda beshta tanlov mavjud. Va hokazo.

Soni barg tugunlari to'liq o'yin daraxtida o'yinni o'tkazish mumkin bo'lgan turli xil usullar soni. Masalan, tic-tac-toe uchun o'yin daraxti 255 168 barg tuguniga ega.

O'yin daraxtlari muhim ahamiyatga ega sun'iy intellekt chunki o'yindagi eng yaxshi harakatni tanlashning bir usuli bu o'yin daraxtini ko'p sonli narsalardan foydalanib qidirishdir daraxtlarni qidirish algoritmlari minimaks kabi qoidalar daraxtni kesib oling. Tik-tac-toe uchun o'yin daraxtini osongina qidirish mumkin, ammo shunga o'xshash katta o'yinlar uchun to'liq o'yin daraxtlari shaxmat qidirish uchun juda katta. Buning o'rniga, a shaxmat o'ynash dasturi izlaydi a qisman o'yin daraxti: odatda mavjud bo'lgan vaqt oralig'ida qidirib topishi mumkin bo'lgan sonli qatlam. "Patologik" ov daraxtlari holatidan tashqari[1] (bu amalda juda kam ko'rinadigan), qidirish chuqurligini oshirish (ya'ni qidirilgan qatlamlar soni) odatda eng yaxshi harakatni tanlash imkoniyatini yaxshilaydi.

Ikki kishilik o'yinlar sifatida ham ifodalanishi mumkin va-yoki daraxtlar. Birinchi o'yinchi g'alaba qozonishi uchun ikkinchi o'yinchining barcha harakatlari uchun yutuqli harakat bo'lishi kerak. Bu birinchi o'yinchining muqobil harakatlarini ko'rsatish uchun disjunksiya yordamida va ikkinchi o'yinchining barcha harakatlarini ifodalash uchun konyunksiya yordamida va-yoki daraxtda aks etadi.

Ov daraxtlarini echish

Deterministik algoritm versiyasi

To'liq bo'yalgan o'zboshimchalik bilan o'yin daraxti

To'liq o'yin daraxti bilan o'yinni "hal qilish" mumkin, ya'ni birinchi yoki ikkinchi o'yinchi kuzatishi mumkin bo'lgan harakatlar ketma-ketligini toping, bu ushbu o'yinchi uchun eng yaxshi natijani kafolatlaydi (odatda g'alaba yoki taqish). Algoritm (bu odatda deyiladi orqaga qarab induksiya yoki retrograd tahlil ) quyidagicha rekursiv tarzda tavsiflanishi mumkin.

  1. O'yin daraxtining so'nggi qatlamini ranglang, shunda 1-o'yinchi uchun barcha yutuqlar bir tomonga (diagrammada ko'k), 2-o'yinchi uchun barcha yutuqlar boshqa rangga (diagrammada qizil) va barcha bog'ichlar uchinchi tomonga bo'yalgan. (Diagrammada kulrang).
  2. Keyingi qatlamga qarang. Agar mavjud pleyerga qarama-qarshi rangli tugun mavjud bo'lsa, ushbu tugunni o'sha o'yinchi uchun ham ranglang. Agar darhol barcha pastki tugunlar bir xil o'yinchi uchun ranglangan bo'lsa, ushbu tugunni o'sha o'yinchi uchun ham ranglang. Aks holda, ushbu tugunga galstuk rangini bering.
  3. Barcha tugunlar ranglanguncha yuqoriga qarab, har bir qatlam uchun takrorlang. Ildiz tugunining rangi o'yinning mohiyatini belgilaydi.

Diagrammada yuqorida ko'rsatilgan algoritm yordamida rang berilgan, o'zboshimchalik bilan o'yin uchun o'yin daraxti ko'rsatilgan.

Odatda o'yinni ("echish" texnik ma'nosida) faqat o'yin daraxtining pastki qismidan foydalanib hal qilish mumkin, chunki ko'p o'yinlarda bir xil o'yinchi uchun yaxshiroq bo'lgan boshqa harakat bo'lsa, harakatni tahlil qilish shart emas ( masalan alfa-beta Azizillo ko'plab deterministik o'yinlarda foydalanish mumkin).

O'yinni hal qilish uchun ishlatilishi mumkin bo'lgan har qanday subtree a deb nomlanadi qaror daraxtiva har xil shakldagi qaror daraxtlarining o'lchamlari o'lchov sifatida ishlatiladi o'yin murakkabligi.[2]

Tasodifiy algoritmlarning versiyasi

Tasodifiy algoritmlardan o'yin daraxtlarini echishda foydalanish mumkin. Ushbu turdagi amalga oshirishda ikkita asosiy afzallik mavjud: tezlik va amaliylik. Holbuki, o'yin daraxtlarini hal qilishning deterministik versiyasini amalga oshirish mumkin Ο(n), quyidagi tasodifiy algoritm kutilgan ish vaqtiga ega θ(n0.792). Bundan tashqari, bu amaliydir, chunki tasodifiy algoritmlar "dushmanni qirib tashlashga" qodir, ya'ni raqib o'yin daraxtini echish uchun ishlatiladigan algoritmni bilib, o'yin daraxtlari tizimini mag'lub eta olmaydi, chunki echish tartibi tasodifiydir.

Quyida tasodifiy o'yin daraxti echimini topish algoritmi qo'llaniladi:[3]

def gt_eval_rand(siz) -> bool:    "" "Agar bu tugun yutuqni baholasa, to'g'ri qaytadi, aks holda noto'g'ri" ""    agar siz.barg:        qaytish siz.g'alaba qozonish    boshqa:        random_children = (gt_eval_rand(bola) uchun bola yilda tasodifiy tartib(siz.bolalar))        agar siz.op == "YOKI":            qaytish har qanday(random_children)        agar siz.op == "VA":            qaytish barchasi(random_children)

Algoritm "degan fikrdan foydalanadiqisqa tutashuv ": agar ildiz tuguni" deb hisoblansa "Yoki"operatori, keyin bitta To'g'ri topildi, ildiz sifatida tasniflanadi To'g'ri; aksincha, agar ildiz tuguni "VA"operator keyin bitta Yolg'on topildi, ildiz sifatida tasniflanadi Yolg'on.

Shuningdek qarang

Adabiyotlar

  1. ^ Nau, Dana (1982). "O'yinlarda patologiya sabablarini tekshirish". Sun'iy intellekt. 19: 257–278. doi:10.1016/0004-3702(82)90002-9.
  2. ^ Viktor Allis (1994). O'yinlar va sun'iy aqlda echimlarni izlash (PDF). Ph.D. Tezis, Limburg universiteti, Maastrixt, Gollandiya. ISBN  90-900748-8-0.
  3. ^ Daniel Roche (2013). SI486D: Hisoblashdagi tasodifiylik, o'yin daraxtlari birligi. Amerika Qo'shma Shtatlari dengiz akademiyasi, kompyuter fanlari bo'limi.

Qo'shimcha o'qish