Wątek przeniesiony 2016-01-03 01:10 z Delphi i Pascal przez furious programming.

Algorytm MINIMAX w kółko i krzyżyk

0

Witam. Mam problem z zaimplementowaniem algorytmu MINIMAX do gry kółko i krzyżyk. Program się kompiluje, z tym że komputer nie zawsze wybiera najlepszą drogę, tj. da się z nim wygrać. Czy ktoś mógłby wskazać mój błąd, albo zaproponować inne podejście do problemu? Z góry dziękuję.


program minimax;

var tab : array[1..9] of char;
    gracz : char;
    i : integer;

procedure plansza;
var i  : integer;

begin
  writeln;
  for i := 1 to 9 do
  begin
    write (' ', tab[i], ' |');
    if ((i = 3) or (i = 6)) then
    begin
      writeln;
      writeln('------------');
    end;
  end;
  writeln;
  writeln;
end;

function wygrana (g : char; sprawdzanie : boolean) : boolean;
var test : boolean;
    i : integer;

begin
  test := false;
  for i := 0 to 2 do
  begin
    if (tab[1 + 3*i] = g) and (tab[2 + 3*i] = g) and (tab[3 + 3*i] = g) then test := true;
    if (tab[1 + i] = g) and (tab[4 + i] = g) and (tab[7 + i] = g) then test := true;
  end;
  if (tab[1] = g) and (tab[5] = g) and (tab[9] = g) then test := true;
  if (tab[3] = g) and (tab[5] = g) and (tab[7] = g) then test := true;
  if (test) then
  begin
    if (not sprawdzanie) then
    begin
       plansza;
       writeln('Wygrywa ', g);
    end;
    wygrana := true;
  end
  else wygrana := false;
end;

function remis (sprawdzanie : boolean) : boolean;
var i : integer;
    pom : boolean;

begin
  pom := false;
  for i := 1 to 9 do
  begin
    if(tab[i] = ' ') then
    begin
      remis := false;
      pom := true;
    end;
  end;
  if (not pom) then
  begin
    if (not sprawdzanie) then
    begin
      plansza;
      writeln('Remis');
      remis := true;
    end;
  end;
end;

function minimax(gracz : char) : integer;
var m, mmx, i : integer;
    pom : boolean;

begin
  pom := false;
  if (wygrana(gracz, true)) then
  begin
    if (gracz = 'X') then
    begin
      pom := true;
      minimax := 1;
    end
    else if (gracz = 'O') then
    begin
      pom := true;
      minimax := -1;
    end;
  end;
  if (remis(true)) then
  begin
    pom := true;
    minimax := 0;
  end;
  if (not pom) then
  begin
    if (gracz = 'X') then gracz := 'O'
    else if (gracz = 'O') then gracz := 'X';
    if (gracz = 'O') then mmx := 10
    else if (gracz = 'X') then mmx := -10;
    for i := 1 to 9 do
    begin
      if (tab[i] = ' ') then
      begin
        tab[i] := gracz;
        m := minimax (gracz);
        tab[i] := ' ';
        if (((gracz = 'O') and (m < mmx)) or ((gracz = 'X') and (m > mmx))) then mmx := m;
      end;
    end;
    minimax := mmx;
  end;
end;

function komputer (gracz : char) : integer;
var ruch, i, j, m, mmx : integer;

begin
  mmx := -10;
  for i := 1 to 9 do
  begin
    if (tab[i] = ' ') then
    begin
      tab[i] := gracz;
      m := minimax (gracz);
      tab[i] := ' ';
      if (m > mmx) then
      begin
        mmx := m;
        ruch := i
      end;
    end;
  end;
  komputer := ruch;
end;

procedure ruch (gracz : char);
var r : integer;

begin
  plansza;
  if (gracz = 'O') then
  begin
    {writeln('Wybierz ruch: ');
    writeln('1 2 3');
    writeln('4 5 6');
    writeln('7 8 9');
    readln(r); }
    writeln('Ruch komputera');
    r := komputer('O');
  end
  else
  begin
    writeln('Ruch komputera');
    r := komputer('X');
  end;
  if ((r >= 1) and (r <= 9) and (tab[r] = ' ')) then tab[r] := gracz;
end;

begin
  for i := 1 to 9 do tab[i] := ' ';
  //gracz := 'O';
  while ((not wygrana('X', false)) and (not wygrana('O', false)) and (not remis(false))) do
  begin
    ruch('O');
    ruch('X');
   { if (gracz = 'O') then gracz := 'X'
    else gracz := 'O';  }
  end;
  readln;
end.
0
marcelel napisał(a):
  if (tab[1] = g) and (tab[2] = g) and (tab[3] = g) then test := true;

Czy słyszałeś o takim wynalazku jak pętla?

marcelel napisał(a):
while ((wygrana('X', false) = false) and (wygrana('O', false) = false) and (remis(false) = false)) do

Zapamiętaj sobie. jeżeli piszesz:

  • coś == true - to robisz jakąś bzdurę wystarczy samo coś - prawie w każdym języku;
  • coś == false - to robisz jakąś bzdurę wystarczy not coś - (pomijając inny zapis negacji w innych językach) prawie w każdym języku;
0

Poprawione.

Mógłbyś jakoś pomóc w rozwiązaniu mojego problemu?

0
marcelel napisał(a):

Poprawione.
Wszędzie czy tylko we wskazanych miejscach?
Może warto wkleić poprawiony kod, aby inni też mogli przeanalizować bez specyficznych reakcji organizmu?

0

Wkleiłem poprawiony we wskazanych miejscach kod.

0
marcelel napisał(a):
    if (tab[1 + 3*i] = g) and (tab[2 + 3*i] = g) and (tab[3 + 3*i] = g) then test := true;
...
  if (tab[1] = g) and (tab[5] = g) and (tab[9] = g) then test := true;

Jakoś wydaje mi się że wciąż nie zawsze pamiętasz o istnieniu pętli.

marcelel napisał(a):
if (pom = false) then

Na temat =true oraz =false teź nie do końca zrozumiałeś.

0

Poprawiłem wszystkie fragmenty związane z true i false, natomiast nie wiem, jak i przede wszystkim po co, mam zastosować pętlę we wskazanym przez Ciebie fragmencie, skoro sprawdzam tylko skosy?

1
  1. Pomyśl jeszcze na temat pętli, jeżeli nic nie wymyślisz sensownego to masz podpowiedź const win:array[8,3]of Byte=((1,2,3),(4,5,6), ...
  2. If w pascalu nie potrzebuje nawiasów okrągłych czyli piszemy if tab[i]=' ' then lub if not pom then
  3. Usuń nadmiar zmiennych
  4. Popracuj nad nazewnictwem zmiennych
  5. Uniwersalizuj nazewnictwo, raz masz gracza nazwanego jako g a w innej funkcji już gracz
  6. Stwórz sobie tabliczkę const Sign:array[Boolean]of Char=('O','X'); teraz gracza możesz oznaczać jako true/false więc zamiast:
if (gracz = 'X') then gracz := 'O'
    else if (gracz = 'O') then gracz := 'X';

wystarczy gracz:=not gracz; oraz w wielu innych miejscach
7. Zmień minmax na function minimax(gracz,turnOf:Boolean):Integer; liczymy dla gracz teraz ruch gracza turnOf
8. Problemem jest to że twoja funkcja minmax nie sumuje całej ścieżki ruchu mmx należy podzielić na dwie różne zmienne.

0

@marcelel - po pierwsze zmień typ zmiennej tab na tablicę dwuwymiarową:

var
  Tab: array [0 .. 2, 0 .. 2] of Char;

Łatwiej będzie dobierać indeksy, bez kombinacji z mnożeniem; Nazwę też zmień, bo nic nie mówi o przeznaczeniu tej zmiennej.

0
_13th_Dragon napisał(a):

Problemem jest to że twoja funkcja minmax nie sumuje całej ścieżki ruchu mmx należy podzielić na dwie różne zmienne.

Nie za bardzo rozumiem. Mógłbyś dokładniej wyjaśnić, jak mam podzielić tę zmienną?

furious programming napisał(a):

po pierwsze zmień typ zmiennej tab na tablicę dwuwymiarową:

Próbowałem tak zrobić na początku, lecz wtedy nie mam pomysłu, jak przekazać wartość

ruch
do funkcji
komputer

function komputer (gracz : char) : integer;
var ruch, i, j, m, mmx : integer;

begin
mmx := -10;
for i := 1 to 9 do
begin
if (tab[i] = ' ') then
begin
tab[i] := gracz;
m := minimax (gracz);
tab[i] := ' ';
if (m > mmx) then
begin
mmx := m;
ruch := i
end;
end;
end;

  • komputer := ruch;**
    end;
0

Współrzędne komórki możesz trzymać w zmiennej typu TPoint.

1 użytkowników online, w tym zalogowanych: 0, gości: 1