Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

[Weird_Sheep]

Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

Ein Kumpel und ich sollen für die Berufsschule das wunderschöne XXO in Pascal realisieren.
Bedingung: Der Computer darf nicht verlieren!

Nun ja, wir haben jetzt schon einiges versucht und der Computer spielt auch schon ein paar Runden, aber er ist zu schlagen, da er immer das selbe Spiel spielt

Man findet zum Minimaxalgorithmus im Allgemeinen recht viel nur nicht konkret auf XXO bezogen, sodass wir den Knackpunkt finden könnten.

Solltet ihr also wissen, was falsch ist, oder wie man die "KI" programmieren kann, sei es in Pascal, Pseudocode oder sonst was Erkennbares, wären wir doch sehr dankbar, wenn ihr es uns wissen lasst

function MaxZuege(var ASpielfeld : XxoSpielfeld) : integer;
var x, ergebnis : integer;
begin
ergebnis := 0;
For x := 1 to 9 do
begin
if ASpielfeld[x] = 0 then ergebnis := ergebnis + 1;
end;
MaxZuege := ergebnis;
end;

{Kopiert ein XxoSpielfeld}
procedure filltempfeld(var ASpielfeld : XxoSpielfeld);
var zaehler : integer;
begin
For zaehler := 1 to 9 do
begin
TempFeld[zaehler]:=ASpielfeld[zaehler];
end;
end;


function ZugSimulation(position:shortint;spieler:shortint) : boolean;
var x : shortint;
gesetzt : boolean;
begin
ZugSimulation := false;
If (Tempfeld[position] = 0) then
begin
Tempfeld[position] := spieler;
ZugSimulation := true;
end;
end;


function maxWert : longint;
var zuege : integer;
ermittelt, zugwert: longint;
GemachterZug : shortint;
begin

ermittelt := -2147483647;
for zuege := 1 to 9 do{MaxZuege(TempFeld) do }
begin
if ZugSimulation(zuege,1) then
begin
if (MaxZuege(Tempfeld)=0) then
begin
zugwert := checkwin(tempfeld);
end
else
begin
zugwert := minwert;
end;
TempFeld[zuege]:= 0;
if zugwert > ermittelt then
begin
ermittelt := zugwert;
maxzug := zuege;
end;
end;
end;
maxwert := ermittelt;

end;

function minWert : longint;
var x : integer;
ermittelt, zugwert : longint;
GemachterZug : ShortInt;
begin
ermittelt := 2147483647;
for x := 1 to 9 do{MaxZuege(Tempfeld) do}
begin
if ZugSimulation(x,-1) then
begin
if (MaxZuege(Tempfeld)=0) then
begin
zugwert := checkwin(TempFeld);
end
else
begin
zugwert := maxwert;
end;
TempFeld[x] := 0;
if zugwert < ermittelt then
begin
ermittelt := zugwert;
minzug := x;
end;
end;
end;
minwert := ermittelt;
end;

 

[W_A_R_M_U_U_H]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

hi
nachdem ich deinen thread gelesen hab, dachte ich mir, beschäftigste dich auch mal damit...hab an sich kaum ne ahnung von KI und Co
nun, ich hab es wie folgt gemacht:
für jedes feld mußt du den nutzen ausrechnen, welcher sich so ergibt:
nutzen[x][y] = (mögliche reihen) + (horiz) + (vert) + (diag)

wobei horiz/vert/diag =
(halt für jede richtung spezifisch)
(eigene Steine - gegnerische Steine) ^2 (^2 hat den sinn, dass dadurch 2 eigene/gegnerische steine in reihe stärker gewichtet werden, dadurch werden eigene reihen vervollständigt oder gegnerische reihen verhindert)

hat warsch eher weniger mit minmax oder suchbäumen zu tun, aber is (für mich) einfacher zu verstehen ;D

ach ja: bisher hab ichs noch nich geschafft, gegen ihn zu gewinnen...
hoffe, ich konnte helfen

 

[LemanRuzz]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

Das ist ganz einfach! Der Computer darf nicht verlieren? kein problem. Bei XXO gewinnt IMMER derjenige der anfängt wenn er es richtig macht.
er muss nur sein Zeichen in die mitte setzten, also so:

===
=X=
===

dann macht zb der spieler das:

=O=
=X=
===

nun setzt der Computer einfach ein X in eine der ecken

=OX
=X=
===

nun muss der spieler um nicht zu verlieren sein o so setzen:

=OX
=X=
O==

jetzt setzt der Comp noch ein x zwischen seine beiden

=OX
=XX
O==

schon hat der spieler keine möglichkeit mehr einen Sieg des Comp zu verhindern.
Noch Fragen?

 

[Herr-Sengele]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

*blablubb* Minimax für XXO

Wenn man nun noch nach Tic Tac Toe suchen würde....
http://www.google.de/search?biw=1150&hl=de&q=minimax+tic+tac+toe&btnG=Google-Suche&meta=

findet man sowas.

Ich würde den zweiten Treffer empfehlen, ist recht gut gemacht mit Minimax, vor allem auch elegant schon mit alpha-beta-prunning, hab eures jetzt nur überflogen, glaube aber ihr habt das nicht gemacht.

gruß&hth,

edit: Nein, ihr habt kein prunning gemacht.

 

[W_A_R_M_U_U_H]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

@lemanRuzz

tschuldige, aber das is totaler schwachsinn...
XXO is n spiel, wenn zwei computer gegeneinander spielen, kann KEINER gewinnen...
da sinn beide völlig gleichberechtigt.
Ich könnt nu beispiele bringen, aber google einfach ma, oder beschäftige dich damit, du wirst auf das gleiche ergebnis kommen...

 

[Worrel]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

=O=
=X=
===

hier ist der spielerische Fehler:

Um den Zugzwang im übernächsten Zug zu verhindern, muß man das O in eine Ecke setzen:

==O
=X=
===

Und wie schon richtig gesagt wurde: Wenn beide gut aufpassen, gewinnt nie einer:

X=O
=X=
===

X=O
=X=
==O

X=O
=XX
==O

X=O
OXX
==O ...

 

[ganswijk]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

=O=
=X=
===

hier ist der spielerische Fehler:

Um den Zugzwang im übernächsten Zug zu verhindern, muß man das O in eine Ecke setzen:

==O
=X=
===

There is only one tricky and very counterintuitive sequence:

X==
===
===

X==
=O=
==X

X==
=O=
O=X

O has lost now, because X can do:

X=X
=O=
O=X

O should have played:

X==
OO=
==X

It's quite easy to trick people with this sequence, because people have learned that the central box is very important to have and after that to occupy the corner boxes.

 

[fre4er]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

hi,
ich würde einfach alle möglichkeiten durchprobieren.
schafft der computer leicht.
dann schaust du bei welchem zug es eine sichere möglichkeit gibt nicht zu verlieren (oder besser zu gewinnen), die nimmst du her.
Am besten mit einer funktion die dir zurückgibt ob die stellung gewonnen, verloren oder unentschieden ist + rekursiver aufruf.
wenn dir das zu primitiv ist, kannst du ja alle schon ausgerechneten stellungen in eine matrix speichern und abrufen wenn du sie baruchst, der computer braucht dann die nachfolgenden nicht mehr ausrechnen. Ob du sie schon ausgerechnet hast schaust du am anfang. nennt man dynamische programmierung, ist viel schneller, aber bei diesem programm egal.

 

[Weird_Sheep]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

hi,
ich würde einfach alle möglichkeiten durchprobieren.
schafft der computer leicht.
dann schaust du bei welchem zug es eine sichere möglichkeit gibt nicht zu verlieren (oder besser zu gewinnen), die nimmst du her.
Am besten mit einer funktion die dir zurückgibt ob die stellung gewonnen, verloren oder unentschieden ist + rekursiver aufruf.
wenn dir das zu primitiv ist, kannst du ja alle schon ausgerechneten stellungen in eine matrix speichern und abrufen wenn du sie baruchst, der computer braucht dann die nachfolgenden nicht mehr ausrechnen. Ob du sie schon ausgerechnet hast schaust du am anfang. nennt man dynamische programmierung, ist viel schneller, aber bei diesem programm egal.

Uiuiui, erstmal danke für die Antworten, hab gar nicht damit gerechnet, dass noch jemand antwortet und habs jetzt nur durch Zufall in den Top100 gesehen.

Nun ja, mittlerweile haben wir auch unseren Fehler gefunden, ne Variable war lokal statt global deklariert und so ist der Minmax nicht den ganzen Baum durch sondern ist mal eben nach dem ersten Durchgang stehen geblieben...

Wer mal ne Runde spielen will: XXO_o

 

[Freezeman]

AW: Benötige Minimaxalgorithmus für XXO (Tic Tac Toe)

hi,
ich würde einfach alle möglichkeiten durchprobieren.
schafft der computer leicht.
dann schaust du bei welchem zug es eine sichere möglichkeit gibt nicht zu verlieren (oder besser zu gewinnen), die nimmst du her.
Am besten mit einer funktion die dir zurückgibt ob die stellung gewonnen, verloren oder unentschieden ist + rekursiver aufruf.
wenn dir das zu primitiv ist, kannst du ja alle schon ausgerechneten stellungen in eine matrix speichern und abrufen wenn du sie baruchst, der computer braucht dann die nachfolgenden nicht mehr ausrechnen. Ob du sie schon ausgerechnet hast schaust du am anfang. nennt man dynamische programmierung, ist viel schneller, aber bei diesem programm egal.

Uiuiui, erstmal danke für die Antworten, hab gar nicht damit gerechnet, dass noch jemand antwortet und habs jetzt nur durch Zufall in den Top100 gesehen.

Nun ja, mittlerweile haben wir auch unseren Fehler gefunden, ne Variable war lokal statt global deklariert und so ist der Minmax nicht den ganzen Baum durch sondern ist mal eben nach dem ersten Durchgang stehen geblieben...

Wer mal ne Runde spielen will: XXO_o

Öhm, ich hab grad gewonnen, kein scheiss, echt! Ich dachte der Computer sollte immer gewinnen?!