Endgame stol bazasi - Endgame tablebase

Stol bazasini so'rash uchun odatiy interfeys

An endgame stol bazasi kompyuterlashtirilgan ma'lumotlar bazasi tarkibida oldindan hisoblangan to'liq tahlil mavjud shaxmat o'yini lavozimlar. Odatda o'yin paytida kompyuter shaxmat dvigateli yoki allaqachon o'ynalgan o'yinni retrospektiv tahlil qiladigan odam yoki kompyuter foydalanadi.

Stol tagida quyidagilar mavjud o'yin nazariy qiymati (yutuq, yo'qotish yoki chizish ) har bir mumkin bo'lgan pozitsiyada va bu natijaga erishish uchun qancha harakat kerak bo'ladi mukammal o'yin. Shunday qilib, stol bazasi an vazifasini bajaradi oracle, har doim optimal harakatlarni ta'minlaydi. Odatda ma'lumotlar bazasi har bir mumkin bo'lgan pozitsiyani aniqlik bilan qayd etadi qismlar taxtada qolgan va eng yaxshi harakatlar Oq harakat qilish va bilan Qora harakatlanmoq.

Stol tagliklari tomonidan yaratilgan retrograd tahlil, a dan orqaga qarab ishlash matematik pozitsiya. 2005 yilga qadar oltita donaga (shu jumladan ikkitasini) o'z ichiga olgan barcha shaxmat pozitsiyalari shohlar ) hal qilingan edi. 2012 yil avgustga kelib, stol tagliklari har bir pozitsiya uchun ettita donaga qadar bo'lgan shaxmatni hal qilishdi (yolg'iz qirol bilan qirolga qarshi pozitsiyalar va beshta dona chiqarib tashlandi, chunki ular "aniq" deb hisoblangan).^[1][2]

Ushbu echimlar shaxmat jamoatchiligining tushunchalarini chuqur oshirdi so'nggi o'yin nazariyasi. Odamlar durang sifatida tahlil qilgan ba'zi pozitsiyalarni yutib olish mumkinligi isbotlangan; stol tayanchini tahlil qilish besh yuzdan ortiq harakatlarda umr yo'ldoshini topishi mumkin ufq odamlar va o'yin paytida kompyuterning imkoniyatlaridan tashqari. Shu sababli ular ham savolni shubha ostiga qo'yishdi 50 ta harakat qoidasi chunki ko'plab pozitsiyalar hozirda mavjud bo'lib, ular bir tomonning yutug'i, ammo 50 ta harakat qoidasi tufayli tortilishi mumkin edi. Stol tagliklari raqobatbardosh o'yinlarni kuchaytirdi va tarkibini osonlashtirdi endgame tadqiqotlar. Ular kuchli analitik vositani taqdim etadi.

Shunga o'xshash boshqa stol o'yinlari uchun stol tagliklari shashka,^[3] shaxmat variantlari^[4] yoki to'qqiz erkak morris^[5] mavjud bo'lsa, o'yin ko'rsatilmagan bo'lsa, u shaxmat deb hisoblanadi.

Fon

Ning jismoniy cheklovlari kompyuter texnikasi chetga, printsipial jihatdan mumkin har qanday o'yinni hal qilish sharti bilan to'liq holat ma'lum va yo'q tasodifiy imkoniyat. Kuchli echimlar, ya'ni har qanday pozitsiyadan mukammal o'yin ishlab chiqaradigan algoritmlar,^[6] kabi ba'zi oddiy o'yinlar bilan mashhur Tic Tac Toe / Nogts va xochlar (mukammal o'yin bilan rasm chizish) va To'rtni ulang (birinchi o'yinchi g'alaba qozonadi). Zaif echimlar kabi murakkabroq o'yinlar uchun mavjud, masalan shashka (ikkala tomonning mukammal o'yinlari bilan o'yin durang deb tanilgan, ammo mukammal bo'lmagan o'yin yaratgan har bir pozitsiya uchun keyingi harakat qanday mukammal bo'lishi ma'lum emas). Boshqa o'yinlar, masalan, shaxmat va Boring, hal qilinmadi, chunki ular o'yin murakkabligi barcha mumkin bo'lgan pozitsiyalarni baholash uchun kompyuterlar uchun juda katta. O'yinning murakkabligini kamaytirish uchun tadqiqotchilar ushbu murakkab o'yinlarni taxtaning hajmini yoki bo'laklarning sonini yoki ikkalasini kamaytirish orqali o'zgartirdilar.

Kompyuter shaxmat ning eng qadimgi domenlaridan biri hisoblanadi sun'iy intellekt, 30-yillarning boshlarida boshlangan. Klod Shannon 1949 yilda shaxmat harakatlarini baholash uchun rasmiy mezonlarni taklif qildi. 1951 yilda Alan Turing ibtidoiy shaxmat o'ynash dasturini ishlab chiqdi, unda material uchun qiymatlar va harakatchanlik; dastur Turingning qo'lda hisob-kitoblari asosida shaxmatni "o'ynadi".^[7] Biroq, vakolatli shaxmat dasturlari rivojlana boshlaganida ham, ular so'nggi o'yinni o'ynashda ajoyib zaiflikni namoyish etishdi. Dasturchilar o'ziga xos xususiyatlarni qo'shdilar evristika so'nggi o'yin uchun - masalan, shoh taxtaning markaziga o'tishi kerak.^[8] Biroq, yanada kengroq echim kerak edi.

1965 yilda, Richard Bellman shaxmatni hal qilish uchun ma'lumotlar bazasini yaratishni taklif qildi va shashka so'nggi o'yinlardan foydalanish retrograd tahlil.^[9][10] Tahlil qilish o'rniga oldinga hozirda doskadagi pozitsiyadan ma'lumotlar bazasi tahlil qiladi orqaga bitta o'yinchi bo'lgan pozitsiyalardan matematik yoki to'xtab qoldi. Shunday qilib, shaxmat kompyuteri endi o'yin davomida so'nggi o'yin pozitsiyalarini tahlil qilishga hojat qolmaydi, chunki ular oldindan hal qilingan. Bu endi xatoga yo'l qo'ymaydi, chunki stol bazasi har doim eng yaxshi harakatni o'ynagan.

1970 yilda Tomas Strölyayn doktorlik dissertatsiyasini nashr etdi^[11][12] quyidagilarni tahlil qilish bilan endgame sinflari: KQK, KRK, KPK, KQKR, KRKBva KRKN.^[13] 1977 yilda Tompsonning KQKR ma'lumotlar bazasi qarshi o'yinda ishlatilgan Grossmeyster Valter Braun.

Ken Tompson va boshqalar stol to'shaklarini to'rt va besh qismli so'nggi o'yinlarni, shu jumladan, xususan, qamrab olish uchun kengaytirishga yordam berishdi KBBKN, KQPKQva KRPKR.^[14][15] Lyuis Stiller 1995 yilda ba'zi olti qismli stol usti so'nggi o'yinlari bo'yicha tadqiqotlar bilan dissertatsiyani chop etdi.^[16][17]

Yaqinda ishtirok etganlar orasida quyidagi odamlar bor:

• Evgeniy Nalimov, uning nomi bilan mashhur Nalimov dasturxonlari nomlangan;
• Stol bazasi kontseptsiyasini "Muzlatgich" deb nomlangan dasturga moslashtirgan Eiko Bleyxer (pastga qarang);
• Gay Xovort, akademik O'qish universiteti, kim ko'p nashr etgan ICGA jurnali va boshqa joylarda;
• Mark Bourzutskiy va Yakov Konoval, ular taxtada etti donadan iborat bo'lgan o'yinlarni tahlil qilishda hamkorlik qildilar;
• Piter Karrer, ixtisoslashgan etti qismli stol usti qurgan (KQPPKQP) ning so'nggi o'yini uchun Kasparov Dunyoga qarshi onlayn o'yin;
• 2012 yil iyul oyida 4 + 3 DTM stolchalarini (KPPPKPP bilan birga 525 ta tugatgan) tugatgan Moskva Davlat Universitetidan Vladimir Maxnychev va Viktor Zaxarov. Dasturxonlar Lomonosov stollari deb nomlangan. Keyingi 5 + 2 DTM stol tagliklari to'plami (KPPPPKP ni o'z ichiga olgan 350 ta tugatish) 2012 yil avgust oyida tugallandi. Stol tagliklarini ishlab chiqarishning yuqori tezligi superkompyuter Lomonosov nomidagi (top500 ). Etti kishiga qadar bo'lgan barcha stol tagliklarining o'lchami taxminan 140 TB.^[18]

Etti donagacha bo'lgan barcha so'nggi o'yinlar jadvallarini bepul yuklab olish mumkin, shuningdek veb-interfeyslar yordamida so'ralishi mumkin (quyidagi tashqi havolalarni ko'ring). Nalimov stol bazasi bir nechta talab qiladi terabayt saqlash maydoni.^[19][20]

Stol tagliklari yaratilmoqda

Metrikalar: konvertatsiya chuqurligi va juftlikka chuqurlik

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

Masalan: DTC va DTM

Stol bazasini yaratishdan oldin dasturchi a ni tanlashi kerak metrik maqbullik - boshqacha qilib aytganda, ular o'yinchi qaysi vaqtda o'yinda "g'olib" bo'lganligini aniqlab olishlari kerak. Har qanday pozitsiyani kerakli so'nggi nuqtadan masofa (ya'ni harakatlarning soni) bilan belgilash mumkin. Odatda ikkita ko'rsatkich qo'llaniladi:

• Juftlik chuqurligi (DTM). Matematik - o'yinni yutishning yagona usuli.
• Konvertatsiya qilish chuqurligi (DTC). Kuchliroq tomon ham materialni qo'lga kiritish orqali g'alaba qozonishi mumkin va shu bilan oddiy o'yin o'yiniga aylanadi. Masalan, KQKRda konvertatsiya Oq Qora rookni qo'lga kiritganda sodir bo'ladi.

Xovort yana ikkita o'lchovni muhokama qildi, ya'ni "nolga siljishgacha chuqurlik" (DTZ) va "qoida bo'yicha chuqurlik" (DTR). Nolinchi harakat - bu ellik harakat qoidasi bo'yicha harakat sonini nolga qaytaradigan harakat, ya'ni juftlik, qo'lga olish yoki garov harakati.^[21] Ushbu ko'rsatkichlar ellik harakat qoidasi, lekin DTR stol bazalari hali hisoblanmagan. 7 kishilik DTZ dasturxonlari 2018 yil avgust oyida ommaga taqdim etildi.^[22]

DTC va DTM o'rtasidagi farqni o'ngdagi diagrammani tahlil qilish orqali tushunish mumkin. Oqni qanday davom ettirish qaysi metrikadan foydalanilganiga bog'liq.

DTC metrikasiga ko'ra, Uayt darvozani egallashi kerak, chunki bu darhol g'alaba qozonadigan pozitsiyaga olib keladi (DTC = 1), ammo mat (matematik) uchun yana ikkita harakat kerak bo'ladi (DTM = 3). DTM metrikasiga ko'ra, Oq ikki harakatda juftlashadi, shuning uchun DTM = DTC = 2.

Ushbu farq ko'plab so'nggi o'yinlarga xosdir. Odatda DTC DTM dan kichikroq, ammo DTM metrikasi eng tezkor matga olib keladi. Istisnolar zaif tomonda faqat qirol bo'lganida va g'ayrioddiy so'nggi o'yinda sodir bo'ladi bitta piyonga qarshi ikkita ritsar; u holda DTC = DTM, chunki materialni olish yoki olish uchun hech qanday himoya materiali yo'q, chunki u hech qanday foyda keltirmaydi. (Darhaqiqat, so'nggi o'yinda himoya piyonini qo'lga kiritish durangga olib keladi, agar bu darhol turmush o'rtog'iga olib kelmasa).

1-qadam: barcha mumkin bo'lgan pozitsiyalarni yaratish

Devid Levi, Kompyuterlar shaxmatni qanday o'ynaydi

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

O'nta noyob kvadrat (simmetriya bilan)

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

Yigirma to'rtta noyob lombard (simmetriya bilan)

Metrikani tanlagandan so'ng, birinchi navbatda berilgan material bilan barcha pozitsiyalarni yaratish kerak. Masalan, qirol va malika qirolga qarshi o'yin uchun DTM jadvallar bazasini yaratish uchun (KQK), kompyuter taxminan 40,000 noyob yuridik pozitsiyalarni tavsiflashi kerak.

Levi va yangi tug'ilgan chaqaloq 40000 soni a dan kelib chiqqanligini tushuntiradi simmetriya dalil. Qora podshoh o'nta kvadratning har biriga joylashtirilishi mumkin: a1, b1, c1, d1, b2, c2, d2, c3, d3 va d4 (diagramaga qarang). Boshqa har qanday kvadratda uning o'rnini aylanish yoki aks ettirish simmetriyasi bilan teng deb hisoblash mumkin. Shunday qilib, burchakdagi qora podshoh a1, a8, h8 yoki h1-da yashashi hech qanday farq qilmaydi. Oq shohni joylashtirish uchun bu sonni eng ko'pi bilan 60 (qonuniy qolgan) kvadratga, so'ngra Oq malikaga eng ko'p 62 kvadratga ko'paytiring. Mahsulot 10 × 60 × 62 = 37,200. Ushbu pozitsiyalarning bir necha yuztasi noqonuniy, imkonsiz yoki bir-birining nosimmetrik aksidir, shuning uchun ularning haqiqiy soni biroz kichikroq.^[23][24]

Har bir pozitsiya uchun jadval bazasi "harakatlanuvchi oq" va "qora harakatlanuvchi" uchun vaziyatni alohida baholaydi. Uaytning malikasi bor deb taxmin qilsak, deyarli barcha pozitsiyalar Oq g'alaba bo'lib, matematikani o'ndan ortiq harakatga majburlamagan. Ba'zi pozitsiyalar tufayli durang o'ynaydi to'xtab qolish yoki malika yo'qolishi muqarrar.

A-ga qo'shilgan har bir qo'shimcha qism garovsiz so'nggi o'yin noyob pozitsiyalar sonini taxminan oltmish marta ko'paytiradi, bu boshqa qismlar egallamagan kvadratlarning taxminiy sonidir.

Bir yoki bir nechta garovga ega so'nggi o'yinlar murakkablikni oshiradi, chunki simmetriya argumenti kamayadi. Piyonlar oldinga siljiy olishlari mumkin, lekin yonboshlashlari mumkin emas, taxtaning aylanishi va vertikal aks etishi pozitsiya tabiatida tub o'zgarishlarni keltirib chiqaradi.^[25] Simmetriyani eng yaxshi hisoblash a2-a7-d7-d2 to'rtburchaklaridagi bitta kvadratni 24 kvadrat bilan cheklash orqali erishiladi. Boshqa barcha qismlar va garovlar garovga nisbatan 64 kvadratning har qandayida joylashgan bo'lishi mumkin. Shunday qilib, garovga ega bo'lgan so'nggi o'yinning murakkabligi 24/10 = 2,4 marta, xuddi shu sonli qismga ega bo'lgan garovsiz so'nggi o'yin.

2-bosqich: retrograd tahlil yordamida pozitsiyalarni baholash

Tim Krabbé jadval bazasini yaratish jarayonini quyidagicha tushuntiradi:

"G'oya shundan iboratki, ma'lumotlar bazasi berilgan material bilan barcha mumkin bo'lgan pozitsiyalar bilan tuzilgan [eslatma: oldingi bobda bo'lgani kabi]. Keyin pastki ma'lumotlar bazasi Qora bilan bog'langan barcha pozitsiyalardan tuziladi. Keyin Oq sherik berishi mumkin bo'lgan joy. Keyin bitta qaerda oq oqni turmush o'rtog'ini keyingi harakatga qo'yishni to'xtata olmasa, u holda har doim oq har doim uni qora tanli turmush o'rtog'ini berishga to'sqinlik qila oladigan joyga etib borishi mumkin va shu tariqa, har doim juftlikdan uzoqroq masofada, shu tariqa turmush o'rtog'i bilan bog'langan barcha pozitsiyalargacha. Keyin ushbu pozitsiyalarning barchasi ma'lumotlar bazasi bo'ylab eng qisqa yo'l bilan juftlik bilan bog'lanadi, demak, "teng-optimal" harakatlardan tashqari, bunday yo'ldagi barcha harakatlar mukammal bo'ladi: Uaytning harakati har doim eng tezkor sherik, Blekning harakati har doim eng sekin turmush o'rtog'iga olib boradi. "^[26]

The retrograd tahlil faqat kerak matematik pozitsiyalar, chunki shashtalangan holatdan orqaga qarab o'tish mumkin bo'lmagan har bir pozitsiya durang bo'lishi kerak.^[27]

1-rasm retrograd tahlil g'oyasini aks ettiradi. Oq rang juftni 1. harakat bilan majburlab, 1-rasmni egallab, 2-rasmdagi holatga olib keladi. Ushbu pozitsiyadan qora rang uchun atigi ikkita qonuniy harakat mavjud, ikkalasi ham matga olib keladi: agar 1 ... Kb8 2. Qb7 # , va agar 1 ... Kd8 2. Qd7 # (3-rasm).

3-rasm, Uaytning ikkinchi harakatidan oldin, "birida turmush o'rtoq" deb ta'riflangan qatlam. "2-rasm, Uaytning birinchi harakatidan so'ng, Qora qanday o'ynashidan qat'i nazar," ikki qavatli juftlik "dir. Va nihoyat, 1-rasmdagi boshlang'ich pozitsiya" uch qavatli juftlik "(ya'ni ikkita harakat), chunki u to'g'ridan-to'g'ri "Ikki qavatli juftlik" deb allaqachon aniqlangan 2-rasm. Hozirgi pozitsiyani boshqa bir qatlam bilan ilgari mavjud bo'lishi mumkin bo'lgan holat bilan bog'laydigan ushbu jarayon abadiy davom etishi mumkin.

Har bir pozitsiya ma'lum miqdordagi harakatlarda yutuq yoki yo'qotish sifatida baholanadi. Retrograd tahlil yakunida yutuq yoki yo'qotish sifatida belgilanmagan pozitsiyalar albatta tortiladi.

Shakl 1 a b v d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b v d e f g h Ko'chirish uchun oq: uch qavatli juftlik (Kc6)

Shakl 2 a b v d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b v d e f g h Ko'chirish uchun qora: ikki qavatli juftlik (Kd8 yoki Kb8)

Shakl 3 a b v d e f g h 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 a b v d e f g h Ko'chirish uchun oq: bir qavatda turmush o'rtoq (Qd7)

3-qadam: Tasdiqlash

Stol bazasi yaratilgandan va har bir pozitsiya baholangandan so'ng, natijani mustaqil ravishda tekshirish kerak. Maqsad o'z-o'ziga muvofiqlik jadval bazasi natijalari.^[28]

Masalan, yuqoridagi 1-rasmda tasdiqlash dasturi "uch qavatli juftlik (Kc6)" ni baholaydi. Keyin 2-rasmdagi holatga qaraydi, keyin Kc6 va "ikki qavatli turmush o'rtog'ini" baholashni ko'radi. Ushbu ikkita baho bir-biriga mos keladi. Agar 2-rasmni baholash boshqa biron bir narsa bo'lsa, u 1-rasmga mos kelmaydi, shuning uchun jadval bazasini tuzatish kerak bo'ladi.^{[tushuntirish kerak ]}

Qo'lga olish, lombardni reklama qilish va maxsus harakatlar

To'rt qismli stol usti uchta bo'lakka asoslangan bo'lishi kerak, agar bitta bo'lak qo'lga olinsa, natijada yuzaga kelishi mumkin. Xuddi shu tarzda, garovni o'z ichiga olgan stol bazasi, keyin yangi materiallar to'plami bilan shug'ullanadigan boshqa stol bazalariga ishonishi kerak. garovni targ'ib qilish qirolichaga yoki boshqa qismga. Retrograd tahlil dasturi oldingi harakatda qo'lga olish yoki lombardni ko'tarish imkoniyatini hisobga olishi kerak.^[29]

Stol tagliklari buni taxmin qiladi kastling ikki sababga ko'ra mumkin emas. Birinchidan, amaliy so'nggi o'yinlarda bu taxmin deyarli har doim to'g'ri keladi. (Biroq, kastingga konventsiya bo'yicha ruxsat beriladi tuzilgan muammolar va tadqiqotlar.) Ikkinchidan, agar qirol va rook asl maydonlarida bo'lsa, kastingga ruxsat berilishi mumkin yoki bo'lmasligi mumkin. Ushbu noaniqlik sababli, kasting mumkin bo'lgan yoki mumkin bo'lmagan holatlar uchun alohida baholash kerak bo'ladi.

Xuddi shu noaniqlik mavjud en passant ehtimol, chunki qo'lga olish en passant raqibning avvalgi harakatiga bog'liq. Biroq, ning amaliy qo'llanmalari en passant garov o'yinlarida tez-tez uchrab turadi, shuning uchun stol tagliklari bu imkoniyatni hisobga oladi en passant ikkala tomonning kamida bitta piyoniga ega bo'lgan pozitsiyalar uchun.

Foydalanish apriori ma `lumot

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

KRP (a2) KBP (a3) ​​so'nggi o'yiniga misol. 1.Kh7 dan boshlangan 72 ta harakatdagi oq juftliklar! Boshqa Oq harakatlari durang.

Yuqorida tavsiflangan usulga ko'ra, jadval bazasi berilgan qismning 64 kvadratdan birini egallashi imkoniyatini berishi kerak. Ba'zi pozitsiyalarda, natijaga ta'sir qilmasdan qidiruv maydonini cheklash mumkin. Bu hisoblash resurslarini tejashga imkon beradi va aks holda imkonsiz bo'lgan qidiruvlarni amalga oshiradi.

Ushbu turdagi dastlabki tahlil 1987 yilda, so'nggi o'yinda nashr etilgan KRP (a2) KBP (a3), bu erda Qora episkop qorong'u kvadratlarda harakat qiladi (o'ngdagi misol holatiga qarang).^[30] Ushbu pozitsiyada biz quyidagilarni amalga oshirishimiz mumkin apriori taxminlar:

1. Agar biron bir qism ushlangan bo'lsa, biz natijani pozitsiyani beshta qism bilan mos keladigan stol tagida qidirishimiz mumkin. Masalan, agar Qora piyon qo'lga olinsa, KRPKB-da yangi yaratilgan pozitsiyani qidirib toping.
2. Oq piyon a2da qoladi; ta'qib qilish harakatlari 1-qoida bo'yicha amalga oshiriladi.
3. Qora piyon a3da qoladi; ta'qib qilish harakatlari 1-qoida bo'yicha amalga oshiriladi.^[31]

Ushbu soddalashtirishning natijasi shundaki, garovlar joylashuvi uchun 48 * 47 = 2256 ta almashtirishni qidirish o'rniga, bitta bitta almashtirish mavjud. Qidiruv maydonini 2256 marta qisqartirish tezroq hisoblashni osonlashtiradi.

Bleicher "Dondurucu" deb nomlangan tijorat dasturini ishlab chiqdi, bu foydalanuvchilarga mavjud Nalimov stol taglaridan yangi stol tagliklarini yaratishga imkon beradi. apriori ma `lumot. Dastur, ettita yoki undan ortiq qismli piyonlar bilan joylashtirilgan joylar uchun stol tayanchini ishlab chiqarishi mumkin edi, hatto etti dona stol tagliklari paydo bo'lishidan oldin.^[32]

Ilovalar

Xat yozish bo'yicha shaxmat

Kasparov vs Dunyo, 1999 yil

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

55.Qxb4 dan keyingi pozitsiya; stol tayanchlari bizga 82 ta harakatdagi Oq g'alaba haqida xabar beradi.

Yilda yozishmalar shaxmat, o'yinchi yordam uchun shaxmat kompyuteridan murojaat qilishi mumkin, agar musobaqa odob-axloq qoidalari bunga imkon bersa. Ba'zi yozishmalar tashkilotlari foydalanish qoidalarini ajratib ko'rsatishadi shaxmat dvigatellari real vaqtda pozitsiyani hisoblab chiqadigan va oldindan hisoblangan kompyuterdan foydalanadigan ma'lumotlar bazasi kompyuterda saqlanadi. Dvigateldan foydalanish taqiqlangan bo'lsa ham, jonli o'yinda so'nggi o'yin stolidan foydalanishga ruxsat berilishi mumkin. O'yinchilar shuningdek, stol tugagandan so'ng stol ustidagi o'yinlarning so'nggi o'yinlarini tahlil qilish uchun stol taglaridan foydalanganlar. Olti qismli stol bazasi (KQQKQQ) yozishmalar o'yinida yuzaga kelgan so'nggi o'yinni tahlil qilish uchun ishlatilgan Kasparov Dunyoga qarshi.^[33]

Raqobatbardosh o'yinchilar ba'zi stol tagliklari e'tiborga olinmasligini bilishlari kerak ellik harakat qoidasi. Ushbu qoidaga ko'ra, agar ellikta harakat qo'lga olinmasdan yoki garovga qo'yilmasdan o'tgan bo'lsa, har qanday o'yinchi durangga da'vo qilishi mumkin. FIDE 1974 yildan boshlab, ellikta harakat g'alaba qozonish uchun etarli bo'lmagan o'yinlar uchun yuzta harakatni amalga oshirish uchun qoidalarni bir necha bor o'zgartirdi. 1988 yilda FIDE KBBKN, KNNKP, KQKBB, KQKNN, KRBKR va KQPKQ uchun ettinchi darajadagi piyon bilan yetmish beshta harakatga ruxsat berdi, chunki stol tagliklari ushbu so'nggi o'yinlarda g'alaba qozonish uchun ellikdan ortiq harakatni talab qiladigan pozitsiyalarni topdilar. 1992 yilda FIDE ushbu istisnolarni bekor qildi va ellik harakat qoidasini asl holatiga keltirdi.^[21] Shunday qilib, stol bazasi pozitsiyani yutqazgan yoki yutqazgan holda belgilashi mumkin, agar u aslida ellik harakat qoidasi bilan belgilansa. 2013 yilda, ICCF 2014 yildan boshlab shaxmat bo'yicha sirtqi musobaqalar o'tkazish qoidalarini o'zgartirdi; olti kishilik stollar asosida o'yinchi g'alaba yoki durangni talab qilishi mumkin.^[34] Bunday holda, ellikta yurish qoidasi qo'llanilmaydi va juftlashish uchun harakatlarning soni hisobga olinmaydi.

Haworth, ellik harakat qoidalariga mos keladigan natijalar beradigan stol bazasini ishlab chiqdi. Biroq, aksariyat jadvallar bir necha yuz marta harakat qilishni talab qiladigan bo'lsa ham, majburiy turmush o'rtog'ining nazariy chegaralarini izlaydi.

Kompyuter shaxmat

Stol tagidagi ma'lumotlar kompyuterga so'nggi o'yinda juda katta ustunlik beradi. Kompyuterlar nafaqat so'nggi o'yinda mukammal o'ynay olishlari, balki murakkabroq o'yin stolidan yutuqli stol bazasini soddalashtirishlari mumkin.^[35] Ikkinchi maqsad uchun, ba'zi dasturlarda konversiya yoki turmush o'rtog'igacha harakatlarning sonisiz pozitsiyalarning o'yin-nazariy qiymatini beradigan "bitbase" ishlatiladi, ya'ni ular faqatgina pozitsiyaning yutganmi, yutganmi yoki durangligini aniqlaydilar. Ba'zan hatto bu ma'lumotlar siqiladi va bitbase faqatgina pozitsiyani yutib chiqadimi-yo'qligini aniqlaydi, yutqazilgan va durang o'yin o'rtasida farq bo'lmaydi.^[27] Masalan, shredderbases Maydalagich dastur, bitbase-ning bir turi,^[36] 157-dagi barcha 3, 4 va 5 qismli bitbazlarga mos keladiMB. Bu Nalimov stollari uchun zarur bo'lgan 7,05 Gbning shunchaki qismi.^[37] Biroz kompyuter shaxmat mutaxassislar stol stollaridan foydalanishda amaliy kamchiliklarni kuzatdilar.^[38] Ellik harakat qoidasini e'tiborsiz qoldirish bilan bir qatorda, qiyin ahvolda bo'lgan kompyuter, hatto stol bazasini o'zi bilmasdan raqib deyarli g'alaba qozona olmasa ham, stol bazasining yo'qotadigan tomonidan qochishi mumkin. Noqulay ta'sir, muddatidan oldin iste'foga chiqishi yoki stol usti bo'lmagan o'yinlarga qaraganda kamroq qarshilik ko'rsatib yutqazadigan past darajadagi o'yin bo'lishi mumkin.

Yana bir kamchilik shundaki, stol tagliklari juda ko'p narsalarni talab qiladi xotira minglab pozitsiyalarni saqlash uchun. Ilg'or dasturlardan foydalaniladigan Nalimov stollari siqilish texnikasi, 7.05 talab qiladiGB barcha 5 qismli uchlar uchun qattiq disk maydoni. 6 qismli tugatish uchun taxminan 1,2 kerakSil kasalligi.^[39][40] 7 qismli Lomonosov stol bazasi uchun 140 ta talab qilinadi Sil kasalligi saqlash maydoni.^[41] Agar ularning xotirasi oddiy qidirish va baholash funktsiyasiga bag'ishlangan bo'lsa, ba'zi kompyuterlar umuman yaxshi ishlaydi. Zamonaviy dvigatellar odatdagidek stol usti kerak bo'lmasdan (ya'ni, ufq effekti ). Faqatgina murakkab o'yin o'yinlarida stol tagliklari dvigatelning ishlashiga sezilarli ta'sir ko'rsatadi.^{[iqtibos kerak ]}

Syzygy stol tagliklari Ronald de Man tomonidan 2013 yil aprel oyida chiqarilgan bo'lib, qidiruv paytida shaxmat dasturidan foydalanish uchun optimallashtirilgan holda ishlab chiqilgan. Ushbu xilma-xillik har bir o'yin uchun ikkita jadvaldan iborat: kichikroq WDL jadvali (g'alaba / durang / yutish) jadvali, unda 50 ta harakat qoidasi va kattaroq DTZ jadvali (nol qatlamgacha bo'lgan masofa, ya'ni garovga o'tish yoki qo'lga olish). WDL jadvallari a ga sig‘adigan darajada kichkina qilib yaratilgan qattiq holatdagi haydovchi qidirish paytida tezkor kirish uchun, DTZ formasi esa root pozitsiyasida qidiruvni amalga oshirish o'rniga, g'alaba qozongan pozitsiyani saqlab, 50-harakat qoidasini tiklash uchun o'yin-nazariy jihatdan eng tez masofani tanlash uchun ishlatiladi. Syzygy stol tagliklari barcha 6 qismli uchlar uchun mavjud bo'lib, ularni hozirda Komodo, Deep Fritz, Houdini va Stockfish kabi ko'plab eng yaxshi dvigatellar qo'llab-quvvatlamoqda.^[42] 2018 yil avgust oyidan boshlab barchasi^[43] 7 qismli Syzygy stollari ham mavjud.^[44]

Stol tagliklarining hozirgi holati quyidagi jadvalda umumlashtirilgan:^[45]

Sakkiz qismli stol bazasini yaratish bo'yicha tadqiqotlar davom etmoqda. 8 kishilik so'nggi o'yinlardan birida 1000 ta harakatlanadigan turmush o'rtog'i topilishi mumkin deb taxmin qilinmoqda, ammo bu 2020 yilgacha sodir bo'lishi mumkin emas.^{[yangilanishga muhtoj ][46]} Suhbat davomida Google 2010 yilda Garri Kasparov "ehtimol" chegara 8 dona bo'lishi mumkinligini aytdi. Chunki boshlang'ich pozitsiyasi shaxmat 32 donadan iborat yakuniy o'yin bo'lib, u shaxmatni kompyuter yordamida hal qilish imkoniyati yo'qligini ta'kidladi.^[47]

Endgame nazariyasi

Lyuis Stiller, 1991 yil

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

A 262-xotin holati (harakatlanish uchun oq rang). Oq g'alaba qozonadi.

Ellik harakat qoidasini e'tiborsiz qoldirish mumkin bo'lgan sharoitda, stol bazalari ba'zi bir kombinatsiyalar g'alaba qozonganmi yoki durangmi degan savollarga javob berishdi. Quyidagi qiziqarli natijalar paydo bo'ldi:

• KBBKN - Bernxard Xorvits va Yozef Kling (1851) Blek himoyaga kirish orqali rasm chizishini taklif qildi qal'a, lekin stol tagliklari umumiy g'alabani namoyish etdi, maksimal DTC = 66 yoki 67 va maksimal DTM = 78.^[48] (Shuningdek qarang garovsiz shaxmat o'yini.)
• KNNKP - Maksimal DTC = DTM = 115 harakat.
• KNNNNKQ - ritsarlar 62,5 foiz pozitsiyalarda g'alaba qozonishadi, maksimal DTM = 85 ta harakat.^[49][50]
• KQRKQR - Materiallar tengligiga qaramay, harakatlanadigan o'yinchi pozitsiyalarning 67,74 foizida g'olib chiqadi.^[51] Maksimal DTC 92 ga, maksimal DTM esa 117 ga teng. Ushbu so'nggi o'yinda ham, KQQKQQda ham birinchi o'yinchi tekshirish odatda yutadi.^[52]
• KRNKNN va KRBKNN - Fridrix Amelung 1900-yillarda ushbu ikkita so'nggi o'yinni tahlil qilgan edi.^[53] KRNKNN va KRBKNN 78% va 95% hollarda kuchli tomon uchun qo'lga kiritildi.^[26][54] Stillerning DTC stol bazasi ushbu so'nggi o'yinlarda bir nechta uzoq muddatli g'alabalarni aniqladi. KRBKNNdagi eng uzoq yutuq DTC 223 va DTM 238 harakatga ega (ko'rsatilmagan). Bundan ham hayratlanarlisi - o'ngdagi pozitsiya, u erda Oq g'alaba qozonadi 1. Ke6! Stiller DTC-ni 243 yurish deb e'lon qildi va keyinchalik DTM 262 harakat ekanligi aniqlandi.^[55]

Bir necha yillar davomida "mate-in-200" pozitsiyasi (quyida keltirilgan birinchi diagramma) eng uzoq vaqtdan beri kompyuter tomonidan ishlab chiqarilgan majburiy turmush o'rtog'i uchun rekord o'rnatgan. (Otto Blati noqonuniy boshlang'ich pozitsiyasidan bo'lsa ham, 1889 yilda "292 ta yurishda jufti" muammosini tuzgan edi.^[56]) 2006 yil may oyida Bourzutskiy va Konoval KTNKRBN pozitsiyasini kashf etdilar, ular 517 ta harakatni hayratda qoldirdilar.^[57] Bu Stillerning maksimal darajasidan ikki baravar ko'p edi va KQBNKQB_1001 pozitsiyasi bo'yicha 330 DTC oldingi rekordidan deyarli 200 ta harakat qildi. Bourzutschkiy shunday deb yozgan edi: "Bu biz uchun katta syurpriz bo'ldi va shaxmatning murakkabligiga katta ehtirom".^[58][59] Keyinchalik, Lomonosov 7 qismli stol usti tugagandan so'ng, DTM 546 bo'lgan pozitsiya topildi (quyida uchinchi diagramma).^[60][61]

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

A 200-yilda turmush o'rtog'i holati (harakatlanish uchun oq rang). Oq piyonning birinchi harakati 119-harakatda.

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

A turmush o'rtog'i-154 holati (harakatlanish uchun qora). Qora g'alaba qozonadi.

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

A 546-yil holati (harakatlanish uchun oq rang).^[61] Lomonosovning 7 qismli stol tagida joylashuv aniqlandi. (Ushbu misolda ahamiyatsiz birinchi suratga olish bilan 8-qism o'chirilgan.)

Ko'pgina pozitsiyalar g'alaba qozonadi, garchi ular birinchi qarashda g'olib bo'lmaydigan ko'rinishga ega bo'lsa. Masalan, o'rta diagrammadagi pozitsiya - Qora uchun 154 ta yurishda yutuq (oq piyon taxminan 80 ta harakatda ushlanadi).^[62]

2006 yil avgust oyida Bourzutschkiy quyidagi etti qismli so'nggi o'yinlarni tahlil qilish natijasida dastlabki natijalarni e'lon qildi: KQQPKQQ, KRRPKRR va KBBPKNN.^[28]

Endgame tadqiqotlari

E. Pogosyants, EG 1978

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

Oynash va g'alaba qozonish uchun oq rang. Bastakor mo'ljallangan 1. Ne3 Rxh2 2. 0-0-0 #! eritmaning asosiy chizig'i sifatida, ammo jadval bazasida 1. h4 kastlingsiz g'alaba qozonishi aniqlandi.

Ko'pchilik bastakor bo'lgani uchun endgame tadqiqotlar stol tagliklarida mavjud bo'lgan pozitsiyalar bilan shug'ullanish, ularning mustahkamligini stol tagliklari yordamida tekshirish mumkin. Ba'zi tadqiqotlar stol tagliklari tomonidan isbotlangan. Buning sababi yoki bastakorning echimi ishlamagani uchun, yoki bastakor o'ylamagan bir xil darajada samarali alternativa bo'lishi mumkin. Yana bir usul stol tagliklari pishirish tadqiqotlar - bu so'nggi o'yinni baholashdagi o'zgarish. Masalan, qirolicha va yepiskop bilan ikkita rookga qarshi o'yinni durang deb o'ylashdi, ammo stol bazalari bu malika va yepiskopning yutug'i ekanligini isbotladilar, shuning uchun ushbu so'nggi o'yinga asoslangan deyarli barcha tadqiqotlar befoyda.^[63]

Masalan, Erik Pogosyants tadqiqotni o'ng tomonda tuzdi, Uayt o'ynashi va g'alaba qozonishi kerak edi. Uning mo'ljallangan asosiy chizig'i 1. Ne3 Rxh2 2. 0-0-0 #! Stol bazasi 1. h4, shuningdek, Oq uchun 33 ta harakatda g'alaba qozonishini aniqladi, garchi Qora piyonni qo'lga kiritishi mumkin bo'lsa ham (bu eng yaxshi harakat emas - garovni qo'lga kiritishda qora 21 ta harakatda, X1-g2 32 ta harakatda yutqazadi) ). Aytgancha, stol bazasi bastakorning echimini tan olmaydi, chunki u kastingni o'z ichiga oladi.^[64]

Stol tagliklari ba'zi tadqiqotlarni tayyorlagan bo'lsa-da, boshqa tadqiqotlar yaratishda yordam berishdi. Bastakorlar stol taglarini qiziqarli pozitsiyalarni qidirishlari mumkin, masalan zugzwang deb nomlangan usuldan foydalanib ma'lumotlar qazib olish. Uchdan besh qismgacha bo'lgan va oltita qismli garovsiz so'nggi o'yinlarning barchasi uchun to'liq ro'yxat o'zaro zugzvanglar jadvalga kiritilgan va nashr etilgan.^[65][66][67]

Stol bazasi yordamida tuzilgan so'nggi o'yinlarni turnirlarni tuzishga ruxsat berish to'g'risida bir nechta tortishuvlar mavjud. 2003 yilda yakuniy o'yinning bastakori va mutaxassisi Jon Roykroft munozarani umumlashtirdi:

[N] ot faqat fikrlar bir-biridan farq qiladi, lekin ular tez-tez qat'iy, qat'iyan qat'iy rioya qilinadi: bir tomondan, biz kompyuterdan foydalanilganligiga hech qachon amin bo'lmasligimiz uchun, uni ajratishga urinish befoyda, degan fikr. "o'rganish" ni kelib chiqishi haqida ma'lumot bermasdan, uning mazmuni bo'yicha baholashi kerak; Boshqa tomondan, "sichqoncha" yordamida kompyuterda tayyor bo'lgan ro'yxatdan qiziqarli pozitsiyani ko'tarish hech qanday ma'noga ega emas, shuning uchun biz har bir pozitsiyani noqonuniy deb hisoblashimiz kerak.^[68]

Roykroftning o'zi ham ushbu yondashuvga rozi. U davom ettiradi: "Biz uchun bitta narsa aniq: mumtoz kompozitsiya va kompyuter kompozitsiyasi o'rtasidagi farqni iloji boricha uzoq vaqt davomida saqlab qolish kerak: agar o'quv diagrammasi bilan bog'liq bo'lgan ism bo'lsa, bu nom mualliflik da'vosidir".^[68]

Xarold van der Heijden, 2001 yil

	a	b	v	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	v	d	e	f	g	h

Oynash va chizish uchun oq rang

Mark Dvoretskiy, an Xalqaro usta, shaxmat bo'yicha murabbiy va muallif ko'proq maqbul pozitsiyani egalladi. U 2006 yilda bir tadqiqotga izoh bergan Xarold van der Heijden, 2001 yilda nashr etilgan, uchta kirish harakatlaridan so'ng darhol pozitsiyaga erishdi. Oq uchun chizilgan harakat 4. Kb4 !! (va 4. Kb5 emas), keyinchalik uchta harakat sodir bo'lishi mumkin bo'lgan o'zaro zugzvanga asoslangan.

Dvoretskiy sharhlar:

Mana, bitta nozik savolga to'xtalib o'tishimiz kerak. Ishonchim komilki, ushbu noyob so'nggi o'yin pozitsiyasi Tompsonning taniqli kompyuter ma'lumotlar bazasi yordamida topilgan. Bu bastakorning yutug'ini pasaytiradigan "nuqson" emasmi?

Ha, kompyuter ma'lumotlar bazasi bugungi kunda hamma uchun mavjud bo'lgan vosita. Shubhasiz, biz yana o'ziga xos pozitsiyalarni ajratib olishimiz mumkin edi - buni muntazam ravishda bajaradigan ba'zi shaxmat kompozitorlari bor. Bu erda baholash standarti erishilgan natija bo'lishi kerak. Shunday qilib: o'tkir g'oyalar mazmuniga emas, balki murakkab kompyuter tahliliga asoslangan mo''jizalar, ehtimol, faqat ba'zi estetlarga qiziqish uyg'otadi.^[69]

"Xudo bilan shaxmat o'ynang"

Ustida Bell laboratoriyalari veb-sayt, Ken Tompson bir marta o'zining jadval bazasidagi ba'zi ma'lumotlarga havolani saqlab qoldi. Bu sarlovhasi “Xudo bilan shaxmat o‘ynang”.^[70]

Stillerning uzoq g'alabalari haqida Tim Krabbe shunga o'xshash yozuvni urdi:

Grossmeyster bu so'nggi o'yinlarda kecha shaxmatni o'rgangan odamdan yaxshiroq bo'lolmaydi. Bu shaxmat bilan hech qanday aloqasi bo'lmagan shaxmat, biz hech qachon kompyuterlarsiz tasavvur qilib bo'lmaydigan shaxmat. Stiller harakatlari dahshatli, deyarli qo'rqinchli, chunki ular haqiqat ekanligini bilasiz, Xudoning algoritmi - bu Hayotning ma'nosi ochilganga o'xshaydi, lekin siz bitta so'zni tushunmaysiz.^[26]

Nomenklatura

Dastlab, so'nggi o'yin jadval bazasi "so'nggi o'yin ma'lumotlar bazasi" yoki "so'nggi o'yin ma'lumotlar bazasi" deb nomlangan. Bu ism ikkalasida ham paydo bo'ldi EG va ICCA jurnali 1970-yillardan boshlab, ba'zan esa bugungi kunda ishlatiladi. Xovortning so'zlariga ko'ra ICCA jurnali birinchi marta "stol bazasi" so'zini shaxmat o'yinlari bilan bog'liq holda 1995 yilda ishlatgan.^[71] Ushbu manbaga ko'ra, jadval bazasida to'liq ma'lumotlar to'plami mavjud, ammo ma'lumotlar bazasida ba'zi ma'lumotlar etishmasligi mumkin.

Xavort "Endgame Table" atamasini afzal ko'radi va uni mualliflik qilgan maqolalarida ishlatgan.^[72] Roykroft o'z jurnalida "Oracle ma'lumotlar bazasi" atamasidan foydalangan, EG.^[73] Shunga qaramay, asosiy shaxmat jamoatchiligi "endgame tablebase" ni eng keng tarqalgan nom sifatida qabul qildi.

Kitoblar

Jon Nunn so'nggi o'yin stollarini batafsil tahlil qilish asosida uchta kitob yozgan:

• Nunn, Jon (1995). Sirlari Kichik qism Tugatishlar. Batsford. ISBN  0-8050-4228-8.
• Nunn, Jon (1999). Sirlari Rook Tugatishlar (2-nashr). Gambit nashrlari. ISBN  1-901983-18-8.
• Nunn, Jon (2002). Sirlari Garovsiz oxirlar (2-nashr). Gambit nashrlari. ISBN  978-1-901983-65-4.

Jadvallar

Etti qismli so'nggi o'yinlar

Hujum qilish	Parchalarni himoya qilish	Eng uzoq g'alaba
		476
		380
		400
		186
		143
		140
		549
		260
		201
		143
		211
		211
		298
		261
		293
		217
		224
		259
		228
		297
		176
		182
		184
		296
		269
		191
		104
		79
		92
		189
		77
		88
		70
		98
		262
		246
		246
		238
		105
		149
		140
		232
		86
		102
		210
		176
		304
		152
		262
		212
		84
		134
		112
		117
		122
		182
		120
		195
		229
		150
		192
		176
		197
		545
		169
		106
		115
		154
		141
		94
		141
		107
		247
		213
		184
		239
		192
		297

Shuningdek qarang

• Kompyuter shaxmat
• EG jurnal
• Shannon raqami
• Shaxmatni echish
• Zobristni xeshlash

Izohlar

Adabiyotlar

• Levi, Dovud; Yangi tug'ilgan, Monti (1991). Kompyuterlar shaxmatni qanday o'ynaydi. Kompyuter fanlari matbuoti. ISBN  0-7167-8121-2.
• Nunn, Jon (2002). Garovsiz tugash sirlari (ikkinchi nashr). Gambit nashrlari. ISBN  1-901983-65-X.
• Stiller, Lewis Benjamin (1995). "Exploiting symmetry on parallel architectures" (PDF). PhD Thesis, Johns Hopkins University. Arxivlandi asl nusxasi (PDF) 2007 yil 30 sentyabrda. Olingan 4 may 2007.

Tashqi havolalar

• Guide to the use of Computer Chess Endgame Tablebases by Aaron Tay
• Downloading tablebases
  • Torrent site for Gaviota, Scorpio, and Syzygy 3,4,5 and 6-men EGTB's
  • Torrent for Nalimov Tablebases (3+4+5+6) complete
  • Distribution site for tablebases up to six pieces
  • 3-4-5 pieces kuni Robert Hyatt's FTP site
• Querying tablebases on the web
  • Web query server for Nalimov tablebases by Eiko Bleicher (up to six pieces)
  • Web query server for Nalimov tablebases at ChessOK (up to six pieces)
  • Web query server for Nalimov tablebases by Lokasoft (up to six pieces)
  • Web query server for Syzygy tablebases by Niklas Fiekas (up to seven pieces)
• Maximal positions, i.e. longest DTM positions for endgames with up to five pieces and some with six pieces, compiled by Kirill Kryukov