Здравствуйте! Мне очень сильно нужно помощь! Нам задали написать тгру определитель, предварительно даже не рассмотрев хотя бы одну программу по написанию игр на Паскале. Я тоже не могу найти никакую литературу по теории игр и реализации их на Паскале. Суть игры состоит в следующем: Есть матрица 3 на 3. 2 Игрока ходят поочередно и ставят цифры в любое место матрицы, при том цифры не должны повторяться. Когда вся матрица заполнена, мы считаем ее детерминант. Если Д больше 0, то выиграет первый, если меньше, то второй, если равно, то ничья. Моя проблема в том, что откуда приступить в задаче. С чего вообще начать? Понятно какими методами нужно пользовться: перебором, отсечением альфа-бета, рекурсией. Но откуда приступить к написанию кода? Как сделать так, чтобы пользователь вписал цифру в таблицу и компьютер отвечал?

Пожалуйста, обьясните мне и не закрывайте тему! Спасибо большое!!!!

Игрой это назвать конечно можно с натяжкой Но теме не менее, графики тут никакой нету на соклько я понял ))) Собственно куда ее тут пихать Пишется за 5 минут в чем конкретно проблема ? Надо ппочередно игрокам ввести матрицу, а потом посчитаь детерминант и все !

klem4, время пошло !!! Через 15 минут ты выкладываешь готовую игру, ОК?

Внимательно читаем задание !!!

Извините, но матрица же одна. Как поочередно каждому вести матрицу?Всю матрицу?Каждый должен ввести одно число после хода другого.

Ну это я образно выразился, а вообще сейчас попробую

Вот на скорую руку ...
Потестил, но могут быть ошибки.

uses crt;

const n=3;

type

   TField = array[1..n,1..n] of byte;

var

   field : TField;

procedure WriteField(x : TField);
var
   i,j : integer;
begin
   for i := 1 to n do begin
      writeln;
      for j := 1 to n do
       write(x[i,j]:2, '  ');
   end;
end;


procedure Fill(var x : TField);
var
   i,j : integer;

   count,t : byte;

   bool : boolean;

   s : set of byte;

begin

   count := 0;

   bool := TRUE;

   s := [];

   repeat

      case bool of
         TRUE : begin

            writeln;
            write('Player1 I : '); readln(i);
            write('Player1 J : '); readln(j);
            write('Player1 x[i,j] : '); readln(t);

            if (x[i,j]=0)and(not (t in s)) then begin
               x[i,j] := t;
               s := s + [t];
               inc(count);
               bool := not(bool);
            end
             else clrscr;
         end;

         FALSE : begin

             writeln;
             write('Player2 I : '); readln(i);
             write('Player2 J : '); readln(j);
             write('Player2 x[i,j] : '); readln(t);

             if (x[i,j]=0)and(not(t in s)) then begin
                 x[i,j] := t;
                 inc(count);
                 bool := not(bool);
             end
              else clrscr;
         end;
      end;

      clrscr;

      WriteField(x);

   until count =9 ;

end;

function Det(x : TField) : integer;
var
   i,j : integer;

   d : integer;

begin

   d := (x[2,2]*x[3,3]-x[3,2]*x[2,3])

                   -
        (x[2,1]*x[3,3]-x[3,1]*x[2,3])

                   +
        (x[2,1]*x[3,2]-x[3,1]*x[2,2]);

   case d>0 of
      TRUE  :  Det := 1;
      False :  Det := -1;
   else
    Det := 0;
   end;

end;


Begin

   clrscr;

   FillChar(Field, sizeof(Field), 0);

   WriteField(Field); writeln;

   Fill(Field);

   writeln;

   write('Winner : ');

   Case Det(Field) of
      1 : write('Player1');
     -1 : write('Player2');
      0 : write('Nobody');
   end;

   readln;


End.

klem4, а компьютер как играть будет? AI его ты сделал?

я подумал что 2 человека, ну можно и компа сделать

ща сделаю, нашел ошибку :




заменить на

Можно, конечно. Только учти, что задача компьютера - выиграть у игрока, а не просто так весело провести время ;)

Кстати, а почему ты после хода второго игрока не делаешь

s := s + [t];

? И зачем вообще делать

Case bool of
  True: ...
  False: ...
End;

, если производятся одни и те же действия? Только чтобы написать "Player 1" или "Player 2"???

ага, это я зря (

да уж, если он еще и думать должен, то это не на пять минут точно будет )))

Ага, и сразу

if d>0 then
   Det := 1
  else
   if d<0 then
    Det := -1
  else
   Det := 0;

заменить на

If d = 0 Then Det := 0
Else Det := (d div Abs(d));

:yes:

вот это здорово придумал

Извините, а здесь рекурсия используется? И еще альфа-бета отсечение?

Вопрос : Играть с компютером надо ? Если да, то надо писать AI

Да!

Извините, но вы не могли бы подсказать как написать ai? Как раз самое сложное именно в этом. И именно это я и не понимаю!!!!

klem4, а правильно ли твоя прога считает детерминант? Я не знаю что это, но в функции Det не используется первый столбец матрицы... <_<

Все конечно может быть ... в торопях писал, но вообще не очень понимаю о чем ты, а считал определитель по первой строке ...

Здесь вроде бы один и тот же результат будет при любом состоянии чисел
x[1,2],x[1,1],x[1,3]... А детерминант скорее всего должен считатся с помощью всех эл-в матрицы.

setare, а обязательно надо использовать "альфа - бета отсечение"? Просто в задаче такого рода это не имеет особого смысла, ведь при размере матрицы (3 х 3) имеется всего 9! вариантов взаимного расположения чисел, то есть 362880... Причем после того, как первый ход сделан, количество оставшихся вариантов сокращается уже до 8! = 40320, и т.д. => быстродействие может быть приемлемым без отсечения вариантов...

Я бы попробовал сделать так: процедура AI компьютера получает на вход частично заполненную матрицу, генерирует (рекурсивно) для нее все возможные варианты продолжения, и выбирает из них тот (само число и его расположение), при котором окончательный детерминант будет максимальным/минимальным (в зависимости от очередности хода компьютера). Если представлять матрицу как строку из 9-ти символов (развернуть матрицу построчно), то памяти в "куче" должно хватить.

P.S. klem4, на самом деле подозрительно. У меня например D считается вот так:

function get_determ(mx: tmatrix): integer;
begin
  result :=
    mx[1, 1]*mx[2, 2]*mx[3, 3] +
    mx[1, 2]*mx[2, 3]*mx[3, 1] +
    mx[1, 3]*mx[2, 1]*mx[3, 2] -

    mx[1, 3]*mx[2, 2]*mx[3, 1] -
    mx[1, 1]*mx[2, 3]*mx[3, 2] -
    mx[1, 2]*mx[2, 1]*mx[3, 3];
end;

т.е. используются все элементы...

да я забыл домножать на элементы первой строки ( забывать начинаю мат.часть

Извините, пожалуйста, volvo, но не могли бы вы еще раз но чуть по легче сказать то, что вы только что написали. Я не очень поняла как компьютер получает на вход частично заполненную матрицу?

Имелось ввиду нечто типа этого:

Type PAIResult=^TItemField
        TAIResult=record
          I,J : 1..n;
          Item: byte;
         result: byte;
       end;
...
Function AI(X:TField):PAIResult;
Var temp: PAIResult;
      i,j:integer;
      item:byte;
      g     :boolean;
      y     :TField;
begin
 y:=X;
 new(temp);
 If busy(X) then begin {Если массив заполнен, то}
  temp.result:=Det(X); 
  AI^:=temp^;            {Возвращаем D}
 end;
 For i:=1 to n do begin {Проссматриваем все возможные ходы:}
    For j:=1 to n do begin
      If X[i][i]=0 then
          For item:=0 to 255 do begin
            y[i][j]:=item;
            temp:=AI(y);
            If temp^.result=1 then AI^:=temp^;
           end;
    end;
 end;
 {Если выигрошного хода не нашлось, то}
     AI^.result:=-1; {Эта строчка была доб. позже...}
 AI^:=temp^;
end;
{
  Здесь компьютер играет либо на золото либо на проигрыш...
  Не учитывается ниченая возможность...
}
...

Ухты, ну и код. Здесь надо долго разбираться. А можно ведь и без указателей, правда? И busy(x) это функция? Кстати, отсечение обязательно. При том нужно дойти до конца и потом отсекать. С последнего уровня и идти наверх.

Ну если я правильно понимаю что ты имеешь ввиду под отсечением, то здесь оно вроде как присутствует- если встречается хороший ход, то остальные ходы не просматриваются...
Да наверно можно и без указателей, например, функция AI будет возвращать результат через глобальную переменную...
Да это функция, возвращающая true, если в массиве нет ни одного нуля иначе False. Ну, только не спрашивай как ее реализовать, а то тебя в FAQ пошлют...

код кое-как исправлен:

Type PAIResult=^TItemField
        TAIResult=record
          I,J : 1..n;
          Item: byte;
         result: byte;
       end;
...
Function AI(X:TField):PAIResult;
Var temp: PAIResult;
      i,j:integer;
      item:byte;
      g     :boolean;
      y     :TField;
begin
 y:=X;
 new(temp);
 If busy(X) then begin {Если массив заполнен, то}
  temp.result:=Det(X); 
  AI^:=temp^;            {Возвращаем D}
 end;
 For i:=1 to n do begin {Проссматриваем все возможные ходы:}
    For j:=1 to n do begin
      If X[i][i]=0 then
          For item:=0 to 255 do begin
            y[i][j]:=item;
            temp:=AI(y);
            If temp^.result=1 then AI^:=temp^;
           end;
    end;
 end;
 {Если выигрошного хода не нашлось, то}
     AI^.result:=-1;
 AI^:=temp^;
end;
{
  Здесь компьютер играет либо на золото либо на проигрыш...
  Не учитывается ниченая возможность...
}
...

Ладно не буду. Спасибо. А почему вы написали
И почему X[i][i]?

:no: Дож, это - не мой вариант. Мой вариант - что-то в таком духе:

Type
  TResult = Record
    Digit: byte; Pos: Byte;
  End;
Var
  max_D: LongInt;
  max_Matrix: String;

{
  CurrMatrix - "развернутое" в строку представление матрицы
  ToUse - оставшиеся для использования цифры
}
Procedure AI(CurrMatrix, ToUse: String);
Var
  D: LongInt;
  s_u, s_m: String;
Begin
  If ToUse = '' Then Begin { цифр больше не осталось -> матрица заполнена }
    D := get_determ(CurrMatrix); { считаем детерминант }
    If D > max_D Then Begin { если найденный D больше/меньше всех предыдущих }
      { запоминаеи макс/мин детерминант и саму матрицу, при которой это произошло }
      max_D := D; max_matrix := CurrMatrix;
    End;
    Exit; { и заканчиваем рекурсию } 
  End;

  { А вот если матрица заполнена не окончательно (ToUse не пустая строка)... }
  {
    ... то генерируем возможные сочетания элементов,
    и передаем это опять в AI:
  }
  For j := 1 To Length(ToUse) Do
    For i := 1 To Length(CurrMatrix) Do
      If CurrMatrix[i] = '0' Then Begin
        s_m := CurrMatrix; s_m[i] := ToUse[j];
        s_u := ToUse; Delete(s_u, j, 1);
        AI(s_m, s_u); { Рекурсия !!! }
      End;
End;

Procedure ComputerMove(CurrMatrix, ToUse: String; Var R: TResult);
Begin
  AI(CurrMatrix, ToUse);
  {
    Когда мы здесь - уже известно, какая матрица из возможных
    дает выигрышную комбинацию, и имея CurrMatrix и max_Matrix,
    можно выбрать одну из цифр, НЕ присутствующих в CurrMatrix...

    Результат (цифра и ее позиция в строке) возвращается через R,
    а потом при отрисовке R.Pos легко переведется в строку и столбец матрицы...
  }
End;

Извините за глупый вопрос, но что значит при отрисовке R.pos легко переведется в строку матрицы? И кстати, там , где вы написали выход их рекурсии, до этого рекурсия не использовалась, правильно? Она используется вами уже после, когда touse не равно " "?

После того, как компьютер сделал свой ход, матрицу значений надо перерисовать, чтобы второй игрок видел картинку, правда? Но я в процедуре ComputerMove возвращаю НЕ 2 координаты (строку/столбец), а только одну, учитывая то, что при известном размере матрицы из 7-ой, например, позиции "растянутой" матрицы получить 3-ю строку и 1-ый столбец не составит труда...


Ну да, это же основное правило составления рекурсивных подпрограмм: сначала проверяется условие выхода, и только если оно НЕ выполняется, рекурсивный вызов продолжается. Иначе очень просто получить бесконечную рекурсию, и как результат - переполнение стека и RunTime Error...

Спасибо за обьяснение! Если возникнут вопросы, я опять вас побеспокою! :D

volvo Здравствуйте, извините, значит в вашей последней программе в последней процедуре уже ничего не надо добовлять?После вызова ai? Или нужно что-то делать с R.pos? Я уже несколько раз перечитывала ваше обьяснение, но никак не могла понять что надо еще что-то добавлять или нет?

Надо, конечно Я просто привел сам способ реализации AI; после вызова

AI(CurrMatrix, ToUse);

будет известна оптимальная матрица, но нужно ведь еще выбрать очередной ход (их же может быть несколько...) Например, у нас на данный момент заполнено 3 элемента:
а после вызова AI будет известна оптимальная матрица:

(это просто пример, так что не надо обращать внимание на конкретные значения... ) Так вот, процедура ComputerMove должна выбрать, какое из чисел, присутствующих во второй матрице, и НЕ присутствующих в первой будет очередным ходом компьютера, то есть, для моего примера, у компьютера есть возможность сделать 6 разных ходов, которые могут привести его к выигрышу: 4 в позицию (1, 1); 5 в позицию (1, 2) и т.д.

Какой именно вариант выбрать и нужно решить сразу после вызова AI...