Нужен алгоритм определния мата

Всем привет!
Программа без интеллекта, только управляет игрой, играют два человека, нужно определить окончание партии. Пока у меня только такая мысль: проверить возможность перемещения короля и возможность перекрыть/съесть атакующую фигуру, но похоже, будет много проверок.
Полагаю, есть более оптимальные алгоритмы, хотел бы услышать ваше мнение.

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

Если я вас правильно понял, вы предлагаете следующий алгоритм:
брать свою фигуру и ставить ее на следующую легальную клетку и проверять, стоит ли король под шахом, и так все клетки, потом брать следущую фигуру и так - пока не пройдем по всем фигурам.
Вы это предлагаете? Поправьте, если я ошибся.

Мой вариант на порядок быстрее: для короля будет максимум 8 проверок, далее, если все таки король остается под шахом, атакуем каждую клетку линии атаки. Но мне кажется есть еще более производительные алгоритмы, но пока я еще не придумал.

Интересная у Вас программа. А что, проверять каждый сделанный человеком ход ей не надо ?

Я не понял ваш вопрос.
Ходы на корректность проверяются, но проверить ход и определить мат - совсем не одно и тоже. Программа, конечно, не даст сделать ход, если стоит мат, но она и не знает, что ходов то больше нет, вот это я и пытаюсь определить программно.

Это мой стиль, я не могу без этого))

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

Люблю быстрые алгоритмы, иначе не вижу смысла писать программы вообще.

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

Vital72, вообще то игра заканчивается еще в случае пата, троекратного повторения позиции, по правилу 50 ходов (с учетом исключений). Вашему алгоритму что, проверять все это не нужно?

Честно говоря, я не понял о чем вы. Я не спец по шахматам и что такое "правило 50 ходов" не знаю. Если вы мне скажете, где в моем алгоритме недоработка, буду признателен.

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

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

2) Произошло трехкратное повторение одной и той же позиции (с сохранением очередности хода и возможности/невозможности рокировки).

3) Сделано 50 ходов подряд без взятий и продвижений пешек (правило 50 ходов).

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

Нет никакого списка исключений.

Меня такие тонкости не интересуют, мне нужен только один момент - определение мата, все остальное - только не в тему.

Извиняюсь. Их, оказывается, полностью отменили, а я не знал.

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

Пат то у Вас сделан ? Мат это вроде тоже самое + король под шахом.

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

Пат не сделан, но думаю, проблем сделать, имея алгоритм с матом, это не составит

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

А что написано на кнопочке и какого она цвета ?

Опредeлил логически.

А кнопочка была, мне кажется, зеленая.

Да пошутил я про кнопочку, извините.
А "логически" это определить невозможно. Вы же не видите, как пользователь, "изнанки".

Сервер устает каждый раз перебирать ходы?

Мало ли... Я вот своих кишков тоже ни разу не видел еще, однако берусь утверждать, что они у меня есть. С вероятностью этак в 99,9%..

Лошади устают. Серверу, при нескольких тысячах пользователей играющих одновременно, могут просто выйти ресурсы. Вот так взять, и выйти...

Движок на моей машине смотрит 0.5 мегапозиций/секунду. Это с функциями оценки позиции. Определения мата требует перебор допустим на два полухода (ход черных/ответ). Что примерно 40^2 = 1600. Итого получаем возможность обработать 300 ходов в секунду.

4)Если на доске возникло такое соотношение материала, при котором невозможно объявить мат ни одной из сторон. Отличается от п.3

А проверять легальность/результат партии на клиенте слабо?

Для проверки мата нужно сгенерировать все ходы, и для каждого проверить легальность. То есть 1 генерация ходов, 40 исполнений, 40 проверок не бод боем ли король, и одна проверка не под боем ли король на входе.

Ничья еще фиксируется в случае просрочки времени одним из участников, когда нет кооперативного мата.