Як все починалося
Все почалося з лекції в Берліні в Університеті ім. Гумбольдта, прочитаної в листопаді 1960. У січні 1961 в скороченому вигляді вона була опублікована в «Комсомольській правді» під назвою — «Люди і машини за шахівницею» (у повному обсязі — через місяць в журналі «Шахи в СРСР»).
Наводжу найбільш істотні моменти цієї лекції:
«… Розглянемо процес мислення шахіста. Кожен знає, що ніколи шахіст не розраховує всі можливі варіанти, не дивиться всі ходи, можливі на дошці … Шахіст під час партії в даній позиції, яку він обмірковує, розглядає приблизно 2-4 ходу ; визначає Онет ходи інтуїтивно, на підставі досвіду тощо Якщо врахувати, що в середньому партія триває ходів сорок, то приблизно за партію шахіст повинен проаналізувати не більше 100 перших ходів … Зрозуміло, шахіст в процесі розрахунку в цілому розглядає не 100 ходів під час партії, а аналізує незрівнянно більше. Якщо в середньому варіант розглядається ходу на 2-3, то і тоді цифра аналізованих ходів виходить досить значна.
Смотрите также:мужские футболки оптом
Слід врахувати, що шахіст під час розрахунків не бачить всієї дошки з 64 полями. Це істотно полегшує аналіз під час партії. Одночасно шахіст має в полі зору, скажімо, полів 8-16, тобто завдання аналізу полегшується в кілька разів. Треба відзначити також, що на деякі фігури шахіст не звертає уваги. Із загального числа в розрахунку беруть участь 3-6 фігур. Нове полегшення завдання. Таким чином, під час партії шахіст аналізує пересування обмеженої кількості фігур на обмеженій ділянці дошки, аналізує пересування лише тих постатей, які безпосередньо беруть участь у сутичках, і лише на тих полях, де ці зіткнення можливі. Інакше кажучи, він розглядає лише ті фігури, що безпосередньо взаємодіють з ворожими, і лише ті поля, де це взаємодія можливо. Але як перевірити, чи правильно вибрані ці фігури і ці поля? Для цього, мабуть, є один спосіб. Назвемо цей метод умовно «методом послідовних наближень». Майстер вибирає хід, аналізує його; якщо в процесі аналізу включаються в гру нові фігури і поля, то зібрана інформація використовується при повторному розгляді і т.д. Аналіз, повторений кілька разів, дозволять в достатній (або, на жаль, недостатньою) точністю визначити ці взаємодіючі фігури і поля — тоді вже розрахунок проводиться начисто «.
Найголовніше, що містилося лекції:
шахіст, коли вважає варіанти, «бачить лише частину фігур і частину дошки;
у варіантах міститься невелика кількість ходів
шахіст діє методом послідовних наближень.
На формалізацію та реалізацію цих простих ідей пішли роки. Зробити крок від майстра до машини виявилося справою складним: треба було знайти шлях до формування невеликого дерева перебору.
Мета неточною гри
На знаходження мети неточною гри пішло три з половиною роки. Мат — мета точної гри; мета досягнута — гра закінчена. А як же в аналізі усіченого дерева? Там мета точної гри (мат) марна, як правило, варіанти в усіченому дереві не можуть бути завершені через мату. У всіх граючих програмах (крім «Піонера») цілі неточною гри немає. Це призводить до того, що усеченное дерево, містить в основному, сміття, так як варіанти обриваються не по змістом, а по досягненні граничної довжини. Отже, при формуванні усіченого дерева повинна діяти мета неточною гри.
У шахах мета неточною гри — виграш матеріалу. За типом це буде та ж мета, що і точна (мат). У 1964 році я знайшов, що в шахах все починається з нападу на фігури противника, з виграшу матеріалу. Але ж траєкторій, за якими можна напасти на фігури супротивника безліч! Як обмежити інформацію про це?
Шаховий горизонт
Горизонт — це гранично допустимий час в полуходах, яке дано для взяття ворожої фігури. Таким чином, горизонт лімітує час пересування фігури по траєкторії до кінцевого полю цієї траєкторії, інакше кажучи горизонт лімітує кількість пересувань фігури за її траєкторії. В середині гри горизонт шахового майстра дорівнює приблизно 4 полуходам (траєкторія з двох пересувань) — фігур багато, цілей (мішеней) — багато, горизонт повинен бути невеликим, і кількість мішеней, які майстер враховує, скорочується. В ендшпілі фігур мало, горизонт повинен зростати (особливо з розміном далекобійних фігур), що сприяє підтримці розумного числа нападів.
Оціночна функція
Зазвичай математики використовують при формуванні дерева тільки оцінну функцію, нехтуючи метою неточною гри. Мушу зізнатися, що сам змішував ці два поняття, які не вбачаючи між ними будь-якої різниці. А відмінність є, і досить істотне.
Функція оцінки дозволяє підрахувати результат гри в кожному вузлі дерева перебору, в тому числі і в кінцевому вузлі варіанту перебору. Можна сказати, що функція оцінки дозволяє оцінити, наскільки добре (або погано) досягнута у варіанті мета гри. Оптимальний же варіант, який визначається мінімаксної процедурою, що грунтується на значеннях оціночної функції в кінцевих вузлах варіантів перебору, дає можливість оцінити досягнення мети у всьому обсязі дерева перебору.
Коли є в програмі лише оцінна функція, обірвати і відсікти варіанти логічно, визначити логічне напрямок руху фігур немає можливості. Тоді й тривають всі варіанти до граничної довжини … Деякі фахівці стверджують, що мета гри полягає в максимізації оціночної функції — це камуфляж відсутності мети. Максимізація оціночної функції всього лише елемент мінімаксної процедури, і не більше! Без мети гри невелике, «людське» дерево перебору не сформована.
Многоступенчатость
Коли мета неточною гри є, вирішальний вплив на розмір дерева надає многоступенчатость досліджуваної системи. Якщо розглядати шахову гру як єдине ціле, як єдину систему, то невеликого дерева не сформіруешь. Можна вважати, що шаховий майстер сприймає шахи як триступеневу систему управління.
Нижчі щаблі (1) з’єднуються в середні (2), а потім — в єдину вищу (3). Це вельми вигідна справа в порівнянні з єдиної, одноступінчатої — системою — з точки зору пошуку рішення. Єдину систему і потрібно аналізувати. А коли система багатоступенева, можна лавірувати. Шахівниця замінюється її математичним відображенням (МО), моделлю, яка і підлягає аналізу. У цей МО ми вже можемо включати не всі перші щаблі й не всі другі сходинки, а лише ті щаблі, що можуть вплинути на вибір ходу (прийняття рішення). Це призводить до додаткового скорочення дерева перебору.
Першою сходинкою шахової системи управління є фігура, атакуюча по траєкторії нападу ворожу фігуру. Перший ступінь сама по собі є елементарною системою управління, і в неї повинна бути мета гри — в даному випадку метою гри є виграш ворожої фігури (мішені). Це було встановлено в 1964 році. З цього моменту, до формалізації другого ступеня — зони гри — пішло довгих п’ять років …
Щоб зрозуміти суть справи, досить ознайомитися з зоною нападу. У зону входить атакуюча фігура (+) з траєкторією нападу (ця траєкторія названа комлевой), атакована фігура (-) — вони входять в першу щабель, а також дві «команди» заперечують фігур різного кольору, що діють по траєкторіях заперечення. Фігури (+) підтримують дії комлевой (атакуючої) фігури, фігури (-) — перешкоджають діям фігур (+). Заперечують фігури (+) знаходяться на відстані всього в одне пересування від кінцевих полів своїх траєкторій. Вони знаходяться в засідці і не мають права рухатися вперед, так як прийнято, що лише одна фігура (комльовая) сторони (+) переміщається по комлевой траєкторії у напрямку до своєї мети (мішені). Поки ж рухається комльовая фігура (+), можуть переміщатися заперечують фігури (-), але чим ближче комльовая фігура до своєї мети, тим менше часу залишається для фігур (-), щоб поспіти до кінцевих полях своїх траєкторій. Це призводить до того, що «горизонт» для заперечують фігур (-), який визначають фігури (-), що беруть участь в зоні (на відміну від граничного «горизонту» для комлевой фігури), є величиною змінною. Найвище значення цього змінного горизонту Нх пов’язано зі значенням граничного горизонту, якому був привласнений індекс НL.
Таким чином, друга ступінь-зона гри — виявилася строго детермінованою, що і дозволило згодом представити утворення зони у вигляді програми для ЕОМ. Третій, найвищий ступінь — МО була введена в алгоритм тоді ж, але формалізована була значно пізніше — через 9 років, та й то після того, як вже більше 5 років тривала робота над програмою. За цим датам можна судити про те, яка щабель триступеневої шахової моделі гри виявилася складніше: на першу пішло 3,5 роки, на другому — 5 років, а на МО — близько 9.
Триєдиний принцип
В основі алгоритму лежить триєдиний принцип включення фігур у гру: включаються лише ті фігури, з якими пов’язана надія, на те, що ці фігури своєчасно візьмуть участь у грі і що це може призвести до кращих результатів за матеріалом. Отже, надія на своєчасність і найбільший виграш. Якщо перший і другий ступені формуються лише з урахуванням своєчасності, то дозвіл на їх формування і включення в МО відбувається з урахуванням можливого поліпшення результатів перебору. За цим совмещенному принципом відбувається формування МО моделі шахової гри.
Початок роботи
У січні 1972 року почалася безпосередньо робота над написанням програми. Два програміста — Борис Штільман і Олександр Юдін почали з написання підпрограми пошуку ходу в оригінальній позиції і створення бібліотеки дебютів. Через кілька місяців програма вже знаходила траєкторії пересування фігур. Почалася робота по створенню бібліотеки ендшпіля. Після усунення поточних помилок була створена підпрограма отримання зони гри.
Далі буде …
Автор: Михайло Мойсейович Ботвинник