Программирование игр и головоломок

[Олеся Ю]

[FONT="Arial Black"][FONT="Times New Roman"]Разработать программную модель следующей логической игры двух игроков (пользователь-компьютер), реализовав выигрышную стратегию для компьютера: Вводится целое число K>=1. Бумажная полоса разбита на N клеток (K <= N <= 40).Играют двое, по очереди выбирая и зачеркивая K пустых смежных клетки. Выигрывает сделавший последний ход. Ходы первого вводятся с клавиатуры и задаются индекcoм ячейки L (1<=L<=N-K+1).При этом вычеркиваются клетки с индексами от L до L+K-1.После каждого хода выводится текущая позиция в виде
__________________
1 2 3 ... n
__________________
__________________
* *

[TinMan]

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

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

[Олеся Ю]

нет, просто берется вводится К, которое больше 1. И что игрок что компьютер каждый раз зачеркивает не больше не меньше а именно К клеток.
И выигрывает тот кто зачеркнул последние клетки К. если осталось по 1й в разных местах, а К=2 то их не считают, выиграл тот кто зачеркнул 2 последние. Если играть на листочке то выигрывает то игрок, то комп, в зависимости от кол-ва N клеток на полосе. Не знаю что за стратегия что должен выигрывать компьютер.=((

[Serge_Bliznykov]

TinMan, не, это не Ним, это совсем другая игра..
K задаётся в начале игры (кем - сейчас не столь важно).
заполняются свободные смежные (подряд) K ячеек, но в ЛЮБОМ месте ленты..
имхо, выигрышная стратегия должна быть, если свободных ячеек подряд меньше или равно 2*K - то располагать свои по центру.
а если их больше - то располагать свои так, чтобы свободных смежных оставался кусок строго больше 3*K ...

это я сейчас из головы пишу, возможно, что и ошибаюсь..


Олеся Ю, а каков порядок игры?
Ну кто задаёт K, N и кто ходит первым - человек или компьютер?

[Олеся Ю]

первым ходит ИГРОК. N и К задается просто при запуске в паскале например: введите N и введите К это не оговорено, я так думаю, задание я написала в точь как оно есть. Моете мне помочь, накидать эту программу?))

[Serge_Bliznykov]

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

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

вот тут:
http://www.prosv.ru/ebooks/inf34/INF...NF4metod06.htm

http://www.prosv.ru/ebooks/inf34/INF...NF4metod07.htm

Если же Вы готовы сформулировать правила этой самой выигрышной стратегии, то написать код уже будет просто!

[TinMan]

Сообщение от Serge_Bliznykov

TinMan, не, это не Ним, это совсем другая игра..
K задаётся в начале игры (кем - сейчас не столь важно).
заполняются свободные смежные (подряд) K ячеек, но в ЛЮБОМ месте ленты..

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

Должен признать, игра довольно интересная получается, особеннно если тщательно подобрать длины поля и хода. Я уже второй день думаю над решением (Олеся, спасибо)). Простой стратегии (как в спичках) тут явно нет. Поэтому я попытался переключиться на самообучающуюся схему. С первого взгляда казалось, она тут легко и органично встанет в пазы - ан, нет! Виной всему большое количество возможных ходов в каждый момент (то есть большое ветвление графа игры) в общем случае - пришлось от этой идеи отказаться.. Тогда я посмотрел в сторону традиционных методов с просмотром на несколько ходов вперед и вычислениеи оценочной функции стоимости хода. Но с последней вышел затык. Беда еще и в том, что я ни разу в нее не играл и поэтому не чувствую.. ((

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

Моете мне помочь, накидать эту программу?))

Думаю, да. Но, Олеся, пожалуйста, поучаствуй в обсуждении. Ты думала хоть немного над этой задачей? Выскажи свои соображения, какими бы сырыми и/или несерьезными они ни казались. Поверь, это сильно поможет делу..

[Олеся Ю]

Спасибо большое за ответ. Я тоже предпочитаю на ты.=)
Я вот пока сижу рисую, пытаюсь разработать стратегию, но почему то у меня либо игрок выигрывает, либо комп, это в зависимости от кол-ва клеток. А мне считай надо чтоб комп выигрывал. Вот я пока не могу понять от чего это зависит((

[Олеся Ю]

Еще моя задача аналогична вот этой. Но я не совсем это вижу.


Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a1, либо a2, либо ... aS бананов (а1 <a2 <...<aS), а 2-ая при каждом очередном
ходе --либо b1, либо b2, либо ... bK бананов (b1 <b2 <...<bK ). Нумерация индексов при a и b не имеет никакого отношения к номерам ходов обезьян Выигрывает та обезьяна, которая на своем ходе не может взять банан(ы) (либо потому, что их не осталось, либо потому что бананов осталось меньше чем a1 (при ходе первой обезьяны) либо b1 (при ходе второй обезьяны)).
Определить может ли выиграть первая обезьяна при наилучших ходах соперницы, которая также стремится выиграть. Все входные данные - натуральные числа.

Решение задачи 4.1.
Будем обозначать текущую ситуацию в игре парой (S,i), где S количество бананов, оставшихся в куче, перед текущим ходом i-ой обезьяны (i равно 1 или 2).
Для того, чтобы (S,1) была выигрышной для игрока 1, среди возможных ситуаций после его хода (S-a1,2), ... ,(S-ak,2) должна быть хоть одна проигрышная для игрока 2 (в эту то ситуацию и надо будет перевести игру); если все ситуации выигрышные для игрока 2, то (S,1) - проигрышная для игрока 1 (как бы он не поступал, он все равно проиграет).
Пусть ситуация после хода игрока 1 стала (S',2). Опять же делаем все допустимые ходы из этой позиции и смотрим является ли получившаяся ситуация (S",1) выигрышной, проигрышной или такой, которую мы еще не можем оценить. Если выполняется последняя альтернатива, то из (S",1) мы опять делаем все возможные ходы, анализируем, и т.д.
Если мы в конце концов определили, для кого является выигрышной текущая позиция, то возвращаемся к предыдущему ходу и пытаемся определить, какая позиция для делающего ход и т. д., пока не вернемся к ситуации (L,1).

const l1=200;
s=10;
var a: array [0..l1,1..2] of byte; {в ячейке a[L,i] 
хранится информация, кто выигрывает в ситуации (L,i)}
b: array [1..2,0..s] of byte; {массив возможных ходов 
первого и второго игроков в b[i,0] хранится число 
возможных ходов игрока i}
l,i,j:integer;
Function f(ba:Integer;No: Byte): Byte;
Var i,p,r: Byte; {рекурсивная функция вычисления (L,i)}
Begin {f=i, если в (ba,i) выигрывает i}
if Ba<0 {после хода монет <0?}
Then f:= 3-No {выигрыш игрока с номером 3-Nо}
else if ba=0 {монет = 0?}
then begin {выигрыш No}
f:=No;
a[ba,no]:=no;
end
Else if a[ba,no]<>0 {в этой ситуации мы уже были}
Then F := a[ba,no] {в ней выигрывает a[ba,no]}
Else
Begin {эту ситуацию мы еще не рассматривали}
r := 0;
{мы будем делать все возможные ходы}
For i := 1 to b[No,0] do
if ba-b[no,i]>=0 {если ход возможен, то делаем его}
then r := r or F(Ba-B[No,i],3-No);
if r=0 then r:=no;
If (No and R)<>0 {есть выигрышный ход?}
Then p := No {да, (ba,i)=No}
Else p := 3-No; {нет, (ba,i)=3-No}
A[Ba,No]:=p; {запоминаем эту информацию}
f:=p;
End;
end;
begin
for i:=0 to l1 do
for j:=1 to 2 do A[i,j] := 0;
write('s=');
readln(b[1,0]); {b[1,0] = количество ходов первого игрока}
for i:=1 to b[1,0] do
begin
write('a',i,'='); {сами ходы}
Readln(b[1,i]);
end;
write('k=');
Readln(b[2,0]); {b[2,0] = количество ходов второго игрока}
For j := 1 to b[2,0] do
begin
write('b',j,'=');
Readln(b[2,j]); {ввод ходов}
end;
repeat {для данных ходов вводятся значения L}
write('L='); {число бананов}
readln(l);
if f(l,1)=1 {вызов рекурсивной функции-проверки}
then writeln('1-я выиграла')
else writeln('1-я проиграла');
for i:=1 to b[1,0] do {распечатка результатов возможных ходов} 
if (l-b[1,i])>=0 {из начальной позиции L}
then writeln('b=',b[1,i],' winner=',a[l-b[1,i],2]);
writeln;
until false;
end.

________
Код нужно оформлять по правилам:
тегом [CODE]..[/СODE] (это кнопочка с решёточкой #)
Не забывайте об этом!
Модератор.

[Poma][a]

Олесь, пожалуйста оформляй код правильно, а то читать не возможно.... (кнопочка #)

и получается что последний цикл будет крутиться "вечно" ?
(прошу прощения, если я ошибся, пишу с чужого ноута => паскаль не установить....)