[Prolog] minimax algorithme in 4 op een rij

[Masterdam]

Ik ben nu in Prolog '4 op een rij' aan het schrijven, en wilde het minimax algorithme schrijven.

Ik krijg echter steeds de error:

code:

ERROR: Arguments are not sufficiently instantiated
Exception: (29) beter_dan(6, 2, 7, _G16579, wit, _G16581, _G16582) ? creep
Exception: (19) beste_zet(3, [7], [ (5, 1), (4, 2), (4, 1)]+[ (7, 2), (7, 1)], zwart, _G15713, _G15714) ? creep

en snap niet hoe ik het kan oplossen.

Mijn code tot nu toe is:

PHP:

% minimax(N): Kies een zet volgens het minimax algoritme met cut-off diepte N. 
% De diepte wordt geteld in het aantal zetten, waarbij elke zet bestaat uit een 
% steen die door een speler gezet wordt.

minimax(N, Bord, Kleur, Zet) :-
    minimax_hulp(N, Bord, Kleur, Zet, _Waarde).

minimax_hulp(_N, Bord, _Kleur, _Zet, Waarde) :-
    \+ legale_zet(Bord, _X),
    evalueer(Bord, Waarde). 
    
minimax_hulp(0, Bord, _Kleur, _Zet, Waarde) :-
    % !, 
    evalueer(Bord, Waarde).
    
minimax_hulp(N, Bord, Kleur, BesteZet, Waarde) :-
    N>0,
    findall(X, legale_zet(Bord, X), LlegaleZetten),
    beste_zet(N, LlegaleZetten, Bord, Kleur, BesteZet, Waarde).
    
beste_zet(N, [BesteZet], Bord, Kleur, BesteZet, Waarde) :-
    % !, 
    maak_bord(Bord, Kleur, BesteZet, NieuwBord),
    NewDepth is N-1,
    andere_speler(Kleur, AndereKleur),
    minimax_hulp(NewDepth, NieuwBord, AndereKleur, _Zet, Waarde).
        
beste_zet(N, [Head|LlegaleZetten], Bord, Kleur, BesteZet, BesteWaarde) :-
    LlegaleZetten \= [],
    maak_bord(Bord, Kleur, Head, NieuwBord),
    NewDepth is N - 1,
    andere_speler(Kleur, AndereKleur),
    minimax_hulp(NewDepth, NieuwBord, AndereKleur, _BestOfHead, WaardeHead),
    beste_zet(N, LlegaleZetten, Bord, Kleur, BestOfTail, WaardeTail),
    beter_dan(Head, WaardeHead, BestOfTail, WaardeTail, AndereKleur, BesteZet, BesteWaarde).
    
beter_dan(Eerstezet, Eerstewaarde, _Tweedezet, Tweedewaarde,'wit', Eerstezet, Eerstewaarde) :-
    Eerstewaarde > Tweedewaarde. 

beter_dan(_Eerstezet, Eerstewaarde, Tweedezet, Tweedewaarde,'zwart', Tweedezet, Tweedewaarde) :-       
    Eerstewaarde > Tweedewaarde.
    
beter_dan(_Eerstezet, Eerstewaarde, Tweedezet, Tweedewaarde,'wit', Tweedezet, Tweedewaarde) :-           
    Eerstewaarde =< Tweedewaarde.
    
beter_dan(Eerstezet, Eerstewaarde, _Tweedezet, Tweedewaarde,'zwart', Eerstezet,  Eerstewaarde) :-
    Eerstewaarde =< Tweedewaarde.

evalueer(Bord, Waarde) werkt trouwens ook nog niet optimaal, maakt nu alleen gebruik van of iemand bijna wint of bijna verliest, en hoeveel stenen iemand in de middelste kolom heeft, hier ga ik nu waarschijnlijk even aan werken, met minimax zie ik het even niet meer zitten.

Een Bord is gerepresentateerd als twee lijsten (Lwit en Lzwart), die elk een verzameling coordinaten hebben (dus als in: [(1,2),(1,3)] ) op een bord van 7 bij 7. Een zet is gelijk aan een kolomnummer.
De rest lijkt me redelijk voor zich spreken

Heeft iemand een idee hoe ik dit op kan lossen?

edit:

PHP tags gebruikt

[ Voor 3% gewijzigd door Masterdam op 14-06-2003 16:05 ]

[Soultaker]

Doe eens de QuickStart lezen over hoe je een fatsoenlijke topicstart maakt. Vergeet niet te vermelden welke Prolog-implementatie je gebruikt en probeer eens te debuggen.

[Verwijderd]

Zorg eens dat er regelnummers voor staan want ik ga niet tellen waar 29ergens zit...
Ik ken niets van prolog maar volgens mij is het gewoon ergens een foutje bij het doorgeven van je argumenten.
Laat ze eens allemaal geprint worden op het scherm zodat je hun waardes kan zien, dat zal je mss een stuk verder helpen

[Masterdam]

Het zijn geen regelnummers, wat het wel zijn weet ik trouwens ook niet...
Ik gebruik SWI-Prolog 5.0.10
Debuggen ben ik trouwens al een paar dagen mee bezig, en het begint nu vrij redelijk te werken, alleen minimax dus nog niet....

[ Voor 38% gewijzigd door Masterdam op 14-06-2003 15:56 ]

[djluc]

Als je ze tussen bijvoorbeeld PHP tags zet worden ze wel genummerd geloof ik.

[Masterdam]

Dit is voor de evalueer-functie, maar weet iemand hoe je met dit soort dingen in prolog de waarde van Teller er kan laten uitkomen? Dit is een probleem wat ik eigenlijk best vaak tegenkom in dit programma en ik kom 'r steeds niet uit...

code:

tel_drie_op_rij(Bord, Kleur, Teller) :-
    findall(X, legale_zet(Bord, X), LlegaleZetten),
    tel_drie_op_rij_hulp(Bord, Kleur, LlegaleZetten, 0).
        
tel_drie_op_rij_hulp(_Bord, _KLeur, [], _Teller).

tel_drie_op_rij_hulp(Bord, Kleur, [Head|LlegaleZetten], Teller) :-
    maak_bord(Bord, Kleur, Head, NieuwBord),
    drie_op_een_rij(NieuwBord, Kleur),
    NewTeller is Teller + 1,
    tel_drie_op_rij_hulp(Bord, Kleur, LlegaleZetten, NewTeller).
    
tel_drie_op_rij_hulp(Bord, Kleur, [Head|LlegaleZetten], Teller) :-
    maak_bord(Bord, Kleur, Head, NieuwBord),
    \+ drie_op_een_rij(NieuwBord, Kleur),
    tel_drie_op_rij_hulp(Bord, Kleur, LlegaleZetten, Teller).

[ Voor 5% gewijzigd door Masterdam op 14-06-2003 16:22 ]

[j_du_pee]

ftp://ftp.swi.psy.uva.nl/SWI-Prolog/refman4.1/refman.pdf een goed beginpunt misschien

ik heb wel een aantal blauwe maandagen SWI gedaan, maar was weg voor prolog begon

[Masterdam]

OK, thx voor de link iig, ik ben m nu aan t checken

edit:
ff doorgelezen, maar uiteindelijk weinig aan gehad. Ik heb ook al een boek liggen, maar het zijn meer een paar handigheidjes die ik niet doorheb.
Hoe je een teller bij kan houden die op 0 begint en toch nog gereturnd kan worden bijvoorbeeld, daar kom ik nu niet uit. En minimax dus niet...

[ Voor 75% gewijzigd door Masterdam op 14-06-2003 16:36 ]

[Soultaker]

Ik begrijp je probleem niet echt en ik heb ook niet veel zin om je code door te spitten, als je zelf niet bereid bent om te gaan debuggen (wat kut is met SWI-Prolog, maar kies dan een minder Spartaanse implementatie) en het probleem te isoleren van de rest van je code.

Het teller handigheidje kan ik je wel uitleggen; het is simpelweg gebaseerd op recursie. De lengte van een lijst wordt bijvoorbeeld zo berekent:

Prolog:

length([], 0).
length([Head|Tail], TailLength + 1) :- 
    length(Tail, TailLength).

(De constructie TailLength + 1 in de parameter van het predicaat wordt niet door alle Prolog-implementaties ondersteund; als alternatief kun je een extra statement van de vorm "Length is TailLength + 1" gebruiken, maar dan gebruiken sommige implementaties weer '=' in plaats van 'is'. Handig hè, standaardiseren?)

Jouw eigen tellerfunctie is wel wat ingewikkelder dan dat, maar het principe zal het zelfde zijn. Ik wil je daar ook best mee helpen, maar dan mag je me eerst duidelijk uitleggen hoe je je spelbord representeert en hoe je zelf gedacht had de boel te construeren.

Waarom gebruik je ueberhaupt een brakke taal als Prolog?

edit:
Overigens zal je in Prolog ook vaak aggregatieparameters gebruiken. Het lengte-voorbeeld wordt dan zoiets:

Prolog:

length(List, Length) :-
    length(List, 0, Length).

length([], Length, Length).
length([Head|Tail], Currentlength, Length) :-
    length(Tail, CurrentLength + 1, Length).

Het length/3 predikaat gebruikt nu de tweede parameter om de huidige lengte bij te houden, en de derde parameter om de totale lengte in te retourneren. Als het einde van de lijst bereikt is (de lijst is gelijk aan []) dan is de huidige lengte gelijk aan de totale lengte.

[ Voor 22% gewijzigd door Soultaker op 14-06-2003 17:53 ]