Оцінювальна функція

Оцінювальна функція, також відома як функція евристичної оцінки або функція статичної оцінки — це функція що використовується ігровими комп'ютерними програмами для оцінки цінності або якості позиції (зазвичай у листовому чи термінальному вузлі) у дереві гри.[1] Найчастіше значення є дійсним числом, або квантованим цілим числом, часто це може бути n-та частка вартості ігрової фігури, наприклад, це може бути камінь в ґо або пішак в шахах, де n може бути десятою, сотою або іншою зручною часткою, але іноді цінність представляють у вигляді масиву із трьох чисел в одиничному інтервалі, які відповідають відсотку виграшу, нічиєї та програшу у цій позиції.

Для нерозв'язних задач не існує аналітичних або теоретичних моделей для оцінювальних функцій, як і повністю ситуативних функцій. Склад оцінювальних функцій визначається емпірично, шляхом вставки функції-кандидата в автомат і оцінки її подальшої ефективності. Зараз для декількох ігор, таких як шахи, сьоґі та ґо, існує значна кількість доказів щодо загального складу їх оцінювальних функцій.

Ігри, у яких комп'ютерні програми для гри використовують оцінювальні функції, включають шахи,[2] ґо,[2] сьоґі,[2] отелло, гекс, нарди[3] і шашки.[4][5] Крім того, з появою таких програм, як MuZero[en], комп'ютерні програми використовують функції оцінки гри у відеоіграх, наприклад, від Atari 2600.[6] Деякі ігри, такі як хрестики-нулики, є строго вирішуваними[en] та не потребують пошуку чи оцінки, тому, що для них доступне дискретне дерево рішень.

Відношення до пошуку

Дерево таких оцінок є частиною алгоритму пошуку, такого як дерево пошуку Монте-Карло або мінімаксний алгоритм, типу альфа-бета-пошуку. Вважається, що значення є відносною ймовірністю виграшу, якщо дерево гри буде розгорнуто від цього вузла до кінця гри. Функція розглядає лише поточну позицію (тобто, на яких місцях знаходяться фігури та який їх взаємозв'язок один з одним) і не бере до уваги історію позиції, не досліджує можливі переміщення вперед від вузла (тому вона статична). Це означає, що для динамічних позицій, де існують тактичні загрози, функція оцінки не буде точною оцінкою. Такі позиції називають неспокійними; вони вимагають, принаймні, обмеженого розширення пошуку, яке називається пошуком спокою[en], для усунення загроз перед оцінкою. Деякі значення, що повертаються оцінювальними функціями, є абсолютними, а не евристичними, якщо на вузлі відбувається виграш, поразка чи нічия.

Існує складний взаємозв'язок між пошуком і знанням у оцінювальній функції. При більш глибокому пошуку перевага в оцінці віддається менш близьким тактичним факторам і більш тонким позиційним мотивам довгого горизонту. Існує також компроміс між ефективністю закодованих знань та обчислювальною складністю: обчислення детальних знань може зайняти так багато часу, що продуктивність знижується, тому часто краще отримати наближення до точних знань. Оскільки оцінювальна функція залежить від номінальної глибини пошуку, а також від розширень і скорочень, що використовуються при пошуку, не існує загального чи окремого формулювання для оцінювальної функції. Оцінювальну функцію, яка добре працює для одного додатку, зазвичай потрібно буде значно переналаштувати або перенавчати, щоб вона ефективно працювала в іншому додатку.

У шахах

У шахах оцінювальна функція зазвичай дає на виході ціле число, а одиниці оцінювальної функції зазвичай називаються пішаками. Термін «пішака» відноситься до значення, коли гравець має на одного пішака більше, ніж у суперника на позиції, як пояснюється в статті «відносне значення шахової фігури[en]». Ціле число 1 зазвичай представляє деяку частку пішака, а в комп'ютерних шахах зазвичай використовуються центи пішака, які складають соту частку пішака. Великі оцінки вказують на матеріальний дисбаланс чи позиційну перевагу або на те, що матеріальний виграш зазвичай неминучий. Дуже великі оцінки можуть свідчити про те, що мат неминучий. Функція оцінки також неявно кодує значення права на хід, яке може змінюватись від невеликої частки пішака до виграшу або програшу.

Ручні оціночні функції

Історично склалося так, що в комп'ютерних шахах складові оцінювальної функції конструюються (тобто створюються вручну) розробником рушія, а не виявляються в процесі навчання нейронних мереж. Загальний підхід до побудови створених вручну оцінювальних функцій полягає в лінійній комбінації різних зважених умов, які впливають на цінність значення позиції. Однак не всі умови у створеній вручну функції оцінки є лінійними, деякі, наприклад, безпека короля та структура пішака, є нелінійними. Кожна умова може вважатися складеною із факторів першого порядку (ті, які залежать лише від простору та будь-якої фігури на ньому), факторів другого порядку (простір по відношенню до інших просторів) і факторів n-го порядку (залежно від історії позиції).

Функція оцінки, створена вручну, зазвичай містить термін матеріального балансу, який зазвичай домінує в оцінці. Звичайні значення[en], що використовуються для матеріального балансу: Королева=9, Тури=5; Кінь або Офіцер=3; Пішак=1; королю призначається довільно велике значення, зазвичай більше, ніж загальна вартість решти фігур.[1] Крім того, у функції, як правило, є набір позиційних умов, які зазвичай не перевищують значення пішака, хоча в деяких позиціях позиційні умови можуть бути набагато більшими, наприклад, коли мат неминучий. Створені вручну функції оцінки зазвичай містять від десятків до сотень окремих умов.

Насправді ефективні ручні функції оцінки створюються не шляхом постійного розширення списку оцінюваних параметрів, а шляхом ретельного налаштування або навчання ваг щодо один одного, скромного набору параметрів, таких як описані вище. Для цього використовуються позиції з різних баз даних, наприклад, з ігор майстрів, рушіїв ігор, ігор Lichess або навіть із самостійної гри, як у навчанні з підкріпленням.

Приклад

Приклад створеної вручну функції оцінки для шахів може виглядати так:

  • c1 * матеріал + c2 * мобільність + c3 * безпека короля + c4 * контроль центру + c5 * пішакова структура + c6 * тропізм короля + . . .

Кожна з умов є вагою, помноженою на коефіцієнт різниці: значення матеріальних чи позиційних умов білих мінус значення умов чорних.

  • Матеріальна умова отримується шляхом присвоєння вартості у пішаках-одиницях кожної з фігур.
  • Мобільність — це кількість законних ходів, доступних гравцю, або, альтернативно, сума кількості місць, атакованих або захищених кожною фігурою, включаючи місця, зайняті дружніми чи протилежними фігурами. Також може бути взята до уваги ефективна мобільність або кількість «безпечних» місць, куди може переміститися фігура.
  • Безпека короля — це набір бонусів та штрафів, що нараховуються за розташування короля та конфігурації пішаків і фігур, що прилягають до короля або перед ним, а також протилежних фігур, що прилягають на місцях навколо короля.
  • Контроль у центрі визначається тим, скільки пішаків і фігур займають або коштують на чотирьох центральних місцях, а іноді й на 12 місцях розширеного центру.
  • Пішакова структура — це набір штрафів і бонусів за різні сильні та слабкі сторони пішакової структури, наприклад, штрафи за здвоєні та ізольовані пішаки.
  • Тропізм короля — це бонус за близькість (або штраф за відстань) певних фігур, особливо королев і лицарів, до короля супротивника.

Нейронні мережі

Хоча нейронні мережі застосовуються в функціях оцінки шахових рушіїв з кінця 1980-х років,[7][8] в комп'ютерних шахах вони стали популярними лише наприкінці 2010-х років, оскільки апаратне забезпечення, необхідне для навчання нейронних мереж, на той час було недостатньо потужним, а алгоритми швидкого навчання, топології та архітектури мереж ще не були розроблені. Спочатку функції оцінки на основі нейронної мережі, зазвичай, складалися з однієї нейронної мережі для всієї функції оцінки, з вхідними характеристиками, обраними з дошки, та вихідним результатом є ціле число, нормоване[en] на шкалу ста пішаків, так, що значення 100 приблизно еквівалентне матеріальній перевазі в одного пішака. Параметри в нейронних мережах зазвичай навчаються за допомогою навчання з підкріпленням або керованого навчання. Останнім часом у функції оцінювання в комп'ютерних шахах почали використовувати декілька нейронних мереж, причому кожна нейронна мережа для певної частини оцінювання, наприклад, структури пішака або ендшпілю. Це дозволяє застосовувати гібридні підходи, коли функція оцінки складається як із нейронних мереж, так і зі створених власноруч умов.

Глибокі нейронні мережі стали використовуватися, хоч і нечасто, в комп'ютерних шахах після того, як роботи Метью Лая Жирафа[9] у 2015 році та Deepmind AlphaZero у 2017 році продемонстрували можливість застосування глибоких нейронних мереж у функції оцінки. Незабаром після цього був запущений проєкт розподілених обчислень Leela Chess Zero для спроби відтворити[en] результати роботи Deepmind AlphaZero. Крім розміру мереж, нейронні мережі, що використовуються в AlphaZero та Leela Chess Zero, також відрізняються від тих, що використовуються у традиційних шахових рушіях, оскільки вони мають два виходи: один для оцінки (заголовок значення) і один для впорядкування ходів (голова політики), а не лише один вихід для оцінки.[10] Хоча в нейронній мережі Leela можна встановити вихід голови значень на дійсне число, щоб наблизити шкалу сотої пішки, яка використовується в традиційних шахових рушіях, за замовчуванням на виході стоїть відсоток перемоги-нічиєї-поразок, вектор із трьох значень з одиничного інтервалу.[10] Оскільки глибокі нейронні мережі дуже великі, рушіям, що використовують глибокі нейронні мережі у своїй функції оцінки, зазвичай вимагають графічного процесора для ефективного обчислення.

Квадратні таблиці

Важливим методом оцінки вартості, принаймні, з початку 1990-х років є використання квадратних таблиць.[11][12] Кожна таблиця являє собою набір із 64 значень, що відповідають квадратам дошки для шахів. Найбільш базова реалізація штучної квадратної таблиці складається з окремих таблиць для кожного типу фігур для кожного гравця, що в шахах призводить до 12 таблиць. У комп'ютерних шахах використовуються складніші варіанти квадратних таблиць, одним із найвідоміших є таблиця з «король-кусок-квадрат», яка використовується в Stockfish, Komodo Dragon[en], Ethereal та багатьох інших рушіях, де кожна таблиця враховує позицію кожного типу фігури стосовно короля гравця, а не позицію кожного типу фігури окремо. Значення в таблицях є бонусами/штрафами за розташування кожної фігури на місці та кодують сукупність багатьох тонких факторів, які важко кількісно оцінити аналітично. У створених своїми руками функціях оцінювання, іноді є два набори таблиць: одна для початку/мідлшпілю, а друга для ендшпілю; позиції середньої гри інтерполюються між ними.[13]

Найпоширенішою функцією оцінки створеною власноруч, що використовується в комп'ютерних шахах, є тільки «фігура-квадрат» таблиця, яка є дуже простою функцією оцінки, що складається з матеріальних умов і лише двох наборів таблиць квадратних фігур, один для відкриття (дебюту), а другий для ендшпілю, для позиційних термів. Проте, вона здатна працювати не гірше багатьох інших власноручних функцій оцінки, що використовуються в комп'ютерних шахах. Квадратна таблиця вперше була створена Томашем Міхнєвським у 2003 році під назвою «Спрощена функція оцінки». Поточну назву ввів Рональд Фрідріх, коли він реалізував її у своєму рушії rofChade.[14]

Спочатку розроблена в комп'ютерному сьоґі у 2018 році Ю Насу,[15][16] найпоширеніша функція оцінки, яка використовується сьогодні в комп'ютерних шахах, є нейронна мережа, яка ефективно оновлюється[en], або розріджена і неглибока нейронна мережа, яка має квадратні таблиці як входи в нейронну мережу.[17] Фактично, найпростіша архітектура — це просто описані вище таблиці з 12 квадратів, нейронна мережа лише з одним шаром і без функцій активації. Архітектура нейронної мережі, яка ефективно оновлюється, з використанням таблиць «король-кусок-квадрат» в якості вхідних даних, була вперше перенесена на шахи в похідній Stockfish під назвою Stockfish NNUE, публічно опублікована 30 травня 2020 року[18] і була прийнята багатьма іншими рушіями раніше ніж її було включено в офіційний рушій Stockfish, 6 серпня 2020 року.[19][20]

Бази таблиць для ендшпілю

Шахові рушії часто використовують базу таблиць ендшпілю у своїй функції оцінки, оскільки це дозволяє рушію ідеально грати в ендшпілі.

В ґо

Історично, оцінювальні функції в ґо враховували як контрольовану територію, вплив каменів, кількість ув'язнених, так і життя та смерть груп на дошці. Однак, сучасні комп'ютерні програми для гри в ігри, такі як AlphaGo, Leela Zero, Fine Art[en] і KataGo, здебільшого використовують глибокі нейронні мережі у своїх оцінювальних функціях і виводять відсоток виграшу/нічиєї/програшу, а не значення кількості каменів.

Див. також

Примітки

  1. ↑ а б Shannon, Claude (1950), Programming a Computer for Playing Chess (PDF), Ser. 7, т. 41, № 314, Philosophical Magazine, процитовано 12 грудня 2021
  2. ↑ а б в Silver, David; Hubert, Thomas; Schrittwieser, Julian; Antonoglou, Ioannis; Lai, Matthew; Guez, Arthur; Lanctot, Marc; Sifre, Laurent; Kumaran, Dharshan (7 грудня 2018). A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science. 362 (6419): 1140—1144. Bibcode:2018Sci...362.1140S. doi:10.1126/science.aar6404. PMID 30523106.
  3. ↑ Tesauro, Gerald (March 1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM. 38 (3): 58—68. doi:10.1145/203330.203343. Процитовано 1 листопада 2013.
  4. ↑ Schaeffer, J.; Burch, N.; Y. Björnsson; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). Checkers is Solved (PDF). Science. 317 (5844): 1518—22. doi:10.1126/science.1144079. PMID 17641166.
  5. ↑ Schaeffer, J.; Björnsson, Y.; Burch, N.; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. Solving Checkers (PDF). Proceedings of the 2005 International Joint Conferences on Artificial Intelligence Organization.
  6. ↑ Schrittwieser, Julian; Antonoglou, Ioannis; Hubert, Thomas; Simonyan, Karen; Sifre, Laurent; Schmitt, Simon; Guez, Arthur; Lockhart, Edward; Hassabis, Demis (2020). Mastering Atari, Go, chess and shogi by planning with a learned model. Nature. 588 (7839): 604—609. arXiv:1911.08265. Bibcode:2020Natur.588..604S. doi:10.1038/s41586-020-03051-4. PMID 33361790.
  7. ↑ Thurn, Sebastian (1995), Learning to Play the Game of Chess (PDF), MIT Press, процитовано 12 грудня 2021
  8. ↑ Levinson, Robert (1989), A Self-Learning, Pattern-Oriented Chess Program, т. 12, № 4, ICCA Journal
  9. ↑ Lai, Matthew (4 вересня 2015), Giraffe: Using Deep Reinforcement Learning to Play Chess, arXiv:1509.01549v1, процитовано 12 грудня 2021
  10. ↑ а б Neural network topology. lczero.org. Процитовано 12 грудня 2021.
  11. ↑ Beal, Don; Smith, Martin C., Learning Piece-Square Values using Temporal Differences, т. 22, № 4, ICCA Journal
  12. ↑ Jun Nagashima; Masahumi Taketoshi; Yoichiro Kajihara; Tsuyoshi Hashimoto; Hiroyuki Iida (2002), An Efficient Use of Piece-Square Tables in Computer Shogi, Information Processing Society of Japan
  13. ↑ Stockfish Evaluation Guide, процитовано 12 грудня 2021
  14. ↑ Ronald Friederich (4 січня 2020). PeSTO: Piece Square Tables Only. Процитовано 12 грудня 2021.
  15. ↑ Yu Nasu (28 квітня 2018). Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (PDF) (Japanese) .
  16. ↑ Yu Nasu (28 квітня 2018). Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (Unofficial English Translation) (PDF). GitHub (English) .
  17. ↑ Gary Linscott (30 квітня 2021). NNUE. GitHub. Процитовано 12 грудня 2020.
  18. ↑ Noda, Hisayori (30 травня 2020). Release stockfish-nnue-2020-05-30. Github. Процитовано 12 грудня 2021.
  19. ↑ Introducing NNUE Evaluation. 6 серпня 2020.
  20. ↑ Joost VandeVondele (25 липня 2020). official-stockfish / Stockfish, NNUE merge. GitHub.

Джерела

  • Slate, D and Atkin, L., 1983, «Chess 4.5, the Northwestern University Chess Program» у шаховій майстерності в людині та машині, 2-е видання, стор. 93–100. Springer-Verlag, Нью-Йорк, Нью-Йорк.
  • Ebeling, Carl, 1987, All the Right Moves: A VLSI Architecture для шахів (ACM Distinguished Dissertation), стор. 56–86. MIT Press, Кембридж, Массачусетс

Посилання