TwiddleLab / Искусственный интеллект / Поиск, игры и планы

Оценка позиций: функции оценки

Урок 6 из 11 · 7 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Большие игры нельзя обыскать до конца, поэтому поиск останавливается на ограничении глубины.
• На срезе позицию вместо этого оценивает функция оценки: взвешенная сумма признаков, например 4 x открытые тройки + 2 x открытые двойки + 1 x центр.
• Дальше минимакс работает как раньше, только на счетах вместо побед и поражений.
• Лучшие признаки и веса дают более сильного бота при том же поиске.

Начать урок

Как идёт урок

1. В шахматах возможных партий больше, чем атомов в наблюдаемой Вселенной. Как же шахматный бот выбирает ход за секунду?

   Сначала ставка: компьютер проверяет миллиард позиций в секунду. Сколько ему понадобится, чтобы прочитать всё шахматное дерево, около 10^120 партий?

2. В «Четыре в ряд» 7 столбцов. Насколько глубоко бот может искать меньше чем за секунду?

   Крути ручку. Каждый лишний ход умножает число позиций на 7.

   7^7 = 823 543 позиции при миллионе в секунду это 0,82 с. Ещё один ход это 7^8 = 5 764 801: почти 6 секунд. Сама игра может длиться 42 хода, поэтому бот никогда не видит конца.

3. Поиск остановился здесь. Никто не выиграл. Какая доска лучше для красных?

   Во всех трёх ходят красные. Доверься глазам.

   На доске B у красных открытая тройка: красные ставят фишку в пустую клетку и выигрывают. На доске C у жёлтых две открытые тройки, а красные могут закрыть только одну. Доски оценены подсчётом угроз: именно это делает функция оценки.

4. Оценка позиции без доигрывания партии.

   Поиск останавливается на ограничении глубины. Там функция оценки даёт позиции счёт по признакам, которые можно посчитать: счёт = 4 x открытые тройки + 2 x открытые двойки + 1 x фишки в центре (у красных минус у жёлтых). Победа стоит 1000.

5. Посчитай открытые тройки красных на этой доске.

   Нажми на каждую пустую клетку, где красная фишка замкнула бы линию из четырёх.

   У красного ряда из трёх пустая клетка на каждом конце: две открытые тройки. На диагонали от нижнего ряда вверх вправо три красные фишки и пустая четвёртая: это третья. 3 открытые тройки дают 4 x 3 = 12 очков.

6. Собери функцию счёта своими руками.

   Поставь признак рядом с каждым весом. Смотри, какую доску предпочитает твоя формула.

   Открытая тройка в одном ходе от победы, открытая двойка в двух, а фишки в центре участвуют в большем числе линий. Каждый признак, умноженный на свой вес, и всё это сложенное, это взвешенная сумма: ровно то, что считает нейрон. Число фишек на доске или сыгранных ходов у обоих игроков одинаково, поэтому ничего не говорит.

7. Минимакс на два хода вглубь, с твоим счётом на срезе.

   Пройди по шагам. У красных три столбца-кандидата.

8. Настрой бота, пока он не выиграет хотя бы 8 из 10 партий.

   Он начинает со всеми весами 0: хорошие позиции от плохих не отличает. Задай веса, потом сыграй матч.

9. Какую доску формула оценивает выше всех?

   4 x тройки + 2 x двойки + 1 x центр, у красных минус у жёлтых.

   Доска A набирает 2, доска B 7, доска C -2. На B открытая тройка идёт вверх по среднему столбцу, и этот столбец за красными, что засчитывается ещё и как центр.

10. Теперь сыграй против своего настроенного бота.

    Ты играешь красными, первый ход твой. Он смотрит на два хода вперёд с твоими весами.

Предыдущий урок: Минимакс · Следующий урок: Альфа-бета: пропусти лишнее · Часть курса: Поиск, игры и планы

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.