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

[Олеся Ю]

вот если К>=N/2+1 то будет выигрывать по любому первый игрок, это и так понятно. А вот если, правда я могу ошибаться, К>N/2, выигрывает первый игрок, а если К=N/2 и если брать клетки ВСЕ N не пропуская не одной, то выиграет 2й игрок, а если брать не подряд, т.е. пропуская то выиграет 1й игрок... Но я не уверенна, не все варианты перебирала, просто сижу играю, и как то так получается...Может и не права я...=(

[Poma][a]

Если комп ходит 2, то давайте повторять ходы 1, НО при попадании в середину запускать алгоритм который ищет и просчитывает все возможные ходы выбирая лучший (ну например n = 9 k = 2

| | | | |1/1 |1/1 | | | |

логически рассуждая понимаем что лучше сделать так :

|2/1 |2/1 | | |1/1 |1/1 | | | |

иначе соперник сделает так :

|    |     |     |    | 1/1 | 1/1 |    | 2/1 | 2/1 | 
|    | 1/2 | 1/2 |    | 1/1 | 1/1 |    | 2/1 | 2/1 |

и мы проиграли....

[Олеся Ю]

не очень понятно...

[Poma][a]

|   |   |   |   |   |   |   |   |   |   |   |   |

вот края нашего поля размером 9
тоесть n = 9, k = 2
поехали...

|1\1|1\1|   |   |   |   |   |   |   |   |   |   |

вот 1 игрок "закрасил" 2 ячейки, мы (копм) повторим действия 1 игрока

|1\1|1\1|   |   |   |   |   |   |   |   |2\1|2\1|

ну и повторяем.... пока 1 игрок не "закрасит" середину тоесть поля 5, 6 тогда надо алгоритм поиска наилучшего хода...

[Олеся Ю]

блин, ну мне в программе все 40 клеток перебирать что-ли со всеми возможными ходами=((

[evg_m]

обобщение стратегии Poma][a

0. для простоты анализа условимся что каждый из противников идет со своего края линии. Любой другой можно свести к данному варианту путем перестановки блоков.

1. наличие попарно симметричных блоков длин (достигается симметричной игрой).
2. наличие центрального блока несимметричного длины (единственного!) (опять симметричная игра).
теперь все симметричные блоки дают преимущество второму игроку (опять симметричная игра) забудем о них.

3. несимметричный блок
k..2k-1 выигрывает игрок делающий ход(первый)
2k..3k-2 выигрывает опять же он (при правильной игре! захват центра и два блока <k)
3k-1 =k+(2k-1) и только тут гарантия выигрыша противника.
поскольку 3k опять выигрывает первый (захват центра и ДВА блока длины k)
для следующего (3k-1) +(2k-1) =k +(2k-1)+(2k-1) и т.д.
т.о. надо стремиться к длине центрального блока k+m(2k-1)
соблюдая симметричность (п.1..2) и немного отступая от нее ( блоки длин k и k+x, где x<k сами по себе равносильны но по разному влияют на длину центрального!)

[Олеся Ю]

вот я нашла кое-что не совсем конечно моё задание, здесь проще, то что зачеркивают подряд и К = либо1,2 или3....

но чем то похоже.В делфи.

[TinMan]

Извиняюсь - ответ писал понемногу в течение двух дней..

Rin, привет )
Да, именно что игра кажется похожей на известные. Это и меня подставило ). Но похоже, что игра оригинальная. Респект ее автору! Мне нравится, что ее граф сильно ветвится.

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

так во всех подобных задачах успех на произвольной стадии НЕ ГАРАНТИРОВАН.
вот если вышел на выигрышную позицию, то тогда нужно придерживаться выигрышной стратегии.

Серж, негарантированность выигрышной позиции носит не совсем принципиальный характер, мне кажется. IMHO легко доказать, что в любой детерминированной игре с полной информацией у одного из игроков (пеового или второго) ВСЕГДА ЕСТЬ либо выигрышная, либо ничейная (на худой конец) стратегия. Но только толку от подобного утверждения не так уж много..

Например, возьмем шашки (а можно и шахматы, разницы нет). Согласно высказыванию выше, один игрок (скорее всего, первый) имеет выигрышную стратегию в самом начале игры. Но только найти ее невозможно (на данном уровне развития выч. техники). В эндшпиле ее можно указать. Но это не значит, что мы вышли на выигрышную позицию. Это значит, что мы вышли на позицию, с которой мы МОЖЕМ ПРОСЧИТАТЬ выигрыш.

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

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

Сообщение от Олеся Ю

не знаю, я вот что то пока совсем не понимаю как можно сделать чтобы выигрывал компьютер, ... И как это все реализовать я пока тоже не понимаю, что-то как-то все запутано и сложно.=(

Сообщение от Олеся Ю

просто сижу играю,

Это мне нравится ). Так и надо.

Сообщение от Олеся Ю

вот я нашла кое-что

А вот это - не очень.. Не искать надо, а думать. Гугл в этом не поможет.

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

const
  mn= 40;
  n: word= 25;  // board length
  l: word= 3;   // move size
  f= 3;

type
  tBoard= array[1..mn] of boolean;


procedure Show(b: tBoard);
var
  i: word;
begin
  for i:=1 to n do write(i:f);
  writeln;
  for i:=1 to n do if b[i] then write('x':f) else write('.':f);
  writeln
end;


function Move(b: tBoard; p: integer; i: word): LongInt;
var
  w: LongInt;
begin
  if not (b[i] or b[i+l-1]) then begin
    for i:=i to i+l-1 do b[i]:= true;
    w:= p;
    for i:=1 to n-l+1 do w:= w+Move(b,-p,i)
  end
  else w:=0;
  Move:= w
end;


var
  b: tBoard;
  i,xi: word;
  r,xr: LongInt;
  t: boolean;

begin
  writeln('game of bricks, (C) TinMan, 2012, programmersforum.ru');
  writeln('==========  well, let''s play!  ==========');
  for i:=1 to n do b[i]:= false;
  repeat
    Show(b);
    xr:= Low(LongInt);
    xi:= 0;
    for i:=1 to n-l+1 do begin
      r:= Move(b,1,i);
      // write(r:f);
      if not (b[i] or b[i+l-1]) and (r>xr) then begin
        xr:= r;
        xi:= i
      end
    end;
    // writeln;
    if xi=0 then writeln('you win')
    else begin
      for i:=xi to xi+l-1 do b[i]:= true;
      writeln('my move was ',xi);
      Show(b);
      t:= true;
      for i:=1 to n-l+1 do t:= t and (b[i] or b[i+l-1]);
      if t then writeln('you lose')
      else begin
        repeat
          write('what''s yours? ');
          readln(i)
        until (i>0) and (i<=n-l+1) and not (b[i] or b[i+l-1]);
        for i:=i to i+l-1 do b[i]:= true;
        //Show(b)
      end
    end
  until (xi=0) or t;
  readln
end.

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

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

[Serge_Bliznykov]

думаю, что надо рандомайзить ходы компьютера (при равных оценочных значениях), иначе скучновато играть.

но так - весьма и весьма неплохо!! (хотя стратегия не является идеальной, к сожалению: для вашего примера доски ходы 5, 11, 20, 23 приводят к победе человека)

[Олеся Ю]

у меня ссылается на ошибку:
xr:= Low(LongInt);