Шахматы на чистом 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 века — нет рокировки и взятия на проходе, уход от шаха примитивный. Так же я не сделал контроль за правильностью хода человека, так что, если хотите самоутвердиться за счёт беззащитной машины, можете сразу срубить короля.

    Скачать игру можно с проекта на Гитхабе, там же небольшая инструкция как играть. О багах, если будут, пишите в комментарии или личку, но когда исправлю — не знаю, после полутора тысяч строк на «седе» мне требуется перерыв.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 67
    • +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 + вечный цикл — это практически нормальные алгоритмы Маркова (Тьюринг-полный язык).
                              • +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
                                                                Тут видимо какой-то баг, я программу старался отладить, но баги всё же могут быть.
                                                              • 0
                                                                VP of sed

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