TD-нарди

TD-нарди — це комп'ютерна програма для гри в нарди, розроблена в 1992 р. Джеральдом Тезауро в дослідницькому центрі Томаса Дж. Ватсона IBM. Назва програми походить від того факту, що це штучна нейронна мережа, навчена за допомогою методу часових різниць, а саме методу TD-лямбда створеного Річардом Саттоном.

TD-нарди досягла рівня гри трохи нижче, ніж у найкращих гравців у нарди того часу. В ній були досліджені стратегії, які не використовувалися людьми, і було досягнуто успіхів у теорії правильної гри в нарди.

Алгоритм гри та навчання

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

Алгоритм навчання TD-нардів полягає в оновленні ваги в її нейронній мережі після кожного ходу, щоб зменшити різницю між оцінкою позицій дошки в попередніх ходах і оцінкою позиції дошки в поточному ходу — звідси і «метод часових різниць». Рахунок будь-якої позиції на дошці — це набір із чотирьох чисел, що відображають оцінку програмою ймовірності кожного можливого результату гри: білі зазвичай перемагають, чорні зазвичай перемагають, білі виграють гру, чорні виграють гру. Для остаточного становища дошки у грі алгоритм порівнює з фактичним результатом гри, а не з власною оцінкою положення дошки.

Алгоритм навчання оновлює кожну вагу після кожного ходу в нейронній мережі відповідно до цього правила:

$w_{t+1}-w_{t}=\alpha (Y_{t+1}-Y_{t})\sum _{k=1}^{t}\lambda ^{t-k}\nabla _{w}Y_{k}$

де:

$w_{t+1}-w_{t}$	це сума зміни ваги, порівняно з його значенням на попередньому ходу.
$Y_{t+1}-Y_{t}$	це різниця між оцінками дошки поточного та попереднього ходу.
$\alpha$	це параметр «темп навчання».
$\lambda$	це параметр, який впливає на те, наскільки існуюча різниця в оцінці поточного стану дошки має відповідати попереднім оцінкам. $\lambda =0$ змушує програму коригувати лише оцінку попереднього ходу; $\lambda =1$ робить спробу програми скоригувати оцінки на всіх попередніх ходах; та значення $\lambda$ від 0 до 1 вказує різні швидкості, з якими важливість старих оцінок має з часом «зменшуватися».
$\nabla _{w}Y_{k}$	це градієнт результату нейронної мережі по відношенню до ваги: тобто, наскільки зміна ваги впливає на результат

Експерименти та етапи навчання

На відміну від попередніх нейромережевих програм гри в нарди, таких як Neurogammon (також написана Тезауро), де експерт навчав програму, надаючи «правильну» оцінку кожної позиції, TD-нарди спочатку була запрограмована «без знань». У ранніх експериментах, використовуючи лише кодування дошки без будь-яких функцій, розроблених людиною (програма самостійно давала оцінку кожному стану), TD-нарди досягла рівня гри, порівнянного з Neurogammon: рівня гри в нарди середнього рівня.

Незважаючи на те, що TD-Gammon виявила цікаві закономірності самостійно, Тезауро ставив питання, чи можна покращити його гру, використовуючи розроблені вручну функції, такі як Neurogammon. Справді, TD-нарди, що самонавчались, з функціями, розробленими експертами, незабаром перевершила усі попередні комп'ютерні програми для нард. Програма перестала покращуватися приблизно після 1 500 000 ігор (самостійних ігор) із використанням 80 прихованих вузлів нейронної мережі.

Успіхи теорії нард

Ексклюзивне навчання TD-нардів за допомогою гри зі самим собою дозволило їй вивчити стратегії, які раніше люди не розглядали або виключали помилково. Її успіх у використанні нестандартних стратегій вплинув на спільноту любителів нард.

Наприклад, у дебютній грі прийнято вважати, що при кидку 2-1, 4-1 або 5-1 білі повинні перемістити одну шашку з точки 6 до точки 5. Це називається «прорізування». Техніка балансує ризиком на можливість розвинути агресивну позицію. TD-нарди виявила, що більш консервативна гра 24-23 — краще. Турнірні гравці почали експериментувати та застосовувати тактику TD-нардів і досягли успіху. За кілька років техніка прорізування зникла з турнірів. (Тим не менш, вона іноді з'являється при кидку 2-1.)

Експерт з нардів Кіт Вулсі виявив, що оцінювання позицій дошки TD-нардів, особливо її зважування між ризиком та безпечною грою, було кращим за його власне або будь-якої людини.

Чудова позиційна гра TD-нардів псується іноді невдалою грою в ендшпілі. Ендшпіль вимагає більш аналітичного підходу, іноді з детальним прогнозом. Використання двошарового підходу TD-нардів створює обмеження щодо того, чого вона може досягти у цій частині гри. Сильні та слабкі сторони TD-нардів були протилежні програмам символьного штучного інтелекту та більшості комп'ютерних програм загалом: програма добре розв'язувала питання, які вимагають інтуїтивного «відчуття», але погано справлялася із систематичним аналізом.