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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

Відношення до пошуку[ред. | ред. код]

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

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

У шахах[ред. | ред. код]

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

Ручні оціночні функції[ред. | ред. код]

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

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

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

Приклад[ред. | ред. код]

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

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

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

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

Нейронні мережі[ред. | ред. код]

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

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

Квадратні таблиці[ред. | ред. код]

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


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

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

Бази таблиць для ендшпілю[ред. | ред. код]

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

В ґо[ред. | ред. код]

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. а б Shannon, Claude (1950). Programming a Computer for Playing Chess. Ser. 7 41 (314). Philosophical Magazine. Процитовано 12 December 2021. 
  2. а б в Silver, David; Hubert, Thomas; Schrittwieser, Julian; Antonoglou, Ioannis; Lai, Matthew; Guez, Arthur; Lanctot, Marc; Sifre, Laurent та ін. (7 December 2018). A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362 (6419): 1140–1144. Bibcode:2018Sci...362.1140S. PMID 30523106. doi:10.1126/science.aar6404.  Проігноровано невідомий параметр |doi-access= (довідка);
  3. Tesauro, Gerald (March 1995). Temporal Difference Learning and TD-Gammon. Communications of the ACM 38 (3): 58–68. doi:10.1145/203330.203343. Процитовано Nov 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. Science 317 (5844): 1518–22. PMID 17641166. doi:10.1126/science.1144079. 
  5. Schaeffer, J.; Björnsson, Y.; Burch, N.; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. Solving Checkers. 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 та ін. (2020). Mastering Atari, Go, chess and shogi by planning with a learned model. Nature 588 (7839): 604–609. Bibcode:2020Natur.588..604S. PMID 33361790. arXiv:1911.08265. doi:10.1038/s41586-020-03051-4. 
  7. Thurn, Sebastian (1995). Learning to Play the Game of Chess. MIT Press. Процитовано 12 December 2021. 
  8. Levinson, Robert (1989). A Self-Learning, Pattern-Oriented Chess Program 12 (4). ICCA Journal. 
  9. Lai, Matthew (4 September 2015). Giraffe: Using Deep Reinforcement Learning to Play Chess. arXiv:1509.01549v1. Процитовано 12 December 2021. 
  10. а б Neural network topology. lczero.org. Процитовано 2021-12-12. 
  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 December 2021. 
  14. Ronald Friederich (January 4, 2020). PeSTO: Piece Square Tables Only. Процитовано December 12, 2021. 
  15. Yu Nasu (April 28, 2018). Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (Japanese). 
  16. Yu Nasu (April 28, 2018). Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (Unofficial English Translation). GitHub (English). 
  17. Gary Linscott (April 30, 2021). NNUE. GitHub. Процитовано December 12, 2020. 
  18. Noda, Hisayori (30 May 2020). Release stockfish-nnue-2020-05-30. Github. Процитовано 12 December 2021. 
  19. Introducing NNUE Evaluation. 6 August 2020. 
  20. Joost VandeVondele (July 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, Кембридж, Массачусетс

Посилання[ред. | ред. код]