Объявить МАТ

← →
Merlin (2002-02-20 14:15) [0]

Вот уперся в одну проблему. Пишу программу для игры в Шахматы. Как програмно определить, что поставлен мат? Шах отследить легко, но для того чтобы определить, что этот шах является матом.. что-то уж очень большой рекурсивный цикл получается :((
А задача сделать это с наименьшими затратами и минимальноое время, т.к. задача очень критична по времени выполнения.
Уверен, что это можно решить как-то проще "по научному" :)
Какие будут предложения?

← →
VuDZ (2002-02-20 14:44) [1]

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

← →
Виктор Щербаков (2002-02-20 14:48) [2]

VuDZ © (20.02.02 14:44)
А мат в 3 хода как объявишь?

← →
McSimm (2002-02-20 15:04) [3]

>VuDZ © (20.02.02 14:44)
Уйти королем - это, к сожалению, не единственный вариант.

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

>Виктор Щербаков © (20.02.02 14:48)
Как я понял, задача не в том, чтобы найти возможный мат, а в том, чтобы определить: "сделанный ход привел к мату".

← →
VuDZ (2002-02-20 15:32) [4]

> Как програмно определить, что поставлен мат?

по-моему я ответил на _задаваемый_ вопрос

← →
McSimm (2002-02-20 15:38) [5]

>VuDZ © (20.02.02 15:32)
>если вокруг короля есть хоть один 0 или 2 тогда это ещё не мат
А если вокруг короля нет ни 0 ни 2, но есть возможность прикрыть его своей фигурой?

← →
troits (2002-02-20 15:40) [6]

Проверить все возможные варианты одного хода (задача не рекурсивная) и проверять, будет ли находиться король под ударом. По - моему, в OWL-chess так и делается.

← →
VuDZ (2002-02-20 15:43) [7]

2McSimm по моему, это уже задача алгоритма расчитать возможные пути прикрытия.
Идите вы отсюды, некогда мне тут вашими дурацими вопросами голову забивать, я стратегией занимаюсь, а не тактикой :> (C)Филин и мыши

PS для тех кто не понял шутки юмора - я предложил вариант и не собираюсь спорить о нём, это пусть Merlin решает.
Свою идею бы лучше предложили

← →
Merlin (2002-02-20 15:54) [8]

> VuDZ ©
По вашему методу будут "ложные" срабатывания. Когда объявили шах, королю ходить некуда, программа решила, что это МАТ и закончила игру. В тоо время, как у игрокка был вариант прикрыть короля какой-то своей фигурой.
Так не пойдет.

> troits ©
Честно говоря не понял, поясните...

← →
troits (2002-02-20 16:00) [9]

Я предложил самый простой метод - "в лоб" перебрать все возможные варианты одного хода (ухода от шаха). То есть вложенный цикл по всем (своим) фигурам -> по всем возможным ходам этой фигуры. В теле цикла делаем проверку на шах. Если находится вариант, когда шаха нет - Ок, это не мат.

← →
VuDZ (2002-02-20 16:04) [10]

2Merlin - при ложном срабатывание надо будет перебрать просто варианты. Я же не сказал, что это даст 100% гарантию, просто позволит исключить ненужные расчёты

← →
Merlin (2002-02-20 16:11) [11]

> troits ©
Я тоже об этоом думал. Но уже в проверке на шах есть куча циклов, вернее проверка правильности хода чужих фигур, могут ли они сбить короля.

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

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

← →
McSimm (2002-02-20 16:16) [12]

2Merlin А каким методом определяется шах?

Вот такие мысли:

Прикрыть - это поставить свою фигуру на одну из клеток между королем и атакующей фигурой.

Нельзя ли тем же методом который определяет шах проверить такое:
-- нет ли шаха от моей фигуры одной из этих клеток? --

Это позволит сократить количество перебираемых вариантов.

← →
VuDZ (2002-02-20 16:17) [13]

ладно, может я и не прав, но, думается, чуток дополним этот вариант, можно получить то, что надо. По крайней мере, со мной согласны некоторые наши программёры, правда им сейчас до шахмат как мне до Луны - не надо и времени нет :)

← →
ProgMan (2002-02-20 16:32) [14]

В обсуждении упоминалось 2 вида спасения:
1. Уход королем.
2. Прикрыть короля.

Есть еще один вариант:
3. "Съесть" атакующую фигуру (в том числе и самим королем).

← →
Владислав (2002-02-20 19:13) [15]

Привет всем.

Один из вариантов (на вскидку :)

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

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

Естественно, событие "шах" - это только одно из условий, но если оно выполняется, то остальные условия проверять не имеет смысла. Ход уже неправильный.

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

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

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

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

В общем-то я кончил :). Если не прав, то "поливайте" критикой. Пообщаемся.

С уважением,
Владислав.

← →
Suntechnic (2002-02-20 20:00) [16]

Как тут правильно заметили возможно только 3 варианта дальнейшего развития событий. Если все три варианта FALSE, тогда мы имеем мат:
1. Уход королем.
2. Прикрыть короля.
3. "Съесть" атакующую фигуру (в том числе и самим королем).

Если первый попавшийся вариант обращает хотя бы одно из этих условий в TRUE, то это уже не мат.

С уходом короля всё ясно. Всего 8 вариантов. Только надо не забывать про т.н. двойной шах, от которого защиты нет и если уход невозможен, то это мат.

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

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

← →
Владислав (2002-02-20 20:12) [17]

> Suntechnic © (20.02.02 20:00)

Все правильно. Но если проверять на правильность следующий ход, то можно не отслеживать диагонали (и т.п.) по которым открывается шах. Проверяется в данном случае вот что: "ХОД, КОТОРЫЙ ПЫТАЮТСЯ СДЕЛАТЬ, НЕ СООТВЕТСТВУЕТ ПРАВИЛАМ".
Иными словами (это касается мата, шаха), мы создаем ситуацию, в которой следующий ход уже сделан. И если в этой ситуации король не избавился от шаха, то эта ситуация "не прокатывает", а это, в свою очередь, значит что сделанный ход не соответствует правилам.

← →
Suntechnic (2002-02-20 20:37) [18]

> Владислав © (20.02.02 20:12)
Насколько я понял, автора как раз и беспокоит прогон всех вариантов. Понятие "правильный", "неправильный" ход у него по идее уже должны существовать и вопрос именно в том, как сузить поиск возможных вариантов. Хотя может я и недопонял автора...

← →
Владислав (2002-02-20 20:47) [19]

> Suntechnic © (20.02.02 20:37)

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

← →
JohnnyCrisJoe (2002-02-21 00:42) [20]

А например такой вариант:

создаётся ещё одна матрица, в которой расписываются сферы влияния всех фигур - и своих и противника:

с... с... С - слон противника
. с. с.... П - пешка противника
.. С... П. К - мой король
. с. с. п. п П - моя пешка
с...П... с - сфера влияния слона
.....К.. п - сфера влияния пешки
........
........

И если король попадает в эти сферы влияния, то мат. -> Если при ходе короля он попадает в те же сферы влияния - мат.
Затем точно такая же проверка атакующей фигуры.

P.S. Может немного сумбурно, просто спать хочу. Видимые мной преимущества - матрица создаётся единожды за ход, и не такая уж эта и сложная процедура, а проверки на попадпние в сферы влияния - это уж вообще детский лепет...

← →
JohnnyCrisJoe (2002-02-21 00:44) [21]

Ух ты, думал что элегантно получится - а получилось как всегда. Если непоняно, завтра объясню ещё раз.

← →
Merlin (2002-02-21 02:20) [22]

> Владислав ©
Фактически ваш вариант не отличается от походить каждой фигурой и проверить сохранился ли шах.

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

Не факт! Фигура, которой я пытаюсь прикрыться может открыть второй шах. Т.е. один черт получается, что после каждого возможного хода этой фигурой проверять не остался ли шах.
В остальном все верно. Т.е. пытаться двигаться от варианта, что дает наименьшее кол-во доп. проверок и далее по нарастающей.

> JohnnyCrisJoe ©
Да, надо доп. пояснения :)

Если так сложно упростить процедуру проверки Мата, может упростить процедуру проверки шаха, и уже тогда перебор в лоб не будет столь громоздким?

Я делаю так, перебираю все фигуры противника и смотрю, может ли она сбить нашего короля, если да, то - Шах. Возможно ли здесь улучшение? :)

← →
Suntechnic (2002-02-21 04:13) [23]

>Merlin © (21.02.02 02:20)
>Не факт! Фигура, которой я пытаюсь прикрыться может открыть второй шах.
Ну нет. На этом моменте я не заострял внимания только потому, что такой ход не возможен в шахматной игре в принципе! Мат тут абсолютно не причём. Если фигура своим ходом открывает шах, то эта фигура как ходящая не расматривается вообще.

← →
Merlin (2002-02-21 04:53) [24]

> Если фигура своим ходом открывает шах, то эта фигура как ходящая не расматривается вообще.

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

← →
Suntechnic (2002-02-21 05:07) [25]

>Merlin © (21.02.02 04:53)
Я всего лишь хочу сказать, что у тебя в любом случае где-то должна стоят проверка на допустимость хода. Скажем пешка назад ходить не может. Ведь глупо перебирать варианты с ходом фигуры, если оказывается, что эта фигура не может ходить по своему определению. Т.е. я бы сказал, что это не проверка на шах, а проверка на допустимость хода. Мне почему-то кажется, что перебрать все фигуры и выяснить какие из них могут совершить ход, это гораздо быстрее, чем анализировать последствия хода.

← →
Владислав (2002-02-21 06:43) [26]

> Suntechnic © (21.02.02 05:07)

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

Точно! Но тогда программа не сможет даже сделать вывод о том, что мат через ход (или два).

← →
Suntechnic (2002-02-21 06:53) [27]

>Владислав © (21.02.02 06:43)
>Точно! Но тогда программа не сможет даже сделать вывод о том, что мат через ход (или два).
Вот и чудненько :) Нам это и не надо. Цель этого анализа не найти следующий ход, а сузить дерево поиска. На этом этапе никакая оценочная ф-ция и в помине не применяется. Просто определяем может фигура ходить или нет... Хотя честно признаюсь шахматные программы никогда не писал, несмотря на то, что играю неплохо.

← →
JohnnyCrisJoe (2002-02-21 11:40) [28]

>Merlin © (21.02.02 02:20) Да, надо доп. пояснения :)

А ведь в голове всё это так просто смотрится..
Специально картинку нарисовал(а ведь замудрил то как...)

http://johnnyboy.chat.ru/chess.jpg

Как я себе это представляю:

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

Что-то ещё больший сумбур внёс. Это всё хронический недосып.

Хотя бы на картинку посмотрим: а на ней видно, что король находится под ударом ладьи(с4) и слона(f6), но слон под ударом коня(h7), а от ладьи можно уйти (h3,h5). т.е это всего лишь шах, не мат.
Фууу.
Я думаю из рисунка всё можно понять, по мне так лучше вопросы задавайте, а я отвечать буду.
Кстати, маленькие фигурки - это возможные ходы(сферы влияния), мои фигуры чёрные.

← →
JohnnyCrisJoe (2002-02-21 11:43) [29]

2Merlin: Если идея имеет право на жизнь, то я лучше готовый алгоритм напишу, просто не учитель я!! :))

← →
Владислав (2002-02-21 15:23) [30]

> Merlin © (21.02.02 02:20)

Да, именно. А много ли таких ходов?

> JohnnyCrisJoe © (21.02.02 11:40)

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

← →
Merlin (2002-02-21 16:37) [31]

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

← →
Владислав (2002-02-21 16:45) [32]

> Merlin © (21.02.02 16:37)

Это кому адресовано? :)

← →
McSimm (2002-02-21 17:25) [33]

Если я правильно понял, проверка на шах осуществляется перебором фигур противника.

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

Попутно вопрос: Поддерживаются ли битовые операции?
(if A and B = 0, где "and" не логическое, а булевое)

← →
JohnnyCrisJoe (2002-02-22 01:29) [34]

2All: Если хватит тяму, то попытаюсь написать готовый алгоритм.
Объяснить по ходу ума не хватает :(( На оптимизацию не расчитывайте, просто все мысли будут реализованы вслух. :))

← →
Merlin (2002-02-22 01:32) [35]

> Есть подозрение, что проверить окружение короля дешевле
> с точки зрения скорости

Энто как? Ведь ферзь может объявить шах и находясь на другой стороне доски!

← →
Shaman_Naydak (2002-02-23 00:19) [36]

Пишу вот огромянное письмо с придуманным алгоритмом. Шахматных программ не писал, разряда шахматного не имею, то есть дальше имеет место быть плод воспаленной вчерашней бессоницей фантазии, так что ногами попрошу меня сильно не бить.
ПРЕАМБУЛА:

1. Разделяем все фигуры на два типа по зонам влияния:
Точечные и Векторные.
Векторные: Ферзь, два слона, две ладьи
Скалярные, Король, два коня, 8 пешек.
2. Занумеровываем их следующим образом:
0 = Ферзь, 1,2=Слоны, 3,4=Ладьи, 5=Король, 6,7=Кони, 8-15-Пешки

Строим матрицу влияния.. То есть берется массив 8*8 по 32 бита
То есть для каждой фигуры рассчитываются зоны ее влияния и в соответсвующей ячейке выставляется в 1 бит, соответствующий данной фигуре (нулевой для ферзя и т.д.).
С Точечными фигурами все просто, проставляем соответствующий бит и всего делов (при этом НЕ НАДО учитывать другие фигуры, которые возможно стоят на этом месте, наоборот все на этом и построено)
С Векторными дела обстоят сложнее:
Возьмем, скажем, ферзя, стоящего на E1 и начнем рассчитывать зону его влияния по вертикали (при этом пусть E2,E3- пусто, E4 - стоит какая-нибудь фигура (ЦВЕТ НЕ ВАЖЕН)). Получаем, что
в E2,E3,E4 - устанавливается в 1 бит 0 (Ферзь=0), а, ВНИМАНИЕ,
в E5,E6,E7,E8 - устанавливается 1 бит 16(0+16)
То есть в каждой ячейке в 32-х байтном числе хранится:
В младших 16 битах - ЗОНА ВЛИЯНИЯ фигур,
В старших 16 битах (точнее, в битах 16-20, так как остальные фигуры точечные) - ЗОНА ПОТЕНЦИАЛЬНОГО ВЛИЯНИЯ фигур.

МЕЖДУ прочим, РАЦУХА. Данную матрицу совершенно не обязательно рассчитывать после каждого хода. ЕЕ можно рассчитать в начале партии, а после каждого хода пересчитывать зону влияния только сходившей фигуры, то есть обнулить соответствующий ей (и взятой фигуры, если таковая подвернется) по всей доске и рассчитать новую зону. ВО КАК!

Данную матрицу рассчитываем как для фигур обоих цветов.

ТАПЕРИЧА СОБСТВЕННО АЛГОРИТМ:

Признак шаха: в поле короля младшие 16 бит - зона влияния <> 0
Теперь рассмотрим условия мата:
1. Если выставлено более одного бита в зоне влияния
(эта ситуация может иметь место, если например белый конь
закрывал белому ферзю шах королю, а сделав ход конем, король
оказывается под ударом и коня и ферзя)
2. Теперь пойдем оь противного..
Мат не получается, если:
а. Королю есть куда отступить, то есть хоть одно поле, куда он может пойти, в котором зона влияния = 0 И (ЗОНА ВЛИЯНИЯ КЛЕТКИ КОРОЛЯ AND ЗОНА ПОТЕНЦИАЛЬНОГО ВЛИЯНИЯ КЛЕТКИ ОТХОДА = 0)
Расшифровываю.. если король стоит под шахом векторной фигуры, например, ферзя, то клетка сзади него может иметь зону влияния = 0, так как ее никто не бьет, но тем не менее отойти он туда не может, так как в зоне потенциального влияния у этой клетки булет установлен бит 0 как и в клетке шаха (0=ферзь)
б. Атакующего можно запинать.. То есть в поле атакующей фигуры (а она = младшим 16 битам ЗОНЫ ВЛИЯНИЯ КЛЕТКИ КОРОЛЯ, см вышеизложенное) ЗОНА ВЛИЯНИЯ (тут уже рассматривается матрица,рассчитанная для обороняющегося) <> 0.
Но если собственно сожрать эту фигуру может только сам король,
то надо дополнительно проверить, что в матрице атакующего ЗОНА ВЛИЯНИЯ ЭТОЙ КЛЕТКИ = 0 (То есть фигуру никто не прикрывает)
в. И, наконец, если атакующая фигура - векторная, то поискать фигуру, которая может закрыть короля от атаки..

Я БЫ ПОМИМО МАТРИЦ ВЛИЯНИЯ рассчитывал бы сперва матрицу возможных ходов, а уж потом начинал бы катавасию с проверками..
тогда большая часть убежит в расчет матрицы ВОЗМОЖНЫХ ХОДОВ и алгоритм упростится (то есть в матрицу ходов попадет расчет для
пункта а, и если король хочет сам есть в пункте б, да и подбор фигуры из пункта в)..

Я СКАЗАЛ, как говаривали наши друзья индейцы..
Все эти алгоритмы я бы написал на ассемблере, тогда полуится ваще полная лепота.

P.S. Если идея стоящая, то с тебя, мужик, ящик пива. Из них 25% пойдет Гоблину, так как именно этот нехороший товарищ втянул меня в этот 1001 способ отлынивать от работы :))

← →
Shaman_Naydak (2002-02-23 00:24) [37]

ВОТ Блин, тут оказывается JohnnyCrisJoе уже выдвигал идею насчет зон влияния.. Ну да ладно, хоть душу отвел..

← →
JohnnyCrisJoe (2002-02-23 17:50) [38]

Ну да, и мне пол-ящика за авторские права :))

← →
Merlin (2002-02-25 20:06) [39]

Не понял:
ЗОНА ПОТЕНЦИАЛЬНОГО ВЛИЯНИЯ - расчитывает далее одной фигуры? А далее второй, третьей?
Далее, если можно закрыться от шаха пешкой, то как узнать, не открывается ли шах с другой стороны, если сдвинуть эту пешку? То что на поле короля есть зона влияния какой-то фигуры+потенциальная зона влияния нам ни о чем не говорит, можем ли мы закрыться конкретно этой пешкой или нет, без расчета на шах новой позици...

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

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