Теория шахматного программирования

Стокфиш на ассемблере написан ??

 

Он написан на C++, может быть с ассемблерными вставками, но точно на C++ https://github.com/official-stockfish/Stockfish/tree/master/src

 

А какая разница, на чём он написан? Важен сам алгоритм. А портировать-то можно на любой язык и платформу.
Ну и ассемблер очень не универсален - надо под каждую архитектуру писать свой код.
Исходники-то на плюсах. И в них, на удивление, мало кода... Я-то думал там серьёзная эвристика. А похоже что просто оптимизация перебора. Ну и теперь понятно почему движки с оценками позиций порой ерунду всякую городят.

 

Проги на Ассемблере быстрее работают.

 

Проги на Ассемблере сложнее поддерживать, никто не пишет серьезный софт на ассемблере. Проще купить новый процессор, чем разрабатывать на ассемблере.

 

С чего это вдруг?

 

Ну вообще да. Нет временных затрат на работу компилятора/интерпретатора. Код идёт напрямую инструкциями для процессора. Другое дело, что это временной выигрыш может быть ничтожен (по сравнению со временем выполнения самого алгоритма). В то время как недостатков (и довольно объективных) хватает (неуниверсальность, временные и трудо-затраты на разработку).

 

В большинстве случаев - нет. Либо так же, либо даже медленнее, как это ни парадоксально. Причина в том, что современные оптимизирующие компиляторы C++ превосходят по своей квалификации 99,9% программистов.
Быстрее только в некоторых специфических ситуациях и при условии очень высокой квалификации программиста (низкоуровневая оптимизация под конкретное железо).

 

Не совсем верно: компилятор как раз тем и занимается, что перегоняет код на с++ в ассемблерный код. Ускорение при написании на ассемблере происходит за счет того, что можно оптимизировать расход процессорного времени.

 

Конечно же я понял о чём Вы. Я лишь придрался к формулировке. (Да и почему нет затрат на работу компилятора?)
Вероятно, Вы хотели сказать, что если и есть идеальная (по быстродействию) программа, то вряд ли её можно написать используя лишь возможности С++ и гарантированно можно написать на ассемблере.

В указанной Вами теме не нашёл ничего конкретного по программированию, поэтому напишу здесь.
Есть ещё способ написания программ на ассемблере, когда за основу берётся код программы, написанной на языке высокого уровня. Код этой программы дизассеблируется, а потом из неё удаляется всё лишнее и(или) заменяется на более оптимальный код.

 

Это оптимизация скорее, а не написание.

 

Все проги работают на машинном (процессорном) коде, Ассемблер - лишь один из языков трансляции алгоритмов на машинный язык. Все зависит от алгоритма. Вы реально считаете, что транслятор хуже понимает, как перевести алгоритм в код чем вы ?

 

Вообще-то разница в интерпретаторе и компиляторе есть. Но программируя только в Бэйсике, этого нифига не поймешь.

 

Уважение программеру

Мое уважение коллеге, который понимает разницу между компилятором и интерпретатором. И понимает что ассемблер по сути это тоже язык ВУ. В нащ век "программистов 1С" это большая редкость ...

 

Хотелось-бы заметить, что скорость работы какой-либо программы складывается из времени собственно ее работы + время потраченное на ее разработку.
С этим и связана популярность Basic (особенно для продуктов Microsoft) - прикладные системы разрабатываются очень быстро (и, да он компилируемый!).
Но даже Basic сейчас вытесняется, и чем интерпретатором !
Нынче рулит Python, пишут, что все преподавание программирования на Западе, ведется на этом языке.
Ну не знаю, как на всем Западе, однако на Эйлеровском проекте подавляющее число участников ваяет именно на нем.

 

Ассемблер - язык ВУ ? "Ну, вы блин даете" ©

—- добавлено: 27 ноя 2016, опубликовано: 27 ноя 2016 —-

Нынешнее семейство трансляторов (не стал зачеркивать - конечно, программ) пишется командами (хотя я видел разную степень этой командности), при этой команде есть саппорт, который выявляет баги - иногда ищешь одну, находишь другую (я, вот недавно в коде Delphi, импортированном видимо из Fox, нашел определение видимости грида в цикле, от итерации независимой - что поможет анализ ассемблера или кода ?).
Ненужная зависимость от библиотек - это вы о каком ЯП говорите ? В дельфях этого нет с рождения. СПП тащит что ли ?
Оптимизация - это вещь. Хорошая оптимизация в оракле на порядке ускоряет выполнение, пока дба что-то там не поменяет, не зная о вашей недокументизированной оптимизации

 

"Скорость работы" - что это для вас? Время пользования программой или ее быстродействие?
"Популярность Basic" - вы этого программерам не говорите, бить не будут, слюны достаточно будет.
"Рулит Питон" - не все, за что платят, пишется через веб, мой город силен традициями ВПК, я в курсе, что всем требуется, и как сказал один камрад, не в 1С дело, бразе

 

По-моему, я достаточно понятно объяснил про скорость работы какой либо программы.
То что у программеров слюней много я знаю, но знаю также, что как и у орудий калибр у них разный.
А вот то, что "дело вовсе не в бобине " (т. е. не в 1С) с этим соглашусь.

 

Хм, а как такая позиция может образоваться.
Как говорят тестеры, телепаты в отпуске. Логи есть ?

—- добавлено: 28 ноя 2016 —-

О, вот как, камрады, куда я попал "Теория шахматного программирования"
Из-за дурацкого вопроса, что ассемблер является ЯВУ?
Ты смотри, солдат, где теория шахмат, обсуждение "скорости-времени выполнения программ" и Багдад?

—- добавлено: 28 ноя 2016, опубликовано: 28 ноя 2016 —-

Повторю для Ondatr (чтобы связность не нарушилась)
Ничего Вы достаточно не объяснили. В один флакон Вы сложили время и скорость. Вы не ответили на первый поставленный мною вопрос (второй и третий снимаю, ибо какой-то ответ получил). В недолетевшем вашем ответе я успел прочитать, про складывание времени. Вы и скорость также скалярно складываете?

 

Ну в принципе, разобрался, откуда там слон. Вот только - чего он туда забрался...

 

Не знаю куда писать, решил начать здесь. Я изобретаю разные шахматные мини игры. Несколько примеров (моих и чужих) тут - https://scratch.mit.edu/studios/1962394/
Все они предназначены для самых маленьких шахматистов, кто только знакомится с ходами фигур. Посоветуйте, где написать про это, чтоб люди могли протестировать, отзывы оставить, что-нибудь новое предложить?

 

"Чукча не читатель..."©?
Специально через слэш написал)) Что интерпретатор, что компилятор (этот конечно побыстрее работает) отжирают быстродействие. Как бы ни был хорош С(++, # и т.д.) - ему все равно требуется компилятор и некий обвес в виде стандартных библиотек.
Ну да ладно, с уровнем "8 класса средней школы" программирования вроде разобрались.
В контексте же данной задачи, разница вообще несущественная - тут скорее дело в железе и принципах. Кмк, надо смотреть в сторону майнинга, распределенных вычислений, видеокарт и специализированных процессоров (ASIC). И как следствие, получается что для данной задачи лучше всего подходят не Ассемблер или Си, а HDL)))))

 

"Вылизывание" кода, конечно, хорошо, но нельзя сбрасывать со счетов изменение архитектуры процессоров и сопроцессоров.

Вот где непочатый край работы.

—- добавлено: 29 ноя 2016, опубликовано: 29 ноя 2016 —-

Для решения данной задачи нужны хорошие идеи и алгоритмы. А дальше уже как реализуешь. Ведь оптимизацией или вычислительного процесса или реализации алгоритма может заняться ... искусственный интеллект.
Почему, если такие системы могут обыгрывать человека в Го, охлаждать суперкомпьютеры, обыгрывать людей в "стрелялки", они не смогут подобрать наилучший вариант кода?

 

Ну если уж мы полезли в ближнюю фантастику, то тут скорее нужен квантовый компьютер)) Это как раз задача (просчитать позицию) для его специализации.

 

И такая тема на форуме есть.

 

Мои пару копеек: Жираф это не совсем полностью самообучаящаяся программа. Это стандартная альфа-бета программа, только оценочная функция позиций была натренирована с помощью нейро-сети.

 

Перевел небольшую статью Торда Ромстада по методу LMR.

LMR в настоящее время по праву занял место одной из базовых техник шахматного программирования (из статьи будет понятно, почему). Это пожалуй последний из ряда найденных "фундаментальных" подходов, ответственных за силу игры современных шахматных движков. Он приобрел широкую популярность относительно недавно, с 2005 года.

Торд Ромстад
"Введение в Сокращение последних ходов (LMR)":

Торд Ромстад

"Введение в Сокращение последних ходов (LMR)"


Введение

Большинство популярных методов селективного поиска в компьютерных шахматах и других абстрактных настольных играх, занимаются сокращением объема работы на "подозрительно хороших" (fail high) узлах. К этой категории относятся: рекурсивное отсечение нулевого хода (null move pruning), отсечения Multi-Cut и ProbCut. Для всех этих методик характерна ещё одна особенность - они сокращают глубину поиска при вычислении значения оценки (или только нижнего предела оценки) узла и если значение оценки окажется выше беты, отсекают поддерево ниже данного узла.

Проблема всех вышеупомянутых методов заключается в том, что хотя сами по себе они работают хорошо, они не слишком удачно дополняют друг друга. Рекурсивный нулевой ход доказал свою огромную эффективность в компьютерных шахматах, но примечательно, что очень немногие программисты сообщали об успехах с добавлением поверх него Multi-Cut и ProbCut. Наиболее вероятное объяснение - что все три метода имеют склонность добиваться успеха на одних и тех же узлах. На тех узлах, где ProbCut мог бы произвести отсечение, нулевой ход как правило будет вызывать отсечение ещё до того, как даже возникнет возможность применить ProbCut.

Поэтому, при попытке дальнейшего улучения стандартного PVS-поиска с рекурсивным нулевым ходом, взгляд невольно обращается к методам, которые сокращают объём работы уже на "откровенно плохих" (fail low) узлах. До недавнего времени в этой области публиковалось не слишком много работ. Сокращение последних ходов является одной из немногих известных методик такого рода. Источники происхождения этого метода затерялись во времени, и кажется ни один человек не знает, кто же предложил его. Метод оставался относительно безвестным вплоть до 2004 года, когда Сергей Марков и я привлекли к нему всеобщее внимание при обсуждении на форуме Клуба компьютерных шахмат. С тех пор Сокращение последних ходов успешно реализовано множеством шахматных программистов, особенно после того, как незадолго до конца 2005 года оно было добавлено во Фрукт (Fruit) - очень сильную программу с открытым исходным кодом.

Терминология все еще не устоялась и поэтому для данной методики используется несколько различных названий. Помимо "Сокращения последних ходов" (LMR), которое я предпочитаю использовать, мне доводилось видеть его описание как "сокращений на основе сортировки", "fail low сокращений", "отсечения по истории (history pruning)". Последнее название наиболее распространенное и, в моём представлении, наиболее неудачное. Почему, объясняется ниже.


Основная идея

Сокращение последних ходов основывается на простом наблюдении, что в программе с хорошим упорядочиванием ходов, бета-отсечение обычно происходит либо уже на первом узле, либо его не будет совсем. Используя это соображение, мы будем просматривать несколько первых ходов каждого узла на полную глубину, а остальные ходы с сокращенной глубиной (если только эти ходы не выглядят особенно форсированными или не интересны нам в каком-либо другом отношении). Если один из сокращенных ходов удивит нас, возвратив оценку выше альфы, то будет произведен его перерасчет, уже с полной глубиной.

Следующий псевдокод иллюстрирует общую структуру PVS-поиска, в том числе рекурсивный нулевой ход и Сокращение последних ходов (код непосредственно отвечающий за LMR выделен жирным шрифтом):

Код:

const int FullDepthMoves = 4;
const int ReductionLimit = 3;

int search(int alpha, int beta, int depth) {
  int value, moves_searched;
  move_t move;

  if(depth == 0) return qsearch(alpha, beta, depth);
 
  // Поиск методом нулевого хода:
  if(ok_to_do_nullmove_at_this_node()) {
    make_nullmove();
    value = -search(-beta, -beta, -(beta-1), depth-4);
    unmake_nullmove();
    if(value >= beta) return value;
  }
 
  moves_searched = 0;
  while((move = pick_move()) && alpha < beta) {
    make_move(move);

    if(moves_searched == 0) // Первый ход использует полную ширину окна
      value = -search(-beta, -alpha, depth-1);
    else {
      if(moves_searched >= FullDepthMoves && depth >= ReductionLimit &&
        ok_to_reduce(move))
        // Просматриваем этот ход с сокращенной глубиной:
        value = -search(-(alpha+1), -alpha, depth-2);
      else value = alpha+1;  // Небольшой хак, гарантирующий, что поиск на полную глубину выполнен
      if(value > alpha) {
        value = -search(-(alpha+1), -alpha, depth-1);
        if(value > alpha && value < beta)
          value = -search(-beta, -alpha, depth-1);
      }
    }
    unmake_move(move);
    if(value > alpha) alpha = value;

    moves_searched++;
  }
  return alpha;
}

Вариации и улучшения

Наиболее очевидно пропущенная вещь в псевдокоде выше, это функция ok_to_reduce(). Бездумное сокращение всех ходов после первых трех или четырех, почти наверняка приведет к катастрофическим результатам. Нам требуются определенные дополнительные условия для идентификации тактически и позиционно интересных ходов, чтобы избежать их слишком частого сокращения. Очевидно, что шахи (и, если более обобщенно, ходы которые продлеваются) никогда не должны сокращаться. Большинство программ также избегают сокращения взятий и превращения пешки. Кроме того, для различных программ условия варьируются в очень широких пределах. Вот некоторые из наиболее популярных условий:

• Статистика Истории. Ходы, которые в прошлом часто отсекались верхним пределом (fail high), или обладают высоким соотношением (fail high) / (fail low), не должны сокращаться.
• Обнаружение статических или динамических угроз. Если ход, который является кандидатом на сокращение, содержит некоторые серьезные тактические или динамические угрозы, то сокращений следует избегать.
• Данные оценки. Их можно использовать несколькими способами. Одна из возможностей, позволить сокращения только на узлах, где статическая оценка ниже альфы. Также возможно проверять, как каждый ход влияет на оценку и избегать сокращения тех ходов, которые улучшают статическую оценку или одну из её компонент с точки зрения ходящей стороны.
• Тип узла. Имеет смысл не сокращать никаких ходов на PV-узлах.

Первое из условий изначально именовалось как метод "отсечения по истории". Мне не нравится это название, поскольку оно предполагает, что условие Истории является определяющим, и поскольку оно маскирует тот факт, что мы говорим скорее о сокращении, чем отсечении. Есть программы, которые успешно используют LMR, не полагаясь на статистику Истории вообще.

Не все программы с LMR в точности следуют структуре псевдокода из предыдущего раздела. Один из наиболее популярных вариантов - пренебречь повторным поиском сокращенных ходов, которые возвратили оценку выше альфы. Большинство программ кажется используют повторный поиск, но они не являются ведущими. Например, Фрукт 2.0 использует LMR без повторного поиска. Повторный поиск по Истории был добавлен только во Фрукте 2.1.

Некоторые авторы шахматных программ также экспериментировали с сокращениями более чем на один полуход, с переменным успехом.


Заработает ли?

Подобно большинству других трюков, эффективность LMR во многом зависит от реализации программы. Для некоторых программ он дает 100 эло или больше, для остальных только небольшое улучшение, или совсем ничего. Существует также ряд программ, где он совершенно не выполняет полезной работы и программа играет лучше без LMR. Единственный способ проверить заработает ли он у вас, просто попробовать.

Однако кажется очевидным, что данный метод обладает определенным потенциалом, даже на самом высоком уровне. Мне известно, что по крайней мере две из лучших на текущий момент коммерческих программ используют LMR, и есть серьезные подозрения в отношении третьей. Насколько я знаю, их число может быть даже больше.

Я полагаю, что LMR все еще весьма сырая и неотработанная техника, и в перспективе она может, и будет, значительно улучшена.


Пример кода

Две популярные шахматные программы использующие LMR, это Фрукт (доступен на странице загрузок сайта WCEC) и Глаурунг (Glaurung). Тем не менее эти два движка значительно различаются в деталях реализации. Сокращения Фрукта основаны на учете истории ходов и типах узлов, в то время как Глаурунг опирается на данные оценки и простую форму определения динамических угроз.

Tord Romstad, 27.02.2006

Оригинальный текст на английском:

Tord Romstad

An Introduction to Late Move Reductions

Introduction

Most of the commonly used selective search techniques in computer chess and other abstract board games work by reducing the amount of work at nodes where the search fails high. Recursive null move pruning, multi-cut pruning and ProbCut all belong to this category. All of these techniques also share another characteristic: They use reduced depth searches to compute an estimate for the score of the node (or just a lower bound for the score), and prune the sub-tree below the node if this estimated score is above beta.

A problem of all the above-mentioned techniques is that although they work well by themselves, they do not complement each other very well. In computer chess, recursive null move pruning has proved to be extremely effective, but remarkably few programmers have reported success with adding multi-cut or ProbCut on top of recursive null move pruning. The most likely reason for this is that all three techniques tend to be successful at the same nodes. At nodes where ProbCut would have achieved a cutoff, the null move search will moste often produce a cutoff before ProbCut is even applied.

When attempting to further improve a standard PVS search with recursive null move pruning, it is therefore tempting to look for techniques which reduce the amount of work at fail low nodes. Until now, little work has been published in this area. Late move reductions are one of the few known techniques. The origins of this technique is lost in antiquity, and nobody seems to know who the inventor was. It was rather obscure until year 2004, when it was popularised by Sergei Markoff and myself in discussions at the Computer Chess Club. Since then, late move reductions have been successfully implemented by a big number of chess programmers, especially after they were added to the very strong open source program Fruit near the end of 2005.

The nomenclature is still not standardized. Several different names are used for the technique. In addition to "late move reductions", which is the name I prefer to use myself, I have seen them described as "ordering-based reductions", "fail low reductions" and "history pruning". The last name is by far the most common, and in my opinion by far the most unfortunate. The reasons for this will be explained below.

The Basic Idea

Late move reductions are based on the simple observation that in a program with reasonably good move ordering, a beta cutoff will usually occur either at the first node, or not at all. We make use of this observation by searching the first few moves at every node with full depth, and searching the remaining moves with reduced depth unless they look particularly forcing or interesting in some other way. If one of the reduced moves surprise us by returning a score above alpha, the move is re-searched with full depth. The following pseudo code displays the outline of a PVS search with recursive null move pruning and late move reductions included (the actual late move reduction code is displayed in boldface):

Код:

const int FullDepthMoves = 4;
const int ReductionLimit = 3;

int search(int alpha, int beta, int depth) {
  int value, moves_searched;
  move_t move;

  if(depth == 0) return qsearch(alpha, beta, depth);
 
  // Null move search:
  if(ok_to_do_nullmove_at_this_node()) {
    make_nullmove();
    value = -search(-beta, -beta, -(beta-1), depth-4);
    unmake_nullmove();
    if(value >= beta) return value;
  }
 
  moves_searched = 0;
  while((move = pick_move()) && alpha < beta) {
    make_move(move);

    if(moves_searched == 0) // First move, use full-window search
      value = -search(-beta, -alpha, depth-1);
    else {
      if(moves_searched >= FullDepthMoves && depth >= ReductionLimit &&
        ok_to_reduce(move))
        // Search this move with reduced depth:
        value = -search(-(alpha+1), -alpha, depth-2);
      else value = alpha+1;  // Hack to ensure that full-depth search
                                          // is done.
      if(value > alpha) {
        value = -search(-(alpha+1), -alpha, depth-1);
        if(value > alpha && value < beta)
          value = -search(-beta, -alpha, depth-1);
      }
    }
    unmake_move(move);
    if(value > alpha) alpha = value;

    moves_searched++;
  }
  return alpha;
}

Enhancements and Variations

The most obvious thing missing in the pseudo code above is the ok_to_reduce() function. Blindly reducing all moves after the first three or four will almost certainly have catastrophic results. We need some extra conditions for identifying tactically and positionally interesting moves, and avoid reducing these too often. Obviously, checks (and more generally, moves which are extended) should never be reduced. Most programs also avoid reducing captures and promotions. Beyond this, the conditions vary widely between different programs. Some of the more popular conditions are the following:

• History counters. Moves which have failed high often in the past, or have a high (fail high) / (fail low) ratio are not reduced.
• Static or dynamic threat detection. If the move which is a candidate for reduction contains some serious tactical or positional threat, reduction is avoided.
• Evaluation data. This can be used in several ways. One possibility is to allow reductions only at nodes where the static eval is below alpha. It is also possible to check how each move affects the evaluation, and to avoid reducing those moves which improve the static eval or one of its components, from the point of view of the moving side.
• Node type. It makes sense not to reduce any moves at PV nodes.

The first of these conditions are the origin of the name "history pruning". I do not like this name, because it implies that the history condition is essential, and because it obscures the fact that we are talking about reductions rather than pruning. There are programs which successfully use late move reductions without relying on history counters at all.

Not all programs with late move reductions follow the exact pattern of the pseudo code in the previous section. One of the most common deviations is to omit the re-search of reduced moves which return a score above alpha. The majority of programs do seem to use re-searches, but they are not essential. For instance, Fruit 2.0 used late move reductions without re-search. History re-search was only added in Fruit 2.1.

Some chess program authors have also experimented with reductions by more than one ply, with varying degrees of success.

Does it Work?

Like most other tricks, the effectivity of late move reductions depends to a great extent on the program. For some programs it gives 100 Elo points or more, for others it is just a tiny improvement, or none at all. There are also programs where it just does not work at all, and the program plays better without late move reductions. The only way to find out whether they work for you is to try.

It seems clear, however, that they have some potential, even on the highest level. I know that late move reductions are used in at least two of the current top commercial programs, and I have strong suspicions about a third. For all I know, the number could be even bigger.

I think that late move reductions is still a very crude and unpolished technique, and that it can and will be improved considerably in the future.

Sample Code

Two popular open source chess programs using late move reductions are Fruit (available from the download section at the WBEC site) and Glaurung. These two engines differ considerably in their implementational details. Fruit's reductions are based on history counters and node types, while Glaurung's are based on evaluation data and a simple form of dynamic threat detection.

Несколько моментов, на которые хотелось бы обратить внимание после прочтения данной статьи.

1. По-видимому, статья несколько устарела. Насколько мне известно, именно сортировка ходов по истории со временем стала основным методом определения неперспективных тихих ходов для LMR. Кроме того, современные программы сокращают более агрессивно.

2. Приведенный псевдокод интересен тем, что по сути представляет собой ядро современной шахматной программы, только без излишних наворотов. Конечно из кода не очевидна роль сортировок и некоторых других методов, но зато он очень компактен.

3. У Эда Шредера можно посмотреть принципы работы LMR на основе кусочков кода:
http://rebel13.nl

4. Не понятно, почему в приведенном выше псевдокоде у вызова функции search из нулевого хода четыре переменные, вместо объявленных при инициализации трех. Но поскольку я не программист, то может быть чего-то не понимаю (хотя кажется, все-таки ошибка).

5. Поскольку, на форуме почему-то нельзя выделить жирным текст в коде (а это важно), вынесу выделенный код отдельно:

 

Математическое обоснование шахматной теории, программирование шахматных программ. (На английском и словенском языках)
https://ailab.si/matej/

 

За статью спасибо.
А что реально нельзя текст выделить жирным?

 

Код:

Код нельзя выделить жирным

И ещё, при копировании кода со сторонних ресурсов с отступами что-то происходит. Больше двух пробелов не позволяет. Приходится редактировать вручную.