Объявить МАТ

← →
McSimm (2002-02-25 20:30) [40]

2Merlin © (22.02.02 01:32)
По почте отсылал соображения. Как думаешь, в этом есть смысл?

← →
VID (2002-02-25 21:34) [41]

объявить мат ? проше простого :
ShowMessage ("Идите на ХХХ!!!");

:)))

← →
False_Delirium (2002-02-26 03:45) [42]

Здра ту олл..:)

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

Каждая клетка имеет 9 точек расположения потенциальных атакующих плюс две "лошади". Это общий случай, когда клетка не расположена вплотную к краю, соответственно в обратной ситуации нужно исключать позиции атакующих. И есть ф-ция котрая определяет атакующих.

Есть несколько множеств, классифицирующих фигуры по способу атаки. Атакующие по дигонали, по горизонтали и вертикали, Г-образные. Соответственно Дама относится к первым двум. Поле - матрица структур, каждая из которых должна содержать название фигуры, расположенной в клетке, либо nil ..:).. Соответственно фигуры - структуры с присужими им полями, среди которых должна быть пренадлежность к виду атаки.

Теперь при атаке короля нужно проверить лишь 9 точек и рассмотреть положение вражеских "Коней":
1) Проверить дигонали
2) Проверить вертикаль и горизонталь
3) "Кони", соответственно

Проверяя каждую точку(каждое направление до первой встреченой фигуры) на наличие вражеской фигуры, сопоставлять найденные фигуры по виду атаки(по диагонали например Офицер, по ортономированным линиям "Тура", Дама в обе):

Function CheckAttackPos(const Cell : TPosition; CheckingAttackType : AttackType) : Boolean ;
begin
case CheckingAttackType of
{это множества}
диагональ : if (Field[Cell.X,Cell.Y].Figure.AttackType = Diagonal) and not Field[Cell.X,Cell.Y].Ally then ... ;{или Cell.Figure in EnemyDiagEnsemble - а из вражеского множества фигур соответственно исключать "убитые"}
Orto : ... ;
Конь : ... ;
end
end ;
//EnemyDiagEnsemble - Множество Фигур врага, атакующих по диагонали
//Cell.Figure.AttackType - Тип атаки фигуры, стоящей на проверяемой клетке.
-------------------------------------------------------------

Непосредственно МАТ.

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

И БОТа потом будет проще написать.

P.S. Писл кратко как мог..:)..если что - поясню.

← →
False_Delirium (2002-02-26 03:50) [43]

"Поле - матрица структур, каждая из которых должна содержать название фигуры, расположенной в клетке, либо nil ..:).. "-
Не то хотел написать.,:))

Поле - матрица ссылок на структуры фигур..:)..о!.:)

← →
Merlin (2002-02-26 04:06) [44]

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

← →
JohnnyCrisJoe (2002-02-26 08:52) [45]

2Merlin: А каким образом ты определяешь, шах или нет? Дело в том, что в алгоритме, который я пытаюсь сообразить(даже интерфейс написал, во как:).. ), половина расчётов на вероятность мата происходит в проверках на шах, а этих проверок на порядок больше(кроме как перебором всех фигур на все варианты ходов я никак не могу это реализовать). Поэтому интересно было бы посмотреть на твой весьма элегантный и лаконичный скрипт © Merlin (20.02.02 16:11) . Предполагаю, что собранные в нём данные сократят работу на порядок.

← →
False_Delirium (2002-02-26 09:00) [46]

Да-да...именно..:))..в том и заключается суть мной написанного...
если фигура открывает шах, то следует лишь проверить несколько условий, а именно :
1) относительно короля как стояла фигура : Диагональ, горизонталь, вертикаль.
2) Пройти от места, где стояла фигура в направлении определённом в первом пункте.
3) Если обнаружена фигура врага по напрвлению, тогда просто проверить к какому типу атакующих она относится.....

Напрмер :
Ферзь закрывает короля справа по горизонтали. Отойдя Ферзь открыл короля. Програмно определяем что ферзь был справа по горизонтали ; от точки его расположения и до конца доски, либо до первой встретившейся фигуры, двигаемся вправо. Если обнаруженная фигура - вражеская то проверяем, она будет атаковать короля в том случае если относится к множеству атакующих по горизонтали/вертикали.

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

← →
Shaman_Naydak (2002-02-26 10:13) [47]

>> Merlin
Да, Зона Потенциального Влияния рассчитывается до конца доски.
Теперь поподробнее о закрытии шаха фигурой.
1. ВСЕ Векторные фигуры, которые потенциально могут шлепнуть короля при перемещении какой-либо фигуры, перечислены в Поле Потенциального Влияния поля Короля.
=> Фигура может открыть открыть шах на короля только в том случае, если она находится под ударом одной из фигур из вышеперечисленного списка,то есть в терминах алгоритма
(Поле Потенциального ВЛияния короля AND Поле Влияния фигуры <> 0)
Но уточняю, это необходимое, но не достаточное условие.
Я так думаю, 90% проверок оно удовлетворит, так как мало какие фигуры могут открыть вектор до короля :))
Но для окончательного решения необходимо прогнать вектор от фигуры и до короля на предмет наличия между ними еще одной фигуры, если такой нет, тогда действительно так пойти нельзя..

В принципе, эту проверку можно исключить, если строить Зону Потенциального Влияния до 1-й же фигуры(точнее до 2-й, так как до 1-й идет просто Зона Влияния), но не советую, так как тогда после каждого хода придется рассчитывать всю матрицу (вышеупомянутая РАЦУХА пропадет, а птичку жалко)

И еще раз повторюсь по поводу того, что прежде чем делать проверки надо построить Матрицу Разрешенных Ходов. Тогда эти проверки попадут туда и просто у такой фигуры не будет ни одного разрешенного хода.

Я уж не говорю, что имея на руках Матрицу Разрешенных Ходов, ее можно и Нужно применить не только для расчета шаха, но и для такой прозаической цели, как какой сделать ход, однако :))

Желаю удачи!

← →
Shaman_Naydak (2002-02-26 10:16) [48]

>> JohnnyCrisJoe ©
За скромное вознаграждение я готов написать свой "элегантный и лаконичный скрипт".. но этта, небезкорыстно, конечно :)
Как пишут врачи: "Хирург конфет и цветов не пьет, однако"

← →
Merlin (2002-02-26 15:03) [49]

> False_Delirium
Понял. Да, возможно, так оно и будет наиболее удачно... подумаю...
> Shaman_Naydak
Если можешь написать, я только приветствую, но требуется это сделать на Perl-е ;)

← →
Shaman_Naydak (2002-02-26 15:49) [50]

А почему, собственно говоря, на Перле? Дельфи уже не годится что ли?
Я так понимаю, что пишешь не собственно шахматную программу, а прогу-посредника между людьми..

И все равно, Дельфийский сайт, а реализовывать обязательно на Перле.. Абидно, панимаиш

← →
Владислав (2002-02-26 17:40) [51]

> Merlin © (26.02.02 15:03)

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

:)

← →
Mystic (2002-02-26 18:28) [52]

1) Если делать шахматы, то с перебором всех ходов. В процессе выбора хода так или иначе перебор присутствует.

2) Если после 3 полуходов сбивается король, то мат.

← →
Merlin (2002-02-26 18:35) [53]

> Shaman_Naydak © (26.02.02 15:49)
> А почему, собственно говоря, на Перле? Дельфи уже не годится
> что ли?

Я пишу серверную часть, сервер будет под Linux. Делать на Kylix гн хочется, т.к. в нем много багов.

> Владислав © (26.02.02 17:40)
> Нужно было изначально указать цель этой программы.

В вопросе, вроде, ясно: "Как програмно определить, что поставлен мат?"
Т.е. есть некое расположение фигур, хочется знать, это Мат или нет. Вот и все, никаких искуственных интелектов не надо :) Только одна загвоздка, сделать это максимально быстро, т.е. с минимальным кол-вом циклов.

> Mystic © (26.02.02 18:28)
>
> 1) Если делать шахматы, то с перебором всех ходов. В процессе
> выбора хода так или иначе перебор присутствует.

Нет, я не ишу програму, играющую в шахматы. Это очень сложная задача, для просто "а не написать ли" и "потрепаться" не тянет :)

> 2) Если после 3 полуходов сбивается король, то мат.

Не понял.

← →
Mystic (2002-02-26 21:24) [54]

Прочитал вопрос, немного не то имел в виду. Предложение такое:

Проверка шаха
=============

От короля отходит 8 направлений. Идем по каждому из них:
1. Если на направлении "опасная фигура" (например, слон или ферзь по диагонали), то
a) устанавливаем признак шаха
b) соседние [два] СВОБОДНЫЕ поля с королем в этом направлении помечаем как

недоступные (естественно, что если опасная фигура стоит на одном из этих полей, то оно

доступно)
c) все поля между королем и фигурой (включая фигуру) помечаем как страшные

2. Если на направлении стоит наша фигура, а за ней опасная, то наша фигура помечается как

как связаная

Смотрим не более 8 полей от короля на ход коня. Если конь присутсвует, то
1. Шах уже есть, устанавливаем признак двойного шаха
2. Шаха еще нет - шах есть, поле коня помечаем как страшное

Смотрим не более 2 полей от короля на взятие пешки. Если пешка присутсвует, то
1. Шах уже есть, устанавливаем признак двойного шаха
2. Шаха еще нет - шах есть, поле пешки помечаем как страшное

Проверка мата
=============

1. Патаемся уйти королем на доступное поле. Для каждого такого поля смотрим, атаковано ли

оно фигурой соперника (тест на шах с выкинутой установкой флагов). Если нам удалось убежать

- мата нет

2. Двойной шах? - Мат

3. Для каждого страшного поля ищем НЕсвязанную нашу фигуру, которая была бы в состоянии его занять. Если такая фигура найдена, то мата нет.

> Merlin
Следующий вопрос про пат?
А потом про список всех возможных ходов?
Если задашь, я брошу все и завалю еще один проект :)))

← →
False_Delirium (2002-02-26 22:00) [55]

Перл .??.:)

Будет сильно тормозить, даже при ФастЦги и(или) мод_перле.

Я считаю что лучше скомпилировать на Си, а в перле обрабатывать поступившие данные и передавать их в пайпе "ехе`шнику" для обработки, и также принимать ввиде упакованого скаляра, чем всё пересчитывать в скрипте.А так даже оптимизации не хватит, а если ещё и сервер будет загружен расчётами нескольких игр..??.:)..

← →
Кулюкин Олег (2002-02-27 12:46) [56]

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

← →
Merlin (2002-02-27 12:55) [57]

> False_Delirium © (26.02.02 22:00)
> Перл .??.:)
> Будет сильно тормозить, даже при ФастЦги и(или) мод_перле.

Вообще-то FastCGI и modperl здесь не причем, т.к. скрипт не будет работать на WEB, а будет демоном.
А тормозить... что-то я сомневаюсь... на http://games.mastak.ru мои скрипты ("Покер" и "Очко") прекрасно держали до 200 запросов в секунду.

> Я считаю что лучше скомпилировать на Си, а в перле обрабатывать
> поступившие данные и передавать их в пайпе "ехе`шнику" для
> обработки

Для чего такой изврат? Делать на Си, так уж делать все на Си. но мне на Perl проще, и быстрее и отлаживаться удобнее. А будет нехватать, перепишу на Си... переписывать проще, нежели писать с нуля.

Я вижу, что все алгоритмы были из соображения, что есть двумерный массив, где фигуры расположены на соотв. "клетках", у меня же был массив фигур в свойствах которых указывалась текущая клетка... По ходу дела придется переписывать :(

← →
Suntechnic (2002-02-27 17:39) [58]

>Merlin © (27.02.02 12:55)
>Я вижу, что все алгоритмы были из соображения, что есть двумерный массив, где фигуры расположены на соотв. "клетках", у меня же был >массив фигур в свойствах которых указывалась текущая клетка...

Для пргограммиста, впрочем как и для игрока в шахматы, что главное? Нестандартное мышление... ;)

← →
False_Delirium (2002-02-27 19:41) [59]

> Вообще-то FastCGI и modperl здесь не причем, т.к. скрипт
> не будет работать на WEB, а будет демоном

ТОгда всё ясно.:)

> Для чего такой изврат? Делать на Си, так уж делать все на
> Си. но мне на Perl проще, и быстрее и отлаживаться удобнее.
> А будет нехватать, перепишу на Си... переписывать проще,
> нежели писать с нуля.

Солидарен.:) КОму где удобней, там лучше и писать..:)

> Я вижу, что все алгоритмы были из соображения, что есть
> двумерный массив, где фигуры расположены на соотв. "клетках",
> у меня же был массив фигур в свойствах которых указывалась
> текущая клетка... По ходу дела придется переписывать :(

Первое что пришло мне на ум, так это объект для каждой фигуры в которых описаны :
Сторона
Позиция на доске(Х,У)
Принадлежность к типу атаки
Алгоритм передвижения - на случай бота
Функция(Предыдущая позиция - Куда походили) возвращающая допустим ли ход.
Функция(Функция в качестве параметра определяющая действие в зависимости от типа атаки) просчитывающая зону атаки, кого и как атакует.

Массив клеток, которые атакуют данную фигуру.

Функция просчитывающая фигуры, которые её атакуют, т.е. 9 точек и два коня(см. выше) моежт быть в классе поля и заполнять этот массив.

Мажно сделать ещё два массива, но при игре Player vs Player нет необходимости.
Массив фигур стоящих на линии атаки к королю(если конечно сама фигура может атаковать короля с данной позиции при отсутствии помех), при каждом ходе можно сверять, если фигура присутствует в этом массиве и ушла с линии атаки, то удалить её. Если массив пуст то данный объект атакует короля.

Массив, который определяет преграды до своего короля, если преград нет, тогда эта фигура закрывает своего короля от атаки по какой-то прямой. - но это опять же при необходимости, тоже нужно доводить до ума, но в случае с ботом, должно быть обязательно..:))

...

ПОтому и написал так. Думаю так проще будет оперировать фигурами. Но есть вариант что массив фигур тоже актуален, но для этого нужно разработать другой алгоритм. Но это я так, свой вариант реализации..:)..

Удачи в шахматах.:)

← →
JohnnyCrisJoe (2002-02-27 20:56) [60]

> Merlin © (27.02.02 12:55
> Я вижу, что все алгоритмы были из соображения, что есть
> двумерный массив, где фигуры расположены на соотв. "клетках",
> у меня же был массив фигур в свойствах которых указывалась
> текущая клетка... По ходу дела придется переписывать :(

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

← →
Mystic (2002-02-28 10:35) [61]

> Кулюкин Олег (27.02.02 12:46)
> Помнится лет 10 назад на "Микроше" были шахматы, так там
> игра заканчивалась когда съедали короля.
> Т.е. проиграть можно было и из-за собственной невнимательности
> (убрал короля из под шаха, да не туда :).

Это правила блица

> Merlin © (27.02.02 12:55)

> Я вижу, что все алгоритмы были из соображения, что есть
> двумерный массив, где фигуры расположены на соотв. "клетках",
> у меня же был массив фигур в свойствах которых указывалась
> текущая клетка... По ходу дела придется переписывать :(

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

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

← →
Suntechnic (2002-02-28 16:54) [62]

← →
Mystic (2002-02-28 18:39) [63]

> Это в каком таком блице короля разрешается "скушать"? :)

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

← →
Suntechnic (2002-02-28 19:16) [64]

>Mystic © (28.02.02 18:39)
>В серьезных турнирах за каждый недоступный ход добавляется 2 мин на обдумывание...

Ты слегка напутал. Это не в блице, а в быстрых шахматах. Быстрые шахматы это с контролем времени от 15 до 60. А в блице всё несколько по-другому.

Вот тут почитай:
http://www.clubkasparov.ru/rev/arbiter/arb06.htm

← →
Suntechnic (2002-02-28 19:27) [65]

Да, совем забыл... короля не бъют не при каких раскладах :)

← →
Владислав (2002-03-01 06:57) [66]

Международные шахматные правила:

http://handbook.fide.com/handbook.cgi?level=E&level=E1&

выдержка из приложения про блиц:

"However, the opponent is entitled to claim a win before making his own move."

← →
Donal_Graeme (2002-03-03 03:00) [67]

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

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

1.уход от шаха самим королём так же решается зонами влияний, которые были уже описаны выше.

далее, если атакующих фигур 2, то бессмысленно рассматривать остальные варианты ухода.

для решения 2-го и третьего методов можно было бы представить каждую фигуру, как класс, у которого есть свойсто CanMove (может ли фигура ходить в данный ход) и метод CanBeat (x, y), (может ли фигура пойти на клетку x, y); соответственно CanMove пересчитывается после каждого хода и в самом простом случае может указывать только на то, закрывает ли эта фигура короля от шаха.
теперь к алгоритмам.

2. для проверки того, можем ли мы съесть атакующую короля фигуру, достаточно пройтись по всем своим фигурам с CanMove = True и проверить, могут ли они бить клетку, на которой стоит атакующая фигура.

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

3. зная координаты атакующей фигуры и координаты короля, вычисляем для каждой своей фигуры с CanMove= True, может ли она пойти на клетку между атакующей фигурой и королём... самое простое, что приходит в голову - перебор всех свободных клеток на линии атаки для каждой фигуры, которая может двигаться.

Объявить МАТ Найти похожие ветки