1. JavaScript / Говнокод #11734

    +160

    1. 1
    2. 2
    3. 3
    4. 4
    if(h&&c-L<0)return y^=8,G--,L;
    
    // Toledo просрал оптимизацию на 2 байта ;)
    if(h&&c<L)return y^=8,G--,L;

    В общем-то этот пост не про говнокод, а про обещанную попытку привести в понятный вид шахматы,
    упомянутые в http://govnokod.ru/11704.

    https://github.com/bormand/nanochess
    Читаем, играем, обсираемкомментируем...

    Запостил: bormand, 09 Сентября 2012

    Комментарии (32) RSS

    • Было бы очень круто, если бы вы очень кратко расписали алгоритм работы. А то времени сейчас нет. Свой говнокод рефакторю. Обещаю не постить.
      Ответить
      • показать все, что скрытоОчень кратко... ну ок.

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

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

        Остальное детали ;)
        Ответить
        • Всё же нужна статья. И дорефакторить надо попытаться, внятные имена переменным выдать и всё такое. Или найти этого самого Toledo и провести терморектальный криптоанализ обфусцированного им же кода.
          Ответить
        • >Затем оценка уточняется путем поиска лучшего ответа противника на данный ход и вычитания его оценки из текущей.
          То есть почти каждый раз выбор второго по лучшести хода может мешать тактике противника?

          >При переборе ходов противника используется несложное отсечение - если найден ход противника с оценкой, большей чем разность оценок нашего текущего и нашего лучшего ходов - поиск прерывается
          То есть глубина анализа ходов всего 2 хода?
          Ответить
          • показать все, что скрыто> То есть почти каждый раз выбор второго по лучшести хода может мешать тактике противника?
            Второй по лучшести ход хуже первого по лучшести - так что скорее всего выбрав его можно испортить игру только себе ;)

            > То есть глубина анализа ходов всего 2 хода?
            Нет, может копаться и глубже, регулируется константой, помеченной как /*ply*/. Но т.к. это js - больше 4 туда писать не стоит.
            Ответить
            • показать все, что скрытоДа, кстати, если там написано 2 (а там написано 2 по дефолту), то глубина поиска 3 хода - свой, противника, свой.
              Ответить
              • > 3 хода
                Это три полухода, то есть полтора хода.
                Wikipedia: Полуход — один ход белых или один ход чёрных, единица измерения и минимальная единица изменения позиции на шахматной доске. Два полухода составляют ход, представляющий собой одну строку в записи шахматной партии на бумаге.
                Ответить
                • показать все, что скрыто> Это три полухода
                  Хм. Спасибо за исправление. Не знал, что это полуходы.

                  P.S. Надо перечитать шахматную терминологию, дабы не спороть еще какую-нибудь хуйню.
                  Ответить
        • >При переборе ходов противника используется несложное отсечение - если найден ход противника с оценкой
          http://ru.wikipedia.org/wiki/Альфа-бета_отсечение
          Ответить
          • показать все, что скрытоАга, я забыл как именно работает альфа-бета отсечение, открывать вики было лень, поэтому написал "несложное отсечение"...

            P.S. Спасибо за линк, придется его прочесть, освежить память ;)
            Ответить
        • Я вот над чем размышляю: оценка позиции - наиважнейшее в шахматном алгоритме. Если оценщик работает хорошо, то алгоритм делает умные ходы. Это стратегия - постепенное улучшение и развитие своей позиции. И для меня лет 15 назад представлялось полнейшей загадкой как машина может анализировать ситуацию на доске.
          Тактика же это просто глубина счета вариантов и тут мы упираемся в возможности процессора.

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

          >сначала грубо оцениваем ход, по нескольким характеристикам - съедаем ли мы фигуру противника, ведет ли ход к захвату центра, будет ли шах и т.п

          У нас есть входной набор параметров, но как они сочетаются - обычная сумма этих факторов помноженная на коэффициенты? Это тривиально.

          Наверняка если натренировать сеть на различных партиях для оценки ситуации, то думаю это будет неплохой идеей.
          Ответить
          • показать все, что скрытоХм. Т.е. что-то типа персептрона, на вход которому подается доска, а на выходе он показывает какой из ходов ему больше всего нравится? Ну идея интересная, и, кстати, мне кажется живые шахматисты тоже видят многие ситуации без перебора, просто взглянув на доску.

            Но я вижу вот такие проблемы:
            1) Непонятно как организовать выход сети - в районе 4000 выходов - по одному на каждый допустимый ход?
            2) Сеть запросто может выдать недопустимый ход - что делать в этом случае? Видимо нужно ее сразу же за это "наказать", проведя цикл обучения, в котором данный ход помечен как плохой.

            P.S. Про 4000 я конечно загнул. Ходов меньше.
            Ответить
            • >на вход которому подается доска, а на выходе он показывает какой из ходов ему больше всего нравится
              Нет, но около того. На вход характеристики позиции, и по оценке каждой позиции судить о варианте.
              И я наверное был неточен, когда сказал что это будет не стратегия. Скорее интуитивное понимание позиции - типа сдвоенные пешки - плохо, или слон лучше коня, но когда позиция закрытая, то лучше таки конь.
              А стратегия - это план. Например план атаки на короля (типа примерный порядок действий в голове, без расчета) - вот такое как сделать я не представляю, чтобы машина понимала и планировала.
              Ответить
              • > слон лучше коня
                > piecesCosts = [0,99,0,306,297,495,846], // cost of the pieces (empty,pawn,king,knight,bishop,rook,quee n)
                > 306,297 knight,bishop

                Оно играет лучше, чем p4wn?
                Ответить
                • > слон лучше коня
                  Общеизвестный факт. Но с оговоркой:
                  > но когда позиция закрытая, то лучше таки конь.
                  Бывает и такое что слон/конь лучше даже чем ладья, из-за своего расположения, конфигурации пешек, итд.

                  Может из-за специфики движка Toledo с конём играет лучше.
                  Ответить
                • Вообще силу фигуры можно грубо определить по количеству полей, которое она атакует (это по ситуации).
                  А в целом - сколько полей она способна покрыть. Так вот слон (даже из угла) лучше, потому что в открытой позиции контроллирует больше чем конь или столько же.
                  Конь даже стоит в центре доски - 8 полей, максимум. А конь в углу - это вообще 2 поля.

                  Плюс слон имеет в 2-3 раза большую скорость перемещения.
                  Ответить
                  • Ясно одно - слонов надо понерфить.
                    Ответить
                  • > силу фигуры можно грубо определить по количеству полей, которое она атакует
                    ага,
                    конь - 2..8
                    слонь - 7..13
                    где тут логика?
                    Ответить
                    • Логика в том, что обычно на доске кромя коня со слоном есть другие фигуры и пешки, слон зачастую стеснен своими пешками.
                      Конь не стесен ничем, потому что прыгает.
                      Ответить
                      • И это какбы подводит нас к выводу, что в эндшпиле сила легких фигур отличается от силы в миттельшпиле...
                        Ответить
                        • >> но когда позиция закрытая, то лучше таки конь.
                          Сколько раз мне нужно это повторить?
                          Сила фигур различается радикально, в зависимости от ситуации. Ладьи в самом начале игры вообще нихуя не стоят. Они статисты.

                          >>Вообще силу фигуры можно грубо определить по количеству полей, которое она атакует
                          Всё тот же принцип.
                          Ответить
            • показать все, что скрыто>>Хм. Т.е. что-то типа персептрона
              у вас там еще не ссут все кипятком от нейронок?
              Ответить
    • показать все, что скрытоУниверситет Хельсинки присвоил 20-летней шведской экоактивистке Грете Тунберг звание почетного доктора факультета теологии. Об этом сообщается на сайте учреждения.
      Ответить

    Добавить комментарий