stockfish (программистское)
Jun. 1st, 2014 08:38 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaШахматная программа Stockfish только что победила в самом престижном турнире компьютерных шахмат. Ее можно таким образом считать сильнейшей программой на данный момент. Необычно тут следующее: Stockfish - программа с открытым исходным кодом, который каждый может прочитать и исследовать. Обычно до сих пор самые верхние места в компьютерном рейтинге занимали программы с закрытыми исходниками.
Прямо вот на Github лежит: хочешь - бери, читай, клонируй, меняй.
Исходники при этом у нее написаны довольно чисто и ясно, читается легко, когда немного - посмотрите сами. Я это к чему говорю: тем программистам, которым интересно понять современное положение дел в компьютерных шахматах, можно посоветовать почитать именно эти исходники. Насколько я понимаю, с алгоритмической точки зрения там ровно такой же alpha-beta pruning, как объясняется в начальных курсах по искусственному интеллекту, и различие разных программ в том, какая у них эвристика остановки поиска, а также беспощадная оптимизация. Тем удобнее, что у текущего чемпиона это все получается сделать с небольшим относительно массивом понятно написанного и общедоступного кода.
Прямо вот на Github лежит: хочешь - бери, читай, клонируй, меняй.
Исходники при этом у нее написаны довольно чисто и ясно, читается легко, когда немного - посмотрите сами. Я это к чему говорю: тем программистам, которым интересно понять современное положение дел в компьютерных шахматах, можно посоветовать почитать именно эти исходники. Насколько я понимаю, с алгоритмической точки зрения там ровно такой же alpha-beta pruning, как объясняется в начальных курсах по искусственному интеллекту, и различие разных программ в том, какая у них эвристика остановки поиска, а также беспощадная оптимизация. Тем удобнее, что у текущего чемпиона это все получается сделать с небольшим относительно массивом понятно написанного и общедоступного кода.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-06-01 05:44 pm (UTC)no subject
Date: 2014-06-01 05:51 pm (UTC)Перебор всевозможных путей в дереве "а если я так схожу - а он так ответит - а я на него эдак..." на максимально возможную глубину и количественная оценка получившихся после этого позиций.
Выбирается тот ход, при котором все рассмотреные позиции в худшем случае лучше чем при других ходах
no subject
Date: 2014-06-01 05:55 pm (UTC)no subject
Date: 2014-06-01 05:56 pm (UTC)no subject
Date: 2014-06-01 06:01 pm (UTC)no subject
Date: 2014-06-01 06:50 pm (UTC)Но как из всех этих позиций выбрать наилучшую? - тем же способом рекурсивно: попробовать каждый мой ход, на него лучший ответ противника, выбрать то, что получилось удачнее всего. А какое это - "удачнее всего"? Попробуем еще на два хода глубже и посмотрим, что получилось...
Если бы мы могли так продолжать неограниченно, то каждую ветку вычислений довели бы до мата, пата или другой концовки игры, и это был бы полный перебор всех возможностей. Но на практике это невозможно, потому что количество вариантов растет экспоненциально. Поэтому после нескольких уровней перебора надо остановиться и сказать: так, эта позиция, которая получилась, в чью пользу она выглядит "из общих соображений" и насколько? Ну типа, у кого больше фигур и пешек, и другие подобные грубые соображения.
От скорости компьютера и нашего умения оптимизировать программу зависит, как глубоко мы сможем делать перебор вариантов.
Эта глубина поиска, а также то, как хитро мы напишем функцию оценки позиции, какие шахматные соображения в нее внесем, и как будем решать, когда останавливать перебор, определят силу игры алгоритма.
Вышеописанное - это алгоритм минимакс с обрывом (обрывом перебора через какое-то количество шагов). На практике применяется несколько более хитрая разновидность, которая называется alpha-beta pruning. Суть этого улучшения в следующем. Предположим, я уже вычислил, что после моего хода А лучший ответ противника Б приводит к позиции, которую я даю оценку, скажем, 10 (чем больше, тем лучше для меня). Теперь я смотрю на свой ход В и вижу, что на него есть ответ противника Г который дает оценку 5, меньше 10. Тогда я могу другие ответы противника на В даже не рассматривать. Я ведь все равно в итоге выберу лучший ответ за противника (т.е. минимальная оценка в мою пользу), который даст оценку 5 или меньше - и поэтому ход В уже точно не сможет конкурировать с ходом А. Значит, я могу сразу отказаться от хода В и все другие ответы противника на него даже не рассматривать.
no subject
Date: 2014-06-01 06:52 pm (UTC)no subject
Date: 2014-06-01 07:12 pm (UTC)no subject
Date: 2014-06-01 07:32 pm (UTC)no subject
Date: 2014-06-01 10:26 pm (UTC)no subject
Date: 2014-06-02 08:10 am (UTC)no subject
Date: 2014-06-02 12:45 pm (UTC)no subject
Date: 2014-06-03 06:55 am (UTC)Учитывая, как сильно продвинулось железо - это просто удивительно!
no subject
Date: 2014-06-03 09:49 am (UTC)no subject
Date: 2014-06-06 01:48 pm (UTC)no subject
Date: 2014-06-16 07:51 am (UTC)