Алгоритм для игры "НИМ".

Алгоритм для игры "НИМ" (иногда камни или спички). Дано n спичек, максимум можно брать по m спичек. Игроков 2-е. Проигрывает тот, кто берет последнюю спичку. Подскажите, пожалуйста, алгоритм выйгрыша. Мне это надо по предмету "Системы искусственного интеллекта". Буду благодарен за любую информацию.

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

Цитата ozzy, 25.02.03, 12:03:10

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

какой текст

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


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

только это ни какой не ИИ, поэтому не понятно что вы хотите

Могу ошибаться, но это игра - модифицированная игра Баше.
А вот игра НИМ сложнее.
Там есть несколько кучек, брать за ход можно только из одной.
К этой игре уже можно ИИ приделать (хотя зачем?).


Есть хороший исходник для 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 - 04.03.03, 14:44

Большое спасибо всем кто ответил. Вы мне очень помогли.
З.Ы.
Я студент-заочник. Я не говорил, что мне нужет ИИ. Просто предмет называется СИИ. Но большей частью будем изучать экспертные системы. Еще раз спасибо.
З.З.Ы.
Я не знаю, что что за игра "НИМ". Может она на кваку похожа, но так в задании написано. Тут я полностью полагался на препода, который давал задание.

Есть хорошее описание этой игры на сайте 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 @ 25.02.03, 20:50

в процедуре 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 @ 02.10.14, 18:47

программа вылетает на строке
while nbit[i]=0 do inc(i);

Выход за пределы диапазона. Нужно так:

while (i <= High(nbit)) and (nbit[i]=0) do inc(i);

Цитата ujif @ 02.10.14, 18:47

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

Двумерный:

ncbit : array [1..MAXROW] of BitType; {= array[1..MAXROW] of array [1..BIT] of integer = array[1..MAXROW,1..BIT] of integer;}

Цитата leo @ 03.10.14, 04:47

Спасибо Уважаемый Leo за поддержку