Блог

Я пишу программу, которая должна уметь читать и анализировать шахматные ходы (SAN).

Вот пример возможных принятых ходов:

 e4
Nf3
Nbd2
Nb1c3
R1a3
d8=Q
exd5
Nbxd2
...
  

Сначала я написал NFA, затем преобразовал его в грамматику, а затем преобразовал в регулярное выражение.

С моими соглашениями это выглядит так

 pln   plxln   plnxln   plnln   plln   pxln   lxln=(B R Q N)   lxln   lnxln=(B R Q N)   lnxln   lnln=(B R Q N)   lnln   ln=(B R Q N)   ln   pnxln   pnln
  

где:

p является символом set {B,R,Q,N,K} (или думать об этом как (B R Q N K) = [BRQNK]

l является символом среди [a-h] интервалов (чувствителен к регистру)

n является числом среди [1-8] интервалов

представляет операцию объединения … если я правильно понял, (B R Q N) это [BRQN] на языках программирования регулярных выражений.

= это просто обычный символ… в шахматных ходах он используется при продвижении (например, e8 = Q)

x это тоже обычный символ … используется, когда, перемещая свою фигуру в этом месте, вы берете фигуру противника.

( / ) : Как в математике

Я попытался разобрать первую часть pln как: [BRQN][a-h][1-8] в онлайн-тестере регулярных выражений java и работал на ход, подобный Nf3 . Я не понял, как сделать объединение для составного выражения (например pln plxln ) … также как я могу пометить части регулярного выражения, чтобы при его обнаружении я получал всю информацию? Я пытался прочитать документы об этом, но не понял.

Любой совет?

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

 [BRQNK][a-h][1-8]|[BRQNK][a-h]x[a-h][1-8]|[BRQNK][a-h][1-8]x[a-h][1-8]|[BRQNK][a-h][1-8][a-h][1-8]|[BRQNK][a-h][a-h][1-8]|[BRQNK]x[a-h][1-8]|[a-h]x[a-h][1-8]=(B R Q N)|[a-h]x[a-h][1-8]|[a-h][1-8]x[a-h][1-8]=(B R Q N)|[a-h][1-8]x[a-h][1-8]|[a-h][1-8][a-h][1-8]=(B R Q N)|[a-h][1-8][a-h][1-8]|[a-h][1-8]=(B R Q N)|[a-h][1-8]|[BRQNK][1-8]x[a-h][1-8]|[BRQNK][1-8][a-h][1-8]
  

Это, очевидно, немного некрасиво. Я могу придумать 2 возможных способа сделать это лучше:

• С COMMENTS помощью флага вы можете добавлять пробелы.
• Объедините возможности вместе более приятным способом. Например, [BRQNK][a-h]x[a-h][1-8]|[BRQNK][a-h][1-8]x[a-h][1-8] может быть переписан как [BRQNK][a-h][1-8]?x[a-h][1-8] .

Я также знаю об одном другом улучшении, которое недоступно в java. (И, возможно, не так много языков, но вы можете сделать это на Perl.) Подвыражение (?1) (аналогично (?2) и т.д.) немного похоже 1 , за исключением того, что вместо сопоставления точной строки, соответствующей первой группе захвата, оно соответствует любой строке, которая могла соответствовать этой группе захвата. Другими словами, это эквивалентно повторной записи группы захвата. Таким образом, вы могли бы (в Perl) заменить первое [BRQNK] на ([BRQNK]) , а затем заменить все последующие вхождения на (?1) .

/^([NBRQK])?([a-h])?([1-8])?(x)?([a-h][1-8])(=[NBRQK])?( |#)?$|^O-O(-O)?$/

.

.

.

.

Это было протестировано на 2599 случаях. Модульные тесты см. Ниже

 describe('Importer/Game', function() {
    let Importer, Game;
    beforeEach(function() {
        Importer = require(`${moduleDir}/import`).Importer;
        Game = require(`${moduleDir}/import`).Game;
    });
    describe('moveRegex', function() {
        describe('non-castling', function() {
            //  ([NBRQK])?  ([a-h])?   ([1-8])?   (x)?     ([a-h][1-8]) (=[NBRQK])? ( |#)?/
            //  unitType?   startFile? startRank? capture? end          promotion?  checkState?
            for(let unitType of ['', 'N', 'B', 'R', 'Q', 'K']) {
                for(let startFile of ['', 'b']) {
                    for(let startRank of ['', '3']) {
                        for(let capture of ['', 'x']) {
                            for(let promotion of ['', '=Q']) {
                                for(let checkState of ['', ' ', '#']) {
                                    //TODO: castling
                                    const dest = 'e4';
                                    const san = unitType   startFile   startRank   capture   dest   promotion   checkState;
                                    testPositive(san);
                                    //TODO: negative substitutions here.
                                    testNagative('Y'        startFile   startRank   capture   dest   promotion   checkState);
                                    testNagative(unitType   'i'         startRank   capture   dest   promotion   checkState);
                                    testNagative(unitType   startFile   '9'         capture   dest   promotion   checkState);
                                    testNagative(unitType   startFile   startRank   'X'       dest   promotion   checkState);
                                    testNagative(unitType   startFile   startRank   capture   'i9'   promotion   checkState);
                                    // testNagative(unitType   startFile   startRank   capture   ''     promotion   checkState);
                                    testNagative(unitType   startFile   startRank   capture   dest   '='         checkState);
                                    testNagative(unitType   startFile   startRank   capture   dest   'Q'         checkState);
                                    testNagative(unitType   startFile   startRank   capture   dest   promotion   '  ');
                                }
                            }
                        }
                    }
                }
            }
        });
        describe('castling', function() {
            testPositive('O-O');
            testPositive('O-O-O');
            testNagative('OOO');
            testNagative('OO');
            testNagative('O-O-');
            testNagative('O-O-O-O');
            testNagative('O');
        });
        function testPositive(san) {
            it(`should handle this san: ${san}`, function(done) {
                const matches = san.match(Importer.moveRegex);
                assert(matches);
                done();
            });
        }
        function testNagative(san) {
            it(`should not match this: ${san}`, function(done) {
                const matches = san.match(Importer.moveRegex);
                assert(!matches);
                done();
            });
        }
    });
});
  

 Re: /^([NBRQK])?([a-h])?([1-8])?(x)?([a-h][1-8])(=[NBRQK])?( |#)?$|^O-O(-O)?$/
  

Это как недостаточно, так и чрезмерно.

Это исключает возможные законные ходы O-O , O-O-O , O-O#, and O-O-O#.

Она включает в себя множество строк, которые никогда не могут быть законными: e8=K, Kaa4, Nf5=B, Qa1xb7

и так далее.

Я сделал это:

 /(^([PNBRQK])?([a-h])?([1-8])?(x|X|-)?([a-h][1-8])(=[NBRQ]| ?e.p.)?|^O-O(-O)?)( |#|$)?$/
  

Включает в себя: O-O , O-O-O , O-O# и O-O-O#

Также: e.p. , N-f6 или NXf6 и Pe4 или Pe5xd6

Обновить:

Спасибо @Toto за улучшение моей версии регулярного выражения выше:

 ^([PNBRQK]?[a-h]?[1-8]?[xX-]?[a-h][1-8](=[NBRQ]| ?e.p.)?|^O-O(?:-O)?)[ #$]?$
  

Я уже некоторое время использую это на своем веб-портале.

 [BRQNK][a-h][1-8]| [a-h][1-8]|[BRQNK][a-h][a-h][1-8]|O-O|0-0-0|[BRQNK]x[a-h][1-8]|[a-h]x[a-h][1-8]|1/2-1/2|1/-O|O-/1