На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> Алгоритм для игры "НИМ".
    Алгоритм для игры "НИМ" (иногда камни или спички). Дано n спичек, максимум можно брать по m спичек. Игроков 2-е. Проигрывает тот, кто берет последнюю спичку. Подскажите, пожалуйста, алгоритм выйгрыша. Мне это надо по предмету "Системы искусственного интеллекта". Буду благодарен за любую информацию.
      Форсайт "Программирование на языке Паскаль"
      Выйду с больничного, могу выслать текст программы.
        Цитата ozzy, 25.02.03, 12:03:10
        Форсайт "Программирование на языке Паскаль"
        Выйду с больничного, могу выслать текст программы.


        какой текст

        вся программа две строчки


        алгоритм простой за каждые два хода твой и его ты всегда можешь гарантировать в сумме м+1 камень что и ведет к выигрышу

        только это ни какой не ИИ, поэтому не понятно что вы хотите
        Microsoft SDE -> Intel algorithmist -> Skype SDET 2
        B.Sc - > M.Sc -> B.Psy -> Scrum Master -> Research Assistent

        https://www.youtube.com/user/igorkle1?feature=mhee
        http://igor-eta.livejournal.com/
        http://www.idea2site.com/
          Могу ошибаться, но это игра - модифицированная игра Баше.
          А вот игра НИМ сложнее.
          Там есть несколько кучек, брать за ход можно только из одной.
          К этой игре уже можно ИИ приделать (хотя зачем?).


          Есть хороший исходник для TP7: http://albom.nm.ru/nim.pas.
          Убилбытого,ктосломалмойпробел!
            По-моему пример этой игры был в книге Фаронова по Турбо Паскалю.....
              Возможно, но я такой книги не читал.
              Убилбытого,ктосломалмойпробел!
                исправлено by GrAnd
                {Логическая игра  ним. Описание игры и программы см. п.2.7.3 книги 1}
                Uses CRT;               {подключение библиотеки дополнительных
                                        процедур и функций для управления экраном}
                const
                 MAXROW = 14;          {максимальное количество рядов}
                 MAXCOL = 20;          {максимальное количество фишек в ряду}
                type
                 ColType   = array [1..MAXROW] of integer;
                var
                 exit   : Boolean;     {признак окончания работы}
                 change : Boolean;     {признак изменения условий игры}
                 nrow   : integer;     {количество рядов}
                 ncol   : ColType;     {м ксимальное количество фишек по рядам}
                 col    : ColType;     {текущее количество фишек по рядам}
                {------------------------------------------------------------}
                Procedure ShowField;
                { Отобр ж ет н  экр не текущее состояние игрового поля }
                const
                 FISH = #220;      { символ-указатель фишки }
                 X0   = 4;         { левая колонка  номеров рядов }
                 X1   = 72;        { прав я колонка  количеств  фишек }
                 X    = 20;        { левый край игрового поля }
                var
                 i,j : integer;
                begin {ShowField}
                 for i := 1 to nrow do
                   begin
                     GotoXY(X0,i+4);
                     write(i);                { номер ряда }
                     GotoXY(X1,i+4);
                     write(col[i]:2);         { количество фишек в ряду }
                     for j := 1 to ncol[i] do { вывод ряда фишек:}
                       begin
                         GotoXY(X+2*j,i+4);
                         if j<=col[i] then write(FISH) else write('.')
                       end
                   end
                end;  {ShowField}
                {------------------------------------------------------------}
                Procedure Prepare;
                { Подготовка  данных и формирование экрана }
                const
                 Header0 = 'И Г Р А   Н И М';
                 Header1 = 'Вы можете взять любое число фишек из любого ряд .';
                 Header2 = 'Выигрывает тот, кто возьмет последнюю фишку.';
                 Header3 = 'Номер ряд ';
                 Header4 = 'Кол-во фишек';
                var
                 i : integer;
                begin {Prepare}
                 clrscr;               { очистить экран }
                 { Вывести з головок: }
                 GotoXY((80-Length(Header0)) div 2,1);
                 write(Header0);
                 GotoXY((80-Length(Header1)) div 2,2);
                 write(Header1);
                 GotoXY((80-Length(Header2)) div 2,3);
                 writeln(Header2);
                 write(Header3);
                 GotoXY(80-Length(Header4),4);
                 write(Header4);
                 { Подготовить начальную раскладку: }
                 for i := 1 to nrow do col[i] := ncol[i]
                end;  {Prepare}
                {------------------------------------------------------------}
                Procedure GetPlayerMove;
                { Получить, проконтролировать и отобразить ход игрок  }
                const
                 TEXT1 = 'Введите В ш ход в форм те РЯД КОЛИЧ (н пример, 2 3 - взять из 2 ряд  3 фишки)';
                 TEXT2 = 'или введите 0 0 для выход  из игры; -1 0 для н стройки игры';
                 TEXT3 = 'В ш ход:                 ';
                 Y     = 20;            {номер строки для вывод  сообщений}
                var
                 correctly : Boolean;   {признак правильности сделанного ход }
                 x1,x2     : integer;   {вводимый ход}
                {-------------------------------------}
                Procedure GetChange;
                { Ввести новую настройку игры (количество рядов и
                 количество фишек в каждом ряду }
                const
                 t1 = 'Н А С Т Р О Й К А    И Г Р Ы';
                 t2 = '(ввод количеств  рядов и количеств  фишек в каждом ряду)';
                var
                 correctly : Boolean;
                 i         : integer;
                begin {GetChange}
                 clrscr;
                 GotoXY((80-Length(t1)) div 2,1);
                 write(t1);
                 GotoXY((80-Length(t2)) div 2,2);
                 write(t2);
                 repeat
                   GotoXY(1,3);
                   write('Введите количество рядов (максимум ',MAXROW,'):      ');
                   GotoXY(WhereX-6,WhereY);
                   readln(nrow);
                   correctly := (nrow<=MAXROW) and (nrow>1);
                   if not correctly then
                     write(#7)
                 until correctly;
                 for i := 1 to nrow do
                   repeat
                     GotoXY(1,i+3);
                     write(' ряд ',i,', количество фишек (максимум ',MAXCOL,'):       ');
                     GotoXY(WhereX-6,WhereY);
                     readln(ncol[i]);
                     correctly := (ncol[i]<=MAXCOL) and (ncol[i]>0);
                     if not correctly then
                       write(#7)
                   until correctly
                end;  {GetChange}
                {-------------------------------------}
                begin {GetPlayerMove}
                 ShowField;            { показать начальное состояние поля }
                 { Сообщить игроку пр вил  ввод  ход : }
                 GotoXY((80-Length(TEXT1)) div 2,Y);
                 write(TEXT1);
                 GotoXY((80-Length(TEXT2)) div 2,Y+1);
                 write(TEXT2);
                 repeat
                   { Пригл сить игрок  ввести ход: }
                   GotoXY(1,Y+2);
                   write(TEXT3);        {вывести приглашение и стереть предыдущий ход}
                   GotoXY(WhereX-16,Y+2); {курсор влево н  16 позиций}
                   readln(x1,x2);       {ввести очередной ход}
                   exit   := x1=0;      {контроль команды выход }
                   change := x1=-1;     {контроль команды изменения}
                   if not (exit or change) then
                     begin
                       correctly := (x1>0) and (x1<=nrow) and
                                    (x2<=col[x1]) and (x2>0);
                       if correctly then
                         begin          {ход пр вильный:}
                           col[x1] := col[x1]-x2; {изменить раскладку фишек}
                           ShowField              {показать поле}
                         end
                       else
                         write(#7)      {ход неправильный: дать звуковой сигнал }
                     end
                   else
                     correctly := true  {случай EXIT или CHANGE}
                 until correctly;
                 if change then
                   GetChange
                end;  {GetPlayerMove}
                {------------------------------------------------------------}
                Procedure SetOwnerMove;
                { Найти и отобразить очередной ход программы }
                {-------------------------------------}
                FUNCTION CheckField : integer;
                { Проверка  состояния игры. Возвращает 0, если нет ни одной
                 фишки (побед  игрок ), 1 - есть один ряд (побед  м шины)
                 и количество непустых рядов в остальных случаях }
                var
                 i,j : integer;
                begin {CheckField}  
                 j := 0;
                 for i := 1 to nrow do if col[i]>0 then inc(j);
                 CheckField := j
                end;  {CheckField}
                {-------------------------------------}
                Procedure CheckPlay;
                { Контроль оконч ния игры }
                var
                 i : integer;
                begin {CheckPlay}
                 GotoXY(1,25);
                 write('Введите 1, если хотите сыграть еще раз, 0 - выход: ');
                 readln(i);
                 if i=1 then change := true else exit := true
                end;  {CheckPlay}
                {-------------------------------------}
                Procedure PlayerVictory;
                { Поздравить игрок  с победой и усложнить игру }
                const
                 t1 = 'ПОЗДРАВЛЯЮ С ОТЛИЧНОЙ ПОБЕДОЙ!';
                var i : integer;
                begin
                 GotoXY((80-Length(t1)) div 2,24);
                 writeln(t1,#7);
                 for i := 1 to nrow do
                   if ncol[i]<MAXROW then inc(ncol[i]);
                 CheckPlay
                end;  {PlayerVictory}
                {-------------------------------------}
                Procedure OwnVictory;
                { Побед  м шины }
                const
                 t1 = 'ВЫ ПРОИГРАЛИ: СЛЕДУЮЩИМ ХОДОМ Я БЕРУ ВЕСЬ РЯД ';
                var
                 i : integer;
                begin {OwnVictory}
                 i := 1;
                 while col[i]=0 do inc(i);
                 GotoXY((80-Length(t1)) div 2,24);
                 write(t1,i,#7);
                 delay(2000);     {задержка на 2 секунды}
                 col[i] := 0;
                 ShowField;
                 CheckPlay
                end;  {OwnVictory}
                {-------------------------------------}
                Procedure ChooseMove;
                { Выбор очередного ход  }
                const
                 BIT = 6;         {количество двоичных разрядов}
                type
                 BitType = array [1..BIT] of integer;
                var
                 ncbit : array [1..MAXROW] of BitType;
                 i,j,k : integer;
                 nbit  : BitType;
                {-------------------------------------}
                Procedure BitForm(n : integer; var b : BitType);
                { Формирует двоичное представление b целого числа  n }
                var
                 i : integer;
                begin {BitForm}
                 for i := BIT downto 1 do
                   begin
                     if odd(n) then b[i] := 1 else b[i] := 0;
                     n := n shr 1
                   end
                end;  {BitForm}
                {-------------------------------------}
                begin {ChooseMove}
                 {Найти двоичное представление количеств  фишек во всех ряд х:}
                 for i := 1 to nrow do BitForm(col[i],ncbit[i]);
                 {Найти сумму разрядов по модулю 2:}
                 for i := 1 to BIT do
                   begin
                     nbit[i] := 0;
                     for j := 1 to nrow do nbit[i] := nbit[i] xor ncbit[j,i]
                   end;
                 {Н йти i = старший ненулевой разряд суммы}
                 i := 1;
                 while nbit[i]=0 do inc(i);
                 if i>BIT then
                   {Оп сный в ри нт}
                   begin
                     j := 1;
                     while col[j]=0 do inc(j);   {найти ненулевой ряд}
                     k := 1                      {взять из него 1 фишку}
                   end
                 else
                   {Безоп сный в ри нт}
                   begin
                     j := 1;
                     while ncbit[j,i]=0 do inc(j); {найти нужный ряд}
                     for i := i to BIT do
                       if nbit[i]=1 then
                         ncbit[j,i] := ord(ncbit[j,i]=0); {инверсия разрядов}
                     k := 0;
                     for i := 1 to BIT do
                       begin
                         if ncbit[j,i]=1 then inc(k);
                         if i<BIT then k := k shl 1
                       end;
                     k := col[j] - k
                   end;
                   GotoXY(1,23);
                   write('Мой ход:         ');
                   GotoXY(WhereX-8,WhereY);
                   delay(1000);
                   write(j,' ',k);
                   col[j] := col[j]-k
                end;  {ChooseMove}
                {-------------------------------------}
                begin {SetOwnerMove}
                 case CheckField of      {проверить количество непустых рядов}
                   0 : PlayerVictory;    {все ряды пусты - побед  игрок }
                   1 : OwnVictory;       {один непустой ряд - побед  м шины}
                   else
                     ChooseMove;         {выбрать очередной ход}
                 end; {case}
                end;  {SetOwnerMove}
                {------------------------------------------------------------}
                begin {Гл вн я прогр мм }
                 nrow := 3;            { Подготовить игру }
                 ncol[1] := 3;         { н  поле из трех  }
                 ncol[2] := 4;         { рядов фишек      }
                 ncol[3] := 5;
                 repeat                { Цикл изменения условий игры }
                   Prepare;            { Подготовить экран }
                   repeat              { Игровой цикл }
                     GetPlayerMove;    { Получить ход пользователя }
                     if not (exit or change) then
                       SetOwnerMove    { Определить собственный ход }
                   until exit or change
                 until exit
                end.
                Вот полный текст программы, о который вы говорили.... Также можно скачать здесь : http://c-l-a-n-e.narod.ru/NIM.PAS
                Сообщение отредактировано: GrAnd -
                  Большое спасибо всем кто ответил. Вы мне очень помогли.
                  З.Ы.
                  Я студент-заочник. Я не говорил, что мне нужет ИИ. Просто предмет называется СИИ. Но большей частью будем изучать экспертные системы. Еще раз спасибо.
                  З.З.Ы.
                  Я не знаю, что что за игра "НИМ". Может она на кваку похожа, но так в задании написано. Тут я полностью полагался на препода, который давал задание.
                    Есть хорошее описание этой игры на сайте http://potential.org.ru


                    Игра Ним или как математики играют в игры
                    http://potential.org.ru/bin/view/Info/ArtDt200502101334PH3C2J2



                    Там описан общий принцип определения стратегии для конечных нейтральных игр.

                    И описан алгоритм вычисления Нимберсов для таких игр.

                    А на сайте http://acm.mipt.ru/judge есть несколько задач про игры

                    1 Ним http://acm.mipt.ru/judge/bin/problems.pl?problem=100&sort=ID&lang=ru
                    2 Камешки http://acm.mipt.ru/judge/bin/problems.pl?problem=101&sort=ID&lang=ru
                    2 Ним в поддавки (кстати, очень интересная штука) http://acm.mipt.ru/judge/bin/problems.pl?problem=103&sort=ID&lang=ru
                    3 Ромашки http://acm.mipt.ru/judge/bin/problems.pl?problem=104&sort=ID&lang=ru

                    так что свои коды вы можете постить туда, а система автоматически проверит, насколько они рабочие.
                      Цитата pascal.km.ru @

                      в процедуре ChooseMove
                      программа вылетает на строке
                      while nbit[i]=0 do inc(i);
                      с кодом 201 если вводишь
                      в самом начале игры следующие данные
                      ряд - 1 ,кол-во фишек кот.нужно убрать - 2
                      поле построено 3 - 4 - 5
                      Плохо что нет объяснения что делает следующая строка
                      for j := 1 to nrow do nbit[i] := nbit[i] xor ncbit[j,i]
                      почему у ncbit двойной индекс ,массив вроде не двумерный
                      вообще бы хотелось более подробного объяснения процедуры
                      ChooseMove
                      Подпись выключена.
                        Цитата ujif @
                        программа вылетает на строке
                        while nbit[i]=0 do inc(i);

                        Выход за пределы диапазона. Нужно так:
                        ExpandedWrap disabled
                          while (i <= High(nbit)) and (nbit[i]=0) do inc(i);


                        Цитата ujif @
                        почему у ncbit двойной индекс ,массив вроде не двумерный

                        Двумерный:
                        ExpandedWrap disabled
                          ncbit : array [1..MAXROW] of BitType; {= array[1..MAXROW] of array [1..BIT] of integer = array[1..MAXROW,1..BIT] of integer;}
                          Цитата leo @

                          Спасибо Уважаемый Leo за поддержку
                          Подпись выключена.
                          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                          0 пользователей:


                          Рейтинг@Mail.ru
                          [ Script Execution time: 0,1479 ]   [ 16 queries used ]   [ Generated: 22.08.19, 12:03 GMT ]