2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 12:03 
Аватара пользователя
Помню, ещё в Фидо в nice.sources раза 2 спрашивали: как вывести все перестановки из N чисел, ведь не напишешь N циклов в цикле от 1 до N. :D Я тогда кидал в эху свой исходник на Турбо Паскале - Дельфи. А на днях я опубликовал часть главы из своей книги "Delphi и Turbo Pascal на занимательных примерах" "Перестановки, сочетания, размещения: вывод всех перестановок".

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

В статье есть ссылка на zip файл с программой на Дельфи, которую легко перевести на Турбо Паскаль.

Есть ещё 2 алгоритма вывода перестановок: один легко найти в Сети, он был в книжке по московским математическим олимпиадам, а другой получается при выводе всех гамильтоновых циклов в полном графе.

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 13:54 
Все уже описано в 7.2.1.2 ACP. А сам алгоритм был обнаружен еще в XVII веке звонарями в Англии.

А так код выглядит несколько жутковато.

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 14:29 
Аватара пользователя

(Оффтоп)

mustitz в сообщении #748259 писал(а):
Все уже описано в 7.2.1.2 ACP.
Обычно сокращают как TAoCP

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 16:09 
Аватара пользователя
А ACP это что, и где это можно скачать?

Я давно как-то написал на Турбо Паскале нерекурсивную программу, решающую шахматные задачи на обычный, обратный и кооп. мат в любое число ходов. Она выдаёт первый ход и число ходов до мата. Звонари вряд ли такое придумали. :-) Она выглядит ещё более жутковато (я основные функции потом переписал на асм), но работает правильно. Не знаю, где бы её опубликовать. В то время Чессмастер 3000 и другие программы почему-то не могли решить даже некоторые обычные задачи без рокировок, взятия на проходе и превращения пешек. Сейчас есть более развитая программа Problemist.

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 16:13 
Аватара пользователя
iqfun.ru в сообщении #748322 писал(а):
А ACP это что
Дональд Кнут "Искусство программирования". Комбинаторная генерация в 4 томе.

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 16:19 
ACP это The Art of Computer Programming, D. Knuth

(Оффтоп)

А какой генератор ходов был? magic bitboard? rotated bitboard? Тогда поверю. А если брать 0x88, то у меня есть генератор ходов на JavaScript, там ничего страшного нет :)

chess.js, посмотреть тут

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 16:41 
iqfun.ru в сообщении #748322 писал(а):
Я давно как-то написал на Турбо Паскале нерекурсивную программу, решающую шахматные задачи на обычный, обратный и кооп. мат в любое число ходов.

(Оффтоп)

30 лет назад я восторгался исходниками программы для решения шахматных задач на Алголе-60 из книги "Библиотека алгоритмов 151б-200б". Кстати, они гордились тем, что программу удалось сделать нерекурсивной :)

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 17:00 
Аватара пользователя
mustitz в сообщении #748328 писал(а):
ACP это The Art of Computer Programming, D. Knuth

А...

mustitz в сообщении #748328 писал(а):
[off]А какой генератор ходов был? magic bitboard? rotated bitboard? Тогда поверю. А если брать 0x88, то у меня есть генератор ходов на JavaScript, там ничего страшного нет :)


Я тогда ещё не имел понятия о рекурсивных программах, ходы перебирал так: ищу фигуру и пытаюсь сделать ей все ходы, после которых нет шаха. Завод купил у воров Турбо Паскаль 5.5 с переведённой документацией, а у меня было много свободного времени (работал в смену в техсекторе).

Кто-то приносил на завод старый сборник алгоритмов за 1979 г., не помню, как назывался, помню, что под редакцией какого-то Алика. :-) Там обсуждался алгоритм сортировки массива простым обменом и решения шахм. задач на мат в 2 хода. Я тогда подумал, что неплохо бы написать решение в любое число ходов. Я этой своей программкой проверял свои задачки, находил побочные варианты, раз в задачнике нашёл ошибку. Одну свою 3-ходовку я даже показывал Давиду Бронштейну, когда он приезжал давать сеансы. Он сказал: "А, это все знают", - сразу сделал ход и ошибся. :-)

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 17:04 
iqfun.ru в сообщении #748343 писал(а):
Кто-то приносил на завод старый сборник алгоритмов за 1979 г., не помню, как назывался, помню, что под редакцией какого-то Алика. :-) Там обсуждался алгоритм сортировки массива простым обменом и решения шахм. задач на мат в 2 хода.
Это был второй выпуск, "Библиотека алгоритмов 51б-100б". В четвертом выпуске (1981 год) составители сборника уже написали свою программу, справляющуюся и с некоторыми пятиходовками..

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 17:22 

(Оффтоп)

iqfun.ru в сообщении #748343 писал(а):
mustitz в сообщении #748328 писал(а):
[off]А какой генератор ходов был? magic bitboard? rotated bitboard? Тогда поверю. А если брать 0x88, то у меня есть генератор ходов на JavaScript, там ничего страшного нет :)


Я тогда ещё не имел понятия о рекурсивных программах


Генератор ходов никак не связан с рекурсией. Это структура, в которой хранится шахматная позиция, плюс способ получения всех ходов в данной позиции. Например, доска представляется 64-битными целыми числами (бит на поле). в начальной позиции битовая маска белых пешек это 0xFF00, ладей 0x81, коней 0x42, и т. д. Это будет семейство генераторов bitboard, самых быстрых на сегодня.

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение23.07.2013, 09:42 
Аватара пользователя
Понятно. У меня было 64 байта на доску, белые фигуры кодировались положительными числами, чёрные отрицательными. Теперь видно, что это не лучший способ перебирать фигуры. Но если сразу всё оптимизировать, то запутаешься в коде и наделаешь ошибок.
Многофигурную двухходовку на PC XT 6 МГц моя программка решала ~5 мин. Ехе файл был 20 Кб.

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение24.07.2013, 11:41 

(Оффтоп)

iqfun.ru в сообщении #748519 писал(а):
Теперь видно, что это не лучший способ перебирать фигуры. Но если сразу всё оптимизировать, то запутаешься в коде и наделаешь ошибок.


Тогда уже лучше использовать 0x88 генератор, будет быстрее, код станет проще, шансов наделать ошибок меньше. Основная идея в том, что шахматную доску надо рассматривать как часть доски 16x16. Итого, поле a1 имеет индекс 0x00, поле b1 - 0x01, ..., поле h1 - 0x07, поле a2 0x10, поле b2 - 0x11, ..., поле a3 - 0x20, ... поле a4 - 0x30, ... поле h7 - 0x77. В этом случае переполнение (например, идем с поля h2 по диагонали вправо) приведет к неправильному индексу 0x17 -> 0x28, который можно проверить единственной проверкой

Используется синтаксис C
if (field & 0x88) then /* Out of board */;


Это делает код единообразнее и проще. Только остается $7\cdot 8=56$ неиспользуемых байт, которые можно задействовать под разные другие нужды (счетчик ходов без взятий, поле взятия на проходе, тэги для рокировок, оценка позиции и т. п.).

вот так выглядит генерация всех ходов:

код: [ скачать ] [ спрятать ]
Используется синтаксис Javascript
ChessGame.MoveGenerator.prototype.get = function()
{
  this.retValue = [];

  for &#40;var rank=0; rank<8; ++rank&#41;
    for &#40;var file=0; file<8; ++file&#41;
    {
      var field = 16 * rank + file;
      var piece = this.board[field];
      if &#40;ChessGame.pieceColor&#40;piece&#41; != this.active&#41; continue;

      switch&#40;piece&#41;
      {
        case &#39;K&#39;: case &#39;k&#39;:
          this.kingMoves&#40;field&#41;;
          break;

        case &#39;Q&#39;: case &#39;q&#39;:
          this.queenMoves&#40;field&#41;;
          break;

        case &#39;R&#39;: case &#39;r&#39;:
          this.rookMoves&#40;field&#41;;
          break;

        case &#39;B&#39;: case &#39;b&#39;:
          this.bishopMoves&#40;field&#41;;
          break;  

        case &#39;N&#39;: case &#39;n&#39;:
          this.knightMoves&#40;field&#41;;
          break;

        case &#39;P&#39;:
          this.pawnMoves&#40;field, +16, this.passant&#41;;
          break;

        case &#39;p&#39;:
          this.pawnMoves&#40;field, -16, this.passant&#41;;
          break;  
      }
    }

  this.castles&#40;&#41;;

  return this.retValue;
}

ChessGame.MoveGenerator.prototype.kingMoves = function&#40;from&#41;
{
  this.lineMoves&#40;from, [1, 15, 16, 17, -1, -15, -16, -17], true&#41;;
}

ChessGame.MoveGenerator.prototype.queenMoves = function&#40;from&#41;
{
  this.lineMoves&#40;from, [1, 15, 16, 17, -1, -15, -16, -17]&#41;;
}

ChessGame.MoveGenerator.prototype.rookMoves = function&#40;from&#41;
{
  this.lineMoves&#40;from, [1, 16, -1, -16]&#41;;
}

ChessGame.MoveGenerator.prototype.bishopMoves = function&#40;from&#41;
{
  this.lineMoves&#40;from, [15, 17, -15, -17]&#41;;
}

ChessGame.MoveGenerator.prototype.knightMoves = function&#40;from&#41;
{
  this.lineMoves&#40;from, [14, 18, 31, 33, -14, -18, -31, -33], true&#41;;
}

ChessGame.MoveGenerator.prototype.lineMoves = function&#40;from, delta, isShort&#41;
{
  for &#40;var i=0; i<delta.length; ++i&#41;
  {
    var to = from;
    for&#40;;;&#41;
    {
      to += delta[i];
      if &#40;&#40;to & 0x88&#41; != 0&#41; break;
      var piece = this.board[to];
      if &#40;ChessGame.pieceColor&#40;piece&#41; == this.active&#41; break;
      this.addMove&#40;from, to, piece != null ? "TAKING" : "MOVE"&#41;;
      if &#40;isShort&#41; break;
      if &#40;piece != null&#41; break;
    }
  }
}
 

 
 
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение26.07.2013, 09:49 
Аватара пользователя
Сейчас нет смысла заниматься этой программой. Ещё могу сказать по этому поводу, что я смотрел тему "шахматы на флэш", программы играли слабо, даже рокировку не понимали. Но на одном сайте я увидел такую программу, что и играет быстро и сила ~ как у 3-го разряда. А ведь AS - интерпретатор и работает медленно. Ещё удивительнее то, что это был не самый высокий уровень игры, самый высокий был под замком для нерегистрир. пользователей. Я поместил этот swf файл на свой сайт.
До этого я видел ява апплет, который играл ~ в силу 2-го разряда (играл только чёрными).

Я хочу сделать на флэш такую игру (называется "Ковбои и кони"): игра идет на шахм. доске 8х8.
У игрока, который играет ковбоями, 2 шахм. короля (это ковбои) на полях d1 и e1. У того, кто играет конями, 12 коней, которые стоят в виде прямоугольника с диагональю c8-f6. Ковбои ходят, как короли, а кони - как кони. Начинают ковбои, ходы делают по очереди. За 1 ход играющий ковбоями делает по 1 ходу каждым королем, а играющий конями - по 1 ходу разными конями. Цель ковбоев - съесть всех коней, цель коней - продержаться 50 ходов, тогда они выигрывают. Если останется 1 конь, игрок делает один ход этим конём, т.к. за 2 хода, как мне кажется, он сможет всегда убежать. Шахов, естественно, нет.

Интересует алгоритм игры за коней. Приходит в голову такой: делать ход, после которого сумма расстояний от королей до коней максимальна. Может, есть лучший алгоритм?

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group