2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 12:03 
Аватара пользователя


07/01/12

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

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

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

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

 Профиль  
                  
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 13:54 


10/04/12
705
Все уже описано в 7.2.1.2 ACP. А сам алгоритм был обнаружен еще в XVII веке звонарями в Англии.

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

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


06/10/08
6422

(Оффтоп)

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

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


07/01/12

232
А ACP это что, и где это можно скачать?

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

 Профиль  
                  
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 16:13 
Заслуженный участник
Аватара пользователя


06/10/08
6422
iqfun.ru в сообщении #748322 писал(а):
А ACP это что
Дональд Кнут "Искусство программирования". Комбинаторная генерация в 4 томе.

 Профиль  
                  
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 16:19 


10/04/12
705
ACP это The Art of Computer Programming, D. Knuth

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение22.07.2013, 16:41 
Заслуженный участник


31/12/05
1525
iqfun.ru в сообщении #748322 писал(а):
Я давно как-то написал на Турбо Паскале нерекурсивную программу, решающую шахматные задачи на обычный, обратный и кооп. мат в любое число ходов.

(Оффтоп)

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

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


07/01/12

232
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 
Заслуженный участник


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

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


10/04/12
705

(Оффтоп)

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


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


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

 Профиль  
                  
 
 Re: Алгоритм с интересными свойствами вывода всех перестановок
Сообщение23.07.2013, 09:42 
Аватара пользователя


07/01/12

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

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


10/04/12
705

(Оффтоп)

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 
Аватара пользователя


07/01/12

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group