Strategiyani o'g'irlash argumenti - Strategy-stealing argument

Yilda kombinatorial o'yin nazariyasi, strategiyani o'g'irlash argumenti general dalil bu ko'pchilik uchun ko'rsatmoqda ikki o'yinchi o'yinlari, ikkinchi o'yinchining kafolati bo'lishi mumkin emas yutish strategiyasi. Strategiyani o'g'irlash argumenti har qanday narsaga tegishli nosimmetrik o'yin (har ikkala o'yinchi bir xil natijalarga ega bo'lgan mavjud harakatlarning bir xil to'plamiga ega bo'lgan, shunda birinchi o'yinchi ikkinchi o'yinchining strategiyasidan "foydalanishi" mumkin), unda ortiqcha harakat hech qachon kamchilikka aylanishi mumkin emas.

Argument a ni olish bilan ishlaydi ziddiyat. G'olib bo'lgan strategiya, uni ishlatadigan ikkinchi o'yinchi uchun mavjud deb hisoblanadi. Ammo keyin, taxminan aytganda, birinchi harakatni amalga oshirgandan so'ng - yuqoridagi shartlarga ko'ra bu kamchilik emas - birinchi o'yinchi ham ushbu g'alaba strategiyasiga muvofiq o'ynashi mumkin. Natijada ikkala o'yinchining ham g'alaba qozonishi kafolatlanadi - bu bema'ni, shuning uchun bunday strategiya mavjud degan taxminga ziddir.

Strategiyani o'g'irlash tomonidan ixtiro qilingan Jon Nesh ning o'yinini namoyish etish uchun 40-yillarda olti burchak har doim birinchi o'yinchining g'alabasi, chunki bu o'yinda bog'lanishlar mumkin emas.[1] Biroq, Nash bu usulni nashr etmadi va Bek (2008) birinchi nashrining kreditini Alfred V. Xeyls va Robert I. Jewett, 1963 yilgi maqolada barmoq uchi unda ular ham buni isbotladilar Hales-Jewett teoremasi.[2] Dalil qo'llaniladigan o'yinlarning boshqa misollariga quyidagilar kiradi m,n,k- o'yinlar kabi gomoku. O'yinda Sylver tanga, strategiyani o'g'irlash o'yin tenglik bilan tugashidan ko'ra, birinchi o'yinchi g'alaba qozonishini ko'rsatish uchun ishlatilgan.[3]

Misol

O'yin misolida strategiyani o'g'irlaydigan argumentdan foydalanish mumkin barmoq uchi, har qanday o'lchamdagi taxta va g'olib qatorlar uchun.[1][2] Aytaylik, ikkinchi o'yinchi strategiyadan foydalanmoqda, S, bu ularga g'oliblikni kafolatlaydi. Birinchi o'yinchi X o'zboshimchalik bilan holatidadir, va keyin ikkinchi o'yinchi an ni qo'yib javob beradi O ga binoan S. Ammo ular birinchi tasodifiy narsani e'tiborsiz qoldirsalar X ular joylashtirgan holda, birinchi o'yinchi ikkinchi o'yinchi birinchi harakatida duch kelgan vaziyatga duch keladi; taxtada bitta dushman bo'lagi. Shuning uchun birinchi o'yinchi o'z harakatlarini mos ravishda amalga oshirishi mumkin S - agar bo'lmasa S boshqasini chaqiradi X e'tiborsiz qoldirilgan joyga joylashtirilishi kerak X allaqachon joylashtirilgan. Ammo bu holda, o'yinchi shunchaki o'zini qo'yishi mumkin X taxtada boshqa tasodifiy holatda, uning aniq ta'siri shu bo'ladi X talab qilgan holatda S, boshqasi esa tasodifiy holatda bo'lib, vaziyatni avvalgidek qoldirib, yangi e'tiborsiz bo'lakka aylanadi. Shu tarzda davom ettirish, S , gipoteza bo'yicha, g'olib pozitsiyani ishlab chiqarishga kafolatlangan (qo'shimcha hisobga olinmagan holda) X natijasi yo'q). Ammo keyinchalik ikkinchi o'yinchi yutqazdi - ular kafolatlangan g'alaba qozonish strategiyasiga ega deb taxmin qilishlariga zid. Ikkinchi o'yinchi uchun bunday g'alaba qozonish strategiyasi mavjud emas, shuning uchun tic-tac-toe birinchi o'yinchi uchun majburiy g'alaba yoki tenglikdir. Keyinchalik tahlillar shuni ko'rsatadiki, bu galstuk.

Xuddi shu dalil har qanday kishiga tegishli kuchli pozitsion o'yin.

Shaxmat

Asosiy maqola: Shaxmat bo'yicha birinchi harakat ustunligi
Filidor, 1777 yil
abvdefgh
8
Shaxmat taxtasi480.svg
a4 oq malika
d3 oq qirol
b2 qora rook
b1 qora shoh
8
77
66
55
44
33
22
11
abvdefgh
Qora zugzvangda, chunki ular podshohlaridan uzoqlashishlari kerak.

Sinflari mavjud shaxmat chaqirilgan pozitsiyalar Zugtsvang unda harakat qilishga majbur bo'lgan o'yinchi, agar bunga yo'l qo'yilsa, "o'tishni" afzal ko'radi. Shu sababli, strategiyani o'g'irlaydigan argumentni shaxmatga qo'llash mumkin emas.[4] Hozirda Oq yoki Qora optimal o'yin bilan g'alabani majburlay oladimi yoki ikkala o'yinchi ham durang o'ynashi mumkinligi ma'lum emas. Shunga qaramay, deyarli barcha shaxmat talabalari Uaytning birinchi harakatini afzallik deb bilishadi va zamonaviy yuqori darajadagi o'yinlarning statistikasi Uaytning g'oliblik nisbati Bleknikiga qaraganda 10 foizga yuqori.

Boring

Yilda Boring o'tishga ruxsat beriladi. Boshlang'ich pozitsiyasi nosimmetrik bo'lsa (bo'sh taxta, ikkala o'yinchida ham ochko yo'q), demak, birinchi o'yinchi birinchi harakatdan voz kechib, ikkinchi o'yinchining g'alaba qozonish strategiyasini o'g'irlashi mumkin. 30-yillardan boshlab, ammo[5] ikkinchi o'yinchiga odatda bir nechta mukofot beriladi kompensatsiya ballari, bu boshlang'ich pozitsiyasini assimetrik qiladi va strategiyani o'g'irlaydigan argument endi ishlamaydi.

O'yindagi asosiy strategiya "oyna boring "Ikkinchi o'yinchi bu raqibning diagonali bilan qarama-qarshi bo'lgan harakatlarni amalga oshiradi. Bu usul yordamida mag'lub bo'lishi mumkin narvon taktikasi, ko janglari yoki kengashning markaziy punktini boshqarish uchun muvaffaqiyatli raqobatlashmoqda.

Konstruktivlik

Strategiyani o'g'irlash argumenti shuni ko'rsatadiki, ikkinchi o'yinchi uchun har qanday gipotetik g'alaba qozonish strategiyasidan ziddiyat keltirib, ikkinchi o'yinchi g'alaba qozona olmaydi. Odatda argument o'yinlarda durang bo'lmasligi mumkin bo'lgan o'yinlarda qo'llaniladi chiqarib tashlangan o'rta qonun. Biroq, u birinchi o'yinchi uchun aniq strategiyani ta'minlamaydi va shu sababli u konstruktiv emas deb nomlangan.[4] Bu aslida g'alaba qozongan strategiyani qanday hisoblash haqida savol tug'diradi.

Kabi cheklangan miqdordagi pozitsiyalarga ega o'yinlar uchun chomp, yutuqli strategiyani to'liq izlash orqali topish mumkin.[6] Biroq, agar pozitsiyalar soni ko'p bo'lsa, bu amaliy emas.

2019 yilda Greg Bodvin va Ofer Grossman g'olib strategiyani topish muammosi ekanligini isbotladilar PSPACE-qiyin strategiyani o'g'irlaydigan argumentlar ishlatilgan ikki turdagi o'yinlarda: minimal poset o'yini va nosimmetrik Maker-Maker o'yini.[7]

Adabiyotlar

  1. ^ a b Bek, Jozef (2008), Kombinatorial o'yinlar: Tic-Tac-Toe nazariyasi, Matematika entsiklopediyasi va uning qo'llanilishi, 114, Kembrij: Kembrij universiteti matbuoti, 65-bet, 74, doi:10.1017 / CBO9780511735202, ISBN  9780511735202, JANOB  2402857.
  2. ^ a b Hales, A. V.; Jewett, R. I. (1963), "Muntazamlik va pozitsion o'yinlar", Amerika Matematik Jamiyatining operatsiyalari, 106 (2): 222–229, doi:10.2307/1993764, JSTOR  1993764, JANOB  0143712.
  3. ^ Sicherman, Jorj (2002), "Sylver coinage nazariyasi va amaliyoti" (PDF), Butun sonlar, 2, G2
  4. ^ a b Bishop, J. M.; Nasuto, S. J .; Tanay T .; Roesch, E. B.; Spenser, M. C. (2016), "HeX va bitta chumolilar uyasi: Hillari xola bilan o'yin o'ynash", Myullerda, Vinsent C. (tahr.), Sun'iy aqlning asosiy masalalari (PDF), Synthese Library, 376, Springer, 369-390 betlar, doi:10.1007/978-3-319-26485-1_22. Xususan 22.2.2.2 bo'limiga qarang, strategiyani o'g'irlash argumenti, p. 376.
  5. ^ Feyrbern, Jon, Komi tarixi, olingan 2010-04-09
  6. ^ rjlipton (2013-10-02). "Strategiyalarni o'g'irlash". Gödelning yo'qolgan maktubi va P = NP. Olingan 2019-11-30.
  7. ^ Bodvin, Greg; Grossman, Ofer (2019-11-15). "Strategiyani o'g'irlash konstruktiv emas". arXiv:1911.06907 [cs.DS ].