
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.97.9.175] |
![]() |
|
Сообщ.
#1
,
|
|
|
Алгоритм для игры "НИМ" (иногда камни или спички). Дано n спичек, максимум можно брать по m спичек. Игроков 2-е. Проигрывает тот, кто берет последнюю спичку. Подскажите, пожалуйста, алгоритм выйгрыша. Мне это надо по предмету "Системы искусственного интеллекта". Буду благодарен за любую информацию.
|
Сообщ.
#2
,
|
|
|
Форсайт "Программирование на языке Паскаль"
Выйду с больничного, могу выслать текст программы. |
Сообщ.
#3
,
|
|
|
Цитата ozzy, 25.02.03, 12:03:10 Форсайт "Программирование на языке Паскаль" Выйду с больничного, могу выслать текст программы. какой текст вся программа две строчки алгоритм простой за каждые два хода твой и его ты всегда можешь гарантировать в сумме м+1 камень что и ведет к выигрышу только это ни какой не ИИ, поэтому не понятно что вы хотите |
Сообщ.
#4
,
|
|
|
Могу ошибаться, но это игра - модифицированная игра Баше.
А вот игра НИМ сложнее. Там есть несколько кучек, брать за ход можно только из одной. К этой игре уже можно ИИ приделать (хотя зачем?). Есть хороший исходник для TP7: http://albom.nm.ru/nim.pas. |
Сообщ.
#5
,
|
|
|
По-моему пример этой игры был в книге Фаронова по Турбо Паскалю.....
|
Сообщ.
#6
,
|
|
|
Возможно, но я такой книги не читал.
|
Сообщ.
#7
,
|
|
|
исправлено 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 |
Сообщ.
#8
,
|
|
|
Большое спасибо всем кто ответил. Вы мне очень помогли.
З.Ы. Я студент-заочник. Я не говорил, что мне нужет ИИ. Просто предмет называется СИИ. Но большей частью будем изучать экспертные системы. Еще раз спасибо. З.З.Ы. Я не знаю, что что за игра "НИМ". Может она на кваку похожа, но так в задании написано. Тут я полностью полагался на препода, который давал задание. |
Сообщ.
#9
,
|
|
|
Есть хорошее описание этой игры на сайте 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 так что свои коды вы можете постить туда, а система автоматически проверит, насколько они рабочие. |
Сообщ.
#10
,
|
|
|
Цитата 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 |
Сообщ.
#11
,
|
|
|
Цитата ujif @ программа вылетает на строке while nbit[i]=0 do inc(i); Выход за пределы диапазона. Нужно так: ![]() ![]() while (i <= High(nbit)) and (nbit[i]=0) do inc(i); Цитата ujif @ почему у ncbit двойной индекс ,массив вроде не двумерный Двумерный: ![]() ![]() ncbit : array [1..MAXROW] of BitType; {= array[1..MAXROW] of array [1..BIT] of integer = array[1..MAXROW,1..BIT] of integer;} |
Сообщ.
#12
,
|
|
|
Цитата leo @ Спасибо Уважаемый Leo за поддержку |