Boring va matematika - Go and mathematics

O'yin Boring dunyodagi eng mashhur o'yinlardan biridir. O'zining oqlangan va sodda qoidalari natijasida o'yin azaldan ilhom manbai bo'lib kelgan matematik tadqiqot. Shen Kuo, 11-asrdagi xitoylik olim, taxtada bo'lishi mumkin bo'lgan lavozimlar soni 10 atrofida ekanligini taxmin qilgan¹⁷² yilda Dream Dream Esselar. So'nggi yillarda o'yinni tadqiq qilish John H. Conway ixtirosiga olib keldi syurreal raqamlar va rivojlanishiga hissa qo'shdi kombinatorial o'yin nazariyasi (Go Infinitesimals bilan^[1] uni Go-da ishlatishning o'ziga xos namunasi bo'lish).

Hisoblashning murakkabligi

Generalized Go o'ynaladi n x n taxtalar va hisoblash murakkabligi G'oliblikni umumlashgan Go-ning ma'lum bir pozitsiyasida aniqlash juda muhim ko qoidalari.

Go deyarli "deyarli" PSPACE, chunki odatdagi o'yinda harakatlarni qaytarib bo'lmaydi va faqatgina qo'lga olish orqali qiyinroq murakkablik uchun zarur bo'lgan takroriy naqshlarni olish imkoniyati mavjud.

Ko holda

Ko bo'lmasa, Go PSPACE-qiyin.^[2] Bu kamaytirish orqali isbotlangan Mantiqiy mantiqiy haqiqiy formulalar, ma'lum bo'lgan PSPACE-to'liq, uchun umumlashtirilgan geografiya, rejali umumlashtirilgan geografiyaga, ga maksimal darajaga ega bo'lgan rejali umumlashtirilgan geografiya, nihoyat Go pozitsiyalariga.

Superko bilan boring, PSPACE-da ekanligi ma'lum emas. Garchi haqiqiy o'yinlar hech qachon bundan uzoqroq davom etmasa kerak ${displaystyle n ^ {2}}$ harakat qiladi, umuman Go o'yinlari uzunligiga bog'liq polinom mavjudmi yoki yo'qligi ma'lum emas. Agar bor bo'lsa, Go PSPACE bilan yakunlangan bo'lar edi. Hozirda u PSPACE, EXPTIME yoki hatto EXPSPACE bilan to'ldirilishi mumkin.

Yapon ko qoidasi

Yapon ko qoidalarida faqat asosiy ko, ya'ni taxtani avvalgi holatga qaytaradigan harakat taqiqlanganligi ko'rsatilgan. Uzoqroq takrorlanadigan holatlarga yo'l qo'yiladi, shuning uchun potentsial ravishda o'yinni abadiy hal qilishiga imkon beradi, masalan, uchta ko, bu erda bir vaqtning o'zida uchta kos mavjud bo'lib, 12 ta harakatlanish aylanishiga imkon beradi.

Yapon ko ko qoidalari bilan Go is MAQSAD - to'liq.^[3]

Superko qoidasi

The superko qoidasi (shuningdek, pozitsion superko qoidasi deb ataladi) ilgari sodir bo'lgan har qanday kengash pozitsiyasini takrorlash taqiqlanganligini ta'kidlaydi. Bu ko-ning aksariyat Xitoy va AQSh qoidalarida qo'llaniladi.

Go-ning murakkablik sinfi superko qoidalari ostida bo'lganligi ochiq muammo. Garchi Yapon ko bilan qoida EXPTIME nihoyasiga etgan bo'lsa ham, Robsonning EXPTIME to'liqligi dalilining pastki va yuqori chegaralari.^[3] superko qoidasi qo'shilganda sindirish.

Ma'lumki, bu hech bo'lmaganda PSPACE-ga qiyin, chunki dalil^[2] Go ning PSPACE qattiqligi ko qoidasiga yoki ko qoidasining etishmasligiga ishonmaydi. Go EXPSPACE-da ekanligi ham ma'lum.^[4]

Robson^[4] agar superko qoidasi, ya'ni "hech qachon oldingi holat qayta tiklanmasligi mumkin" bo'lsa, EXPTIME tugallangan ba'zi ikkita o'yinchi o'yinlariga qo'shilsa, u holda yangi o'yinlar EXPSPACE bilan yakunlangan bo'ladi. Intuitiv ravishda, bu pozitsiyadan qonuniy harakatlarni aniqlash uchun hatto eksponent miqdor talab etiladi, chunki pozitsiyaga qadar bo'lgan o'yin tarixi eksponent sifatida uzoq bo'lishi mumkin.

Natijada, superko variantlari (oldingi taxtaning holatini takrorlaydigan harakatlarga yo'l qo'yilmaydi) umumlashtirildi shaxmat va shashka EXPSPACE bilan to'ldirilgan, chunki umumlashtirilgan shaxmat^[5] va shashka^[6] EXPTIME tugagan. Biroq, bu natija Go-ga tegishli emas.^[4]

Ba'zi Go konfiguratsiyalarining murakkabligi

Go Go endgame, taxtani boshqa barcha mahalliy hududlardan tirik toshlar bilan ajratib turadigan maydonlarga bo'linishidan boshlanadi, masalan, har bir mahalliy maydon polinom kattaligi kanonik o'yin daraxtiga ega. Tilida kombinatorial o'yin nazariyasi, bu Go o'yini polinom kattaligi kanonik o'yin daraxtlari bilan subgames yig'indisiga ajralganda sodir bo'ladi.

Ushbu ta'rif bilan Go so'nggi o'yinlari PSPACE-ga qiyin.^[7]

Bu konvertatsiya qilish orqali isbotlangan Mantiqiy mantiqiy formulalar PSPACE bilan tugallangan muammo kichik (polinomial kattalikdagi kanonik o'yin daraxtlari bilan) yig'indisiga o'ting. E'tibor bering, qog'oz Go o'yinlari PSPACE-da ekanligini isbotlamaydi, shuning uchun ular PSPACE bilan to'ldirilmagan bo'lishi mumkin.

Qaysi tomonni yutishini aniqlash a narvon Yaponiya ko qoidasi yoki superko qoidasi amal qilishidan qat'i nazar, PSPACE poygasini qo'lga kiritish.^[8] Bu PSPACE bilan to'ldirilgan deb nomlanuvchi QBF-ni taxta atrofida yorug'lik nurlari singari zinapoyalar bilan taqlid qilish orqali isbotlangan.

Yuridik lavozimlar

Taxtadagi har bir joy bo'sh, qora yoki oq bo'lishi mumkinligi sababli, jami 3 ta^n² uzunligi n bo'lgan kvadrat taxtada mumkin bo'lgan taxta joylari; ammo ularning faqat bir qismi qonuniydir. Tromp va Farnebek yuridik pozitsiyalar uchun rekursiv formulani ishlab chiqdilar ${displaystyle L (m, n)}$ uzunligi m va n bo'lgan to'rtburchaklar taxtaning.^[9] Ning aniq soni ${displaystyle L (19,19)}$ 2016 yilda olingan.^[10] Shuningdek, ular asimptotik formulani topadilar ${displaystyle Lapprox AB ^ {m + n} C ^ {mn}}$ , qayerda ${displaystyle Aapprox 0.8506399258457145}$ , ${displaystyle Bapprox 0.96553505933837387}$ va ${displaystyle Capprox 2.975734192043357249381}$ . Kuzatiladigan koinotda taxminan 10 ta narsa borligi taxmin qilingan⁸⁰ atomlar, odatdagi taxta o'lchamidagi mumkin bo'lgan huquqiy pozitsiyalar sonidan ancha kam (m = n = 19). Kengash kattalashgan sari qonuniy pozitsiyalarning ulushi kamayadi.

Taxta hajmi n × n	3^n²	Foiz qonuniy	${displaystyle L}$ (yuridik lavozimlar) (A094777 )^[11]
1×1	3	33.33%	1
2×2	81	70.37%	57
3×3	19,683	64.40%	12,675
4×4	43,046,721	56.49%	24,318,165
5×5	847,288,609,443	48.90%	414,295,148,741
9×9	4.43426488243×10³⁸	23.44%	1.03919148791×10³⁸
13×13	4.30023359390×10⁸⁰	8.66%	3.72497923077×10⁷⁹
19×19	1.74089650659×10¹⁷²	1.20%	2.08168199382×10¹⁷⁰

O'yin daraxtining murakkabligi

The kompyutershunos Viktor Allis mutaxassislar o'rtasidagi odatiy o'yinlar taxminan 150 ta harakatni davom ettirishini ta'kidlaydi, har bir harakat uchun o'rtacha 250 ta tanlov mavjud, bu esa a ni taklif qiladi o'yin daraxtining murakkabligi 10 dan³⁶⁰.^[12] Soni uchun nazariy jihatdan mumkin o'yinlar, shu jumladan amalda o'ynash mumkin bo'lmagan o'yinlar, Tromp va Farnebak 10 ning pastki va yuqori chegaralarini beradi^10⁴⁸ va 10^10¹⁷¹ navbati bilan.^[9]Pastki chegara a ga yaxshilandi Googolpleks Walraet va Tromp tomonidan.^[13]Mumkin bo'lgan o'yinlar soni bo'yicha eng ko'p keltirilgan raqam, 10 ta⁷⁰⁰^[14] 361 ta harakat yoki 361 ta oddiy almashtirishdan kelib chiqadi! = 10⁷⁶⁸. Yana bir keng tarqalgan chiqish - bu N kesishish va L uchun eng uzun o'yinni qabul qilishdir. Masalan, ba'zi professional o'yinlarda ko'rinib turganidek, 400 ta harakat 361 ta harakatdan bittasi bo'ladi⁴⁰⁰ yoki 1 × 10¹⁰²³ mumkin bo'lgan o'yinlar.

Mumkin bo'lgan o'yinlarning umumiy soni - bu taxtaning kattaligi va bajarilgan harakatlar soni funktsiyasidir. Aksariyat o'yinlar 400 yoki hatto 200 ta harakatdan kam davom etsa-da, yana ko'p narsalar mumkin.

O'yin hajmi	Taxta kattaligi N (chorrahalar)	N!	O'yinning o'rtacha uzunligi L	N^L	O'yinning maksimal davomiyligi (# harakat)	O'yinlarning pastki chegarasi	O'yinlarning yuqori chegarasi
2×2	4	24	3	64		386,356,909,593^[15]	386,356,909,593
3×3	9	3.6×10⁵	5	5.9×10⁴
4×4	16	2.1×10¹³	9	6.9×10¹⁰
5×5	25	1.6×10²⁵	15	9.3×10²⁰
9×9	81	5.8×10¹²⁰	45	7.6×10⁸⁵
13×13	169	4.3×10³⁰⁴	90	3.2×10²⁰⁰
19×19	361	1.0×10⁷⁶⁸	200	3×10⁵¹¹	10⁴⁸	10^10⁴⁸	10^10¹⁷¹
21×21	441	2.5×10⁹⁷⁶	250	1.3×10⁶⁶¹

Mumkin bo'lgan o'yinlarning umumiy sonini taxtaning kattaligiga qarab bir necha usul bilan baholash mumkin, ba'zilari boshqalarga qaraganda qattiqroq. Eng sodda, taxta o'lchamining o'zgarishi, (N)_L, noqonuniy ushlash va pozitsiyalarni kiritmasa. N taxtaning kattaligi (19 × 19 = 361) va L ni eng uzun o'yin sifatida olib, N^L yuqori chegarani tashkil qiladi. Keyinchalik aniq chegara Tromp / Farnebäck qog'ozida keltirilgan.

Eng uzun o'yin L (19 × 19)	(N)_L	O'yinlarning pastki chegarasi	O'yinlarning yuqori chegarasi	Izohlar
1	361	361	361	Oq birinchi harakatdan so'ng iste'foga chiqadi, 361 barcha simmetriyaga e'tibor bermaydi, shu jumladan y = x else (Burchakdan masofalar) 10x10-10 = 90 90/2 = 45 +10 (x = y simmetriya nuqtalarini qaytarish) = 55.
2	722		721	Qora oqning birinchi harakatidan so'ng iste'foga chiqadi, 721 barcha simmetriyani hisobga olmaganda, y = x else 19x19-19 = 342 342/2 = 171 +19 = 190 - 1 = 189.
50	2.1×10¹²⁶		7.5×10¹²⁷
100	1.4×10²⁴⁹		5.6×10²⁵⁵
150	6.4×10³⁶⁷		4.2×10³⁸³
200	1.9×10⁴⁸¹		3.2×10⁵¹¹
250	8.2×10⁵⁸⁷		2.4×10⁶³⁹
300	2.8×10⁶⁸⁴		7.8×10⁷⁶⁶
350	3.6×10⁷⁶⁰		1.3×10⁸⁹⁵
361	1.4×10⁷⁶⁸		1.8×10⁹²³	181 qora va 180 oq toshlardan foydalangan holda eng uzun o'yin
411	n / a		1.3×10¹⁰⁵¹	Eng uzoq professional o'yin^[16]
500	n / a		5.7×10¹²⁷⁸
1000	n / a		3.2×10²⁵⁵⁷
47 million	n / a		10^10⁸	361 ^ 3 harakat
10⁴⁸	n / a	10^10⁴⁸	10^10¹⁷¹	Eng uzoq o'yin

10⁷⁰⁰ Shunday qilib, 200 ta harakatda o'tkazilishi mumkin bo'lgan o'yinlar sonini ortiqcha baholash va 361 ta harakatlarda o'tkazilishi mumkin bo'lgan o'yinlar sonini kam baholashdir. Bir yilda taxminan 31 million soniya bo'lganligi sababli, 47 million harakatni o'ynash uchun kuniga 16 soat soniyada bir harakat qilib, taxminan 2¼ yil kerak bo'ladi.

Shuningdek qarang

O'yinning murakkabligi
Shannon raqami (Shaxmat)

Izohlar

^ Infinitesimals-ga o'ting
^ ^a ^b Lixtenshteyn, Devid; Sipser, Maykl (1980 yil aprel). "Go polinomiya-kosmik qiyin" (PDF). ACM jurnali. 27 (2): 393–401. doi:10.1145/322186.322201.
^ ^a ^b Robson, Jon (1983). "Go murakkabligi". Axborotni qayta ishlash bo'yicha IFIP 9-Butunjahon kompyuter kongressi materiallari: 413–417.
^ ^a ^b ^v Robson, J (1984). Eksponentli kosmosga ega bo'lgan kombinatoriya o'yinlari to'liq qaror qabul qilish muammolari. Informatika matematik asoslari to'plami. Kompyuter fanidan ma'ruza matnlari. 176. 498-506 betlar. doi:10.1007 / BFb0030333. ISBN 978-3-540-13372-8.
^ Aviezri Fraenkel va D. Lixtenshteyn (1981). "N × n shaxmat bo'yicha mukammal strategiyani hisoblash n ga eksponent vaqtni talab qiladi". J. Taroq. Th. A. 31 (31): 199–214. doi:10.1016/0097-3165(81)90016-9.
^ J. M. Robson (1984). "N by N shashka uchun vaqt tugadi". Hisoblash bo'yicha SIAM jurnali. 13 (2): 252–267. doi:10.1137/0213018.
^ Vulf, Devid (2002). Nowakovski, Richard J. (tahrir). "Oxirgi o'yinlar PSPACE-ga qiyin" (PDF). Matematika fanlari ilmiy-tadqiqot instituti nashrlari 42: 125–136.
^ Krasmaru, Marsel; Tromp, Jon (2000). Narvonlari PSPACE-Complete hisoblanadi. Kompyuterlar va o'yinlar. Kompyuter fanidan ma'ruza matnlari. 2063. Springer. 241-249 betlar. CiteSeerX 10.1.1.24.4665. doi:10.1007/3-540-45579-5_16. ISBN 978-3-540-43080-3.
^ ^a ^b Tromp, J; Farnebek, G (2007), Go kombinatorikasi, Springer, Berlin, Heidelberg, doi:10.1007/978-3-540-75538-8_8, ISBN 978-3-540-75537-1
^ https://tromp.github.io/go/legal.html 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
^ https://tromp.github.io/go/gostate.pdf
^ Allis 1994 yil
^ Walraet, M; Tromp, J (2016), Go o'yinlari Googolpleksi, Springer, Berlin, Heidelberg, doi:10.1007/978-3-319-50935-8_18, ISBN 978-3-319-50934-1
^ AGA - Go o'ynash uchun eng yaxshi o'nta sabab
^ Tromp 1999 yil
^ https://homepages.cwi.nl/~aeb/go/misc/gostat.html

Adabiyotlar

AGA. "Go o'ynashning eng yaxshi o'nta sababi".
Allis, Viktor (1994). O'yinlar va sun'iy aqlda echimlarni izlash (PDF). Ph.D. Tezis, Limburg universiteti, Maastrixt, Gollandiya. ISBN 978-90-900748-8-7.
Xirn, Robert A. (2006). "O'yinlar, jumboqlar va hisoblashlar" (PDF). [Fan nomzodi Tezis, MIT.]
Jonson, Jorj (1997-07-29). "Kuchli kompyuterni sinab ko'rish uchun qadimiy o'yin o'ynang". Nyu-York Tayms.
Papadimitriou, Xristos (1994), Hisoblash murakkabligi, Addison Uesli.
Tromp, Jon (1999). "Pozitsion superko bilan 2 × 2 o'yinlar soni".
Tromp, Jon (2016). "Huquqiy Go pozitsiyalari soni (19 × 19 gacha)".
Tromp, Jon; Farnebak, Gunnar (2007). "Go kombinatorikasi".

Tashqi havolalar

Boring va matematika
O'yinning mumkin bo'lgan natijalari soni - Sensei kutubxonasidagi maqola

[1] Infinitesimals-ga o'ting

[sipser1980-2] Lixtenshteyn, Devid; Sipser, Maykl (1980 yil aprel). "Go polinomiya-kosmik qiyin" (PDF). ACM jurnali. 27 (2): 393–401. doi:10.1145/322186.322201.

[robson1983-3] Robson, Jon (1983). "Go murakkabligi". Axborotni qayta ishlash bo'yicha IFIP 9-Butunjahon kompyuter kongressi materiallari: 413–417.

[robson1984-4] v Robson, J (1984). Eksponentli kosmosga ega bo'lgan kombinatoriya o'yinlari to'liq qaror qabul qilish muammolari. Informatika matematik asoslari to'plami. Kompyuter fanidan ma'ruza matnlari. 176. 498-506 betlar. doi:10.1007 / BFb0030333. ISBN 978-3-540-13372-8.

[Fraenkel1981-5] Aviezri Fraenkel va D. Lixtenshteyn (1981). "N × n shaxmat bo'yicha mukammal strategiyani hisoblash n ga eksponent vaqtni talab qiladi". J. Taroq. Th. A. 31 (31): 199–214. doi:10.1016/0097-3165(81)90016-9.

[robson1984checkers-6] J. M. Robson (1984). "N by N shashka uchun vaqt tugadi". Hisoblash bo'yicha SIAM jurnali. 13 (2): 252–267. doi:10.1137/0213018.

[7] Vulf, Devid (2002). Nowakovski, Richard J. (tahrir). "Oxirgi o'yinlar PSPACE-ga qiyin" (PDF). Matematika fanlari ilmiy-tadqiqot instituti nashrlari 42: 125–136.

[8] Krasmaru, Marsel; Tromp, Jon (2000). Narvonlari PSPACE-Complete hisoblanadi. Kompyuterlar va o'yinlar. Kompyuter fanidan ma'ruza matnlari. 2063. Springer. 241-249 betlar. CiteSeerX 10.1.1.24.4665. doi:10.1007/3-540-45579-5_16. ISBN 978-3-540-43080-3.

[Tromp_and_Farnebäck_2007-9] Tromp, J; Farnebek, G (2007), Go kombinatorikasi, Springer, Berlin, Heidelberg, doi:10.1007/978-3-540-75538-8_8, ISBN 978-3-540-75537-1

[10] ttps://tromp.github.io/go/legal.html 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935

[11] ttps://tromp.github.io/go/gostate.pdf

[12] Allis 1994 yil

[13] Walraet, M; Tromp, J (2016), Go o'yinlari Googolpleksi, Springer, Berlin, Heidelberg, doi:10.1007/978-3-319-50935-8_18, ISBN 978-3-319-50934-1

[top_ten-14] AGA - Go o'ynash uchun eng yaxshi o'nta sabab

[15] Tromp 1999 yil

[16] ttps://homepages.cwi.nl/~aeb/go/misc/gostat.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]