0,3
рейтинг
22 августа 2013 в 13:45

Разработка → Шахматы на чистом sed

В Линуксе и многих других системах существует утилита командной строки sed («сед») — это несложный редактор, которые преобразует текст, попадающий ему на вход при помощи несложных команд.

Его, в основном, используют для всяких мелких нужд в bash-скриптах — заменить одну строку на другую, что-то удалить и так далее. Если говорить терминами более привычных языков, в «седе» доступны две строковые переменные, в одной из которых можно что-нибудь проверять, заменять, а со второй только обмениваться данными из первой, метки, команды переходов на метки и группировка команд, плюс ещё несколько менее полезных директив.

Вот на этом безобразии я решился написать шахматы, причём такие, чтобы можно было бы играть с компьютером.

Вообще, это не первая игра на «седе», существует, например, Тетрис и Арканоид, но моя игра, похоже, обошла их по размеру и интеллекту.

Мне давно хотелось узнать «сед» получше, но как-то повода не было, вот я и решил написать на нём что-то более значительное, чем скрипт заменяющий одну строку на другую. К сожалению, недостаток всех существующих доселе игр на «седе» — им требуется значительная скриптовая обвязка (что замутняет чистоту идеи) в связи с одной неприятной особенностью — «сед», прежде чем что-то сделать, ждёт нажатия клавиши ввода.

Поэтому, когда я размышлял что же написать, я выбрал шахматы — игру пошаговую, где каждую команду подтверждать ввод положено. Честно сказать, я тогда не представлял на что я себя обрекаю. В итоге (а игру я писал примерно две недели, правда с гигантскими перерывами), я пару раз порывался бросить это занятие.

Сложнее всего было с числами — как их вычитать, складывать, сравнивать, если в «седе» вообще нет арифметики? Пришлось изобрести свой формат хранения чисел, например, «111::11» означает 302 (число кодируется количеством единиц, десятки разделяются двоеточием), вся математика над этими числами делается при помощи набора регулярных выражений и переходов между ними.

Вот кусочек логики вычитания (вся функция занимает 59 строк):



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

Должен сразу предупредить — игра ощутимо медленная, на моём «Макбуке Про» (2,9ГГц, Интел Ай7) ответный ход к «e2 e4» просчитывается 6,3 секунды. Впрочем, шахматы учат терпению, так что это не должно быть помехой.

# кстати, можете сравнить производительность своего компьютера с моим при помощи команды
printf "\ne2 e4\nq\n" | time sed -f chess.sed

Из ограничений, которые я себе поставил — не использовать расширения GNU sed и расширенные регулярные выражения.

Итак, что же вышло?

Запрограммированы позиционная оценка и оценка наличия фигур на доске (алгоритмы оценок взял из книги «Программирование шахмат и других логических игр» Корнилова Евгения Николаевича), перебор ходов (вложенности нет, перебирается только ближайший ход), обнаружение шаха и мата, дошедшая до конца доски пешка преобразуется в ферзя.

Нет обнаружения пата (руки не дошли, хотя сделать несложно) и игра, фактически, ведётся по правилам XIV века — нет рокировки и взятия на проходе, уход от шаха примитивный. Так же я не сделал контроль за правильностью хода человека, так что, если хотите самоутвердиться за счёт беззащитной машины, можете сразу срубить короля.

Скачать игру можно с проекта на Гитхабе, там же небольшая инструкция как играть. О багах, если будут, пишите в комментарии или личку, но когда исправлю — не знаю, после полутора тысяч строк на «седе» мне требуется перерыв.
Евгений Степанищев @bolk
карма
96,8
рейтинг 0,3
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (66)

  • +36
    Ух, такому исходнику позавидуют даже самые изощренные адепты perl-а.
    • +2
      Я думал, что Perl — это единственный язык, который выглядит одинаково до и после обфускации. Однако, нет :\
  • 0
    Все хорошо, только вот пешки могут идти назад. Т.е. в случае стоящей пешки на e4 возможен ход e4 e3.
    • +9
      Я не делал контроля за ходом человека.
      • +15
        и вот тут мне поперло (с)
        А по теме, сильно конечно
    • 0
      Чего????? O_o
      Пешка? Назад? ФИДЕ поменяла правила?
      Из «нестандартных ходов» в современных шахматах встречаются:
      1) Рокировка (короткая и длинная) — плюс надо отслеживать соблюдение условий рокировки.
      2) Первый ход пешки — на одну или на две клетки.
      3) Вытекает из второго — «взятие на проходе» (en passant).
      4) Превращение пешки на последней горизонтали в любую фигуру, кроме короля (в том числе и ещё имеющуюся на доске — т.е. второй ферзь официально разрешён).

      P.S. Понял — Вы имели в виду, что игра как раз даёт возможность сделать запрещённый ход.
  • +53
    «а игру я писал примерно две недели, правда с гигантскими перерывами» — вы только что очень сильно занизили мою самооценку.
  • +3
    Буквально месяц назад подумывал написать игру на sed'e, но руки так и не дошли.

    Но это что-то космическое, снимаю шляпу.

    Я, кстати, записал небольшой фрагмент игры в демонстрационных целях, можете вставить в топик вместо видео, или записать свое: ascii.io/a/5088
    • 0
      А там моноширинного нет, а то все клетки сползли :)
      • 0
        Запишите из своей консоли, будет выглядеть почти так, как у вас (только там небольшие проблемы с русскими буквами).
    • +4
      Ай-ай чужие игры из под рута запускать. (:
      • +3
        Я проверил код перед запуском! =)
  • +14
    Мсье знает толк в шахматах!
  • +4
    Кстати, а на брейнфаке шахматы уже писал кто-нибудь?
  • 0
    Почему-то компьютер не закрылся от шаха ферзём, а просто подвинул своего ферзя. За что и был сурово съеден.
    • 0
      Оценка глубиной на один ход, он просто не смог просчитать эту ситуацию :)
      • 0
        Я чуть ниже ссылку разместил — мне кажется что вот это как раз и есть один ход ).
        • 0
          Не-не, имеется ввиду, что он перебирает свои ходы и смотрит какой лучше, но дальше не перебирает оценки соперника (это уже глубина 2).
          • 0
            Ааа, понятно. прошу прощения, неправильно понял. Думал он хотя бы шахи-то фиксирует. Хотя сеперь я понял, что это та же валидация хода человека.
            • +1
              Вообще, добавить оценку на второй шаг не так уж и сложно, там всё есть уже для этого :) Просто я уже как-то подустал :)
              • +1
                То что вы вообще написали больше трёх строк уже подвиг на мой взгляд :)
                Как я уже сказал — это гениально.
      • +2
        Ой, я забыл сказать, что на мой взгляд вы — просто гений. Я преклоняюсь перед вашими способностями! Спасибо!
    • +2
      Вот тут можно трансляцию матча посмотреть: ascii.io/a/5089
    • 0
      Вообще-то, по правилам шахмат, не закрыться от шаха — это запрещенный ход (а не просто неразумный). Точнее, если королю объявлен шах, то допустимо либо закрыться, либо отодвинуть короля, либо убить нападающую фигуру. Как-то так.
      • 0
        Мне тоже так вспоминается. Но не будем слишком строги :).
  • +8
    Когда захотите awk освоить, будете ММОРПГ писать? ;)

    Вообще, очень круто! Две недели кажутся сильно жалким сроком для такого объёма работы
    • +1
      Надо попробовать :-D
  • 0
    Очень напомнило лабораторные работы по НАМ :)

    sed + вечный цикл — это практически нормальные алгоритмы Маркова (Тьюринг-полный язык).
    • 0
      НАМ?
      • 0
        Нормальные алгоритмы Маркова.
  • +4
    После ходов 1.е4 h5 2.Qf3 h4 3.Bc4 h3 4.Q:f7 черные в стиле гроссмейстера О. Бендера сделали ход Bf8:f7. Я был настолько обескуражен, что сдался.
    • 0
      Вы уж не ждите от этого умственного упражнения многого :) Там даже анализ ваших ходов не производится, получается, что компьютер видит ваши фигуры только в тот момент, когда рубит.
      • +1
        Это я так, если вы захотите совершенствовать. Сам факт того, что вы сделали шахматы на sed-е вызывает восхищение.
  • 0
    Ура! Болк — торт!
    • +1
      sed: 312: chess.sed: transform strings are not the same length
      • 0
        Нужен sed с поддержкой utf-8
        • +1
          Я и не ожидал, что сейчас остались другие!
  • +1
    Мсье bolk, вы, наверное, и более качественную реализацию шахмат писали, причем более удобным способом? Может быть сделаете статью? Было бы интересно узнать из первых уст о создании шахмат. Хотелось бы услышать именно про взаимосвязь движка и оболочки (графического исполнения), да и про саму оболочку тоже.
    • 0
      Нет, не писал, увы :)
    • 0
      Наверняка по этой теме есть много книг, тема-то старая.
      • 0
        Там в основном про движок — про отсечение ненужных вариантов. А вот про то, как этот алгоритм передвигает фигуры по доске редко пишут. Именно визуализация идеи (причем не только шахмат) и интересует.
      • 0
        кстати, уже была ваша статья про шахматы: habrahabr.ru/post/128549/
        и ваш пост «про пару недель не поспать» уже был: habrahabr.ru/post/128549/#comment_4251342
        • +1
          Doom пока не обещаю :)

          Шахматы были да, но там через сеть два человека друг с другом играли и баш всё-таки на пару порядков проще «седа» :)
    • 0
      Шахматы для шахматных оболочек я писал давным давно, там взаимодействие — текстовое через банальный ввод и вывод, который оболочка перенаправляет на себя, и может натравливать разные программы друг на друга.
  • +2
    Шикарно, ты бог=)
  • 0
    Спасибо!
  • +1
    Я уже начинаю сомневаться по поводу «недостаточно гик» :C
    • 0
      Intel® Core(TM) i5-3210M CPU @ 2.50GHz, (lenovo tp x230)
      linux gentoo 64b
      4.25s user 0.01s system 99% cpu 4.284 total
      • 0
        В Линуксе, по-моему, гнушный сед, у меня с гнушным тоже результат лучше:

        3.29 real         3.29 user         0.00 sys
        
        • 0
          А я-то думаю почему у меня результат как у автора. Похоже на правду:

          model name: Intel® Core(TM)2 Duo CPU P8700 @ 2.53GHz

          6.06user 0.00system 0:06.17elapsed 98%CPU (0avgtext+0avgdata 33136maxresident)k
          6.09user 0.00system 0:06.16elapsed 98%CPU (0avgtext+0avgdata 33136maxresident)k
          6.05user 0.02system 0:06.19elapsed 98%CPU (0avgtext+0avgdata 33136maxresident)k
    • +2
      У меня эти шахматы больше похожи на space invaders

      image
      • 0
        Видимо шрифт не юникодный или консоль.
        • +1
          Жду Space Invaders!
      • 0
        Хардкор, только хардкор :)
  • +2
    может напишите хороший туториал по sed?
    • +1
      Пока сил на это нет :) Может потом попробую.
    • 0
      Месячник квайнов закончился, теперь все за sed и awk возьмутся?
  • 0
    Извините, что не по теме, какой шрифт используется на скриншотах?
    • 0
      Есть серьёзное подозрение, что это Monaco. Косвенно подтверждается упоминанием мака.
      • 0
        Большое спасибо!
        • 0
          Так и есть, это Monaco :)
        • 0
          Да, в общем-то, не за что :)
  • 0
    Вы нереально круты. Я даже боюсь открывать исходник на ночь.
  • +1
    Я немного был в шоке, когда слон сделал ход f5 f3 и съел моего ферзя)))
    Мои слоны тоже могут не по правилам ходить.
    Вообще, снимаю шляпу.
    • +1
      Тут видимо какой-то баг, я программу старался отладить, но баги всё же могут быть.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.