Про шахматы

← →
infom © (2004-05-08 11:27) [0]

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

← →
Думкин © (2004-05-08 11:32) [1]

Значит не хочет он тебе автомат ставить. Видимо прав.
Слышал что порядка 10^111. :-))

← →
infom © (2004-05-08 11:35) [2]

А посчитать точно возможно ли?если да то как

← →
Algol (2004-05-08 11:37) [3]

В такой формулировке их бесконечное число ...

А кроме того я что-то не понял, что должна делать программа ?? Подсчитывать точное число возможных партий?

← →
OlegGashev © (2004-05-08 11:41) [4]

infom © (08.05.04 11:35) [2]
Можно, перебор всех вариантов. :-)))

← →
Algol (2004-05-08 11:41) [5]

Оценить (т.е. подсчитать приблизительно) можно так:
Среднее число возможных ходов на каждом полуходе составляет 20.
Значит на каждом полном ходе возможно 20*20 комбинаций. Если взять среднюю продолжителности партии - 30 ходов, то получаем число партий: 40^30
Эта оцнка числа разумных партий. Если же считать число партий вообще, то их бесконечно много, поскольку противники могут ходить туда-сюда, бесконечно повторяя позицию...

← →
Ske4er © (2004-05-08 11:41) [6]

Мне просто интересно... так порасуждал... если бы возможно было бы это сделать, то можно было бы записасть наилучший ход для каждой ситуатиции и все... тогда почему супер-компьютеры все еще думают по 10 мин на ход играя с Каспаровыми?... или это они так дулго ищут в БД нужную позицию? :)))

← →
KilkennyCat © (2004-05-08 12:43) [7]

> Algol (08.05.04 11:41) [5]

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

← →
Anatoly Podgoretsky © (2004-05-08 13:21) [8]

Algol (08.05.04 11:41) [5]
Нет даже первый ход 24 варианта, второй еще более

← →
Андрей Сенченко © (2004-05-08 13:30) [9]

А у меня в запасе ход конём !
:)

← →
nikkie © (2004-05-08 13:35) [10]

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

← →
Salaga (2004-05-08 16:27) [11]

Е. Гик "Математика на шахматной доске" - маленькая такая книжка, там есть немного из того, что ты ищешь

← →
Algol (2004-05-08 17:36) [12]

> KilkennyCat © (08.05.04 12:43) [7]

Ааа... сорри не знал таких правил )) Шахматы - не моя стихия, никогда не понимал этой игры, если честно...

> infom

Если вашего препода действительно не интересовал результат, а только алгоритм (любитель восточной философии наверно), тогда задача довольно просто решается.
1)Строим дерево вариантов хода на каждом ходу, запоминаем соотв позиции.
2)Обходим новые вершины.Если эта позиция уже встречалась два раза, обрываем ветку. Если вышел пат или мат - обрываем ветку. Если прошло 50 ходов и ничего не съедено - обрываем ветку.
3)Если ветка не оборвалась, идем к пункту первому для данной вершины.
4)Если открытых веток не осталось, считаем число листьев в дереве (впрочем, до этого дело не дойдет:)

В силу п2 последовательность действий конечна, а значит является алгоритмом.

← →
nikkie © (2004-05-08 17:48) [13]

>Algol
такой алгоритм заведомо работать не будет. 2Gb памяти, доступных процессу, не хватит, чтобы построить все дерево. у меня складывается ощущение, что под деревом ты имел в виду просто список всех ходов возможных в данной позиции. но даже так для некоторого N памяти не хватит, чтобы помнить все партии из N ходов. решать надо рекурсивно. и, вероятно, надо учитывать, что в каждой нетерминальной позиции (мат, пат, 3-кратное повторение, 50 ходов) партия может продолжаться дальше, а может и окончиться любым из 3-х исходов по инициативе партнеров.

PS
1. правило 50 ходов еще включает условие, что не было хода пешкой.
2. повторение позиции требует, чтобы не только фигуры стояли также, но и чтобы очередь хода была у той же стороны.

← →
Sanek_metaller © (2004-05-08 18:19) [14]

>infom © (08.05.04 11:35) [2]
А посчитать точно возможно ли?если да то как
Играть в шахматы и считать:)

← →
Algol (2004-05-08 18:33) [15]

> nikkie © (08.05.04 17:48) [13]
> >Algol
> такой алгоритм заведомо работать не будет.

Я в этом и не сомневаюсь :)

> ты имел в виду

Я имел ввиду именно то, что написал.

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

>nikkie © (08.05.04 13:35)
>на самом деле можно выбить автомат...
>если в самом деле требуется
>>описать алгоритм и написать программу
>не сказано, что программа должна закончить работу за разумное время!

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

Ну не верю....
Не верю что подобные задачи могут даваться студентам...
Просто, так получилось что

>Не верю что подобные задачи могут даваться студентам...

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

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

Но правда был случай, когда преподы любили просто поиздеваться:
Помню когда я учился на первом курсе, у нас появилась новая (молодая, аспирантка или только-что закончившая аспирантуру) преподавательница (вела у нас практические занятия по вышке). И хотя я в группе в математике "шарил" лучше всех, видно я чем-то ей не понравился, так как она начала меня доставать. Например заканчивается занятие, и она говорит типа мол все свободны, а вот товарищ [моя фамилия] нам к следующему занятию решит вот это. и пишет на доске какую-нить фигню...
Пару таких задачек я решил, но так как мне за это ничего не обещали, то в очередной раз когда она решила припахать меня решить (sqrt(-1))^sqrt(-1) то я уже забил на это, и вскоре она от меня отстала со своими доставаниями...

← →
Algol (2004-05-08 21:25) [20]

> преподы любили просто поиздеваться

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

Про шахматы Найти похожие ветки