Объявить МАТ

← →
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]

← →
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]

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