[PHP] Een AI voor 4 op een rij!

[jochemh]

Zo, na wat simpel programmeer werk met het normale websites maken met php, ben ik gaan kijken wat er allemaal nog meer mee mogelijk is. Na een sudoku puzzel oplosser ( http://www.jochemh.nl/sudoku.php ) was ik van plan een 4 op een rij spelletje te maken, wat natuurlijk bij iedereen bekend voorkomt. Dit tot nu toe: http://www.jochemh.nl/4/. Nou is mijn vraag: hoe kan ik een computerspeler maken, dus eigenlijk een artificiële intelligentie?

Een idee zou misschien kunnen zijn om voor elk leeg vakje een soort positieve kans uit te rekenen (om te kijken bij welk vakje de computer de meeste kans heeft om te winnen, gebasseerd op welke 4 op een rij-mogelijkheden er zijn) en negatieve kansen (om te kijken bij welk vakje de tegenstander zou kunnen winnen). Ik weet nog niet precies hoe ik dit zou kunnen aanpakken. Misschien heeft iemand een (beter) idee?

Jochem

[TweakerNummer]

Je zou kunnen kijken wat anderen gedaan hebben. Bijv zoals http://www.geocities.com/...ystem/3517/C4/C4Conv.html

Dat is dus gewoon domweg vooruit kijken met een maximale diepte btw.

[ Voor 22% gewijzigd door TweakerNummer op 16-05-2007 19:56 ]

[jochemh]

Bij die link stat dat je in de console kunt kijken, maar dan zie je alleen de moves die de computer verzint, en de source code is veel te ingewikkeld om zo te doorgronden. Ik heb nu meer een oppervlakkig idee nodig. Toch bedankt!

[Creepy]

Kijk eens naar het minimax algoritme. Dat is toch wel een van de makkelijkere algoritmes voor "AI" (tis eigenlijk gewoon bruteforce ).

[Serpie]

Creepy schreef op woensdag 16 mei 2007 @ 21:33:
Kijk eens naar het minimax algoritme. Dat is toch wel een van de makkelijkere algoritmes voor "AI" (tis eigenlijk gewoon bruteforce ).

Leuke tip, boeiend, ik vond deze link http://ai-depot.com/articles/minimax-explained/ ik ga me ook maar eens verdiepen in AI's lijkt me leuk. Wellicht heb ik er wat aan de volgende contests.

[Grijze Vos]

Misschien heb je hier wat aan:

http://files.pandemic.nl/~greyfox/IS-Assignment4.pdf

Kan ook nog wel de bijbehorende sourcecode opzoeken, als je daar mee wilt spelen. (Delphi 7)

[Verwijderd]

Om het minder brute force te maken kan je Alpha/Beta pruning gebruiken.

[jochemh]

Het ziet er op het eerste gezicht allemaal lastig uit, maar het lijkt me toch leuk om hier wat tijd aan te besteden. PHP is natuurlijk helemaal niet bedoeld om 'spelletjes' mee te maken, maar het is zo gegroeit door het websites maken. Welke andere progammeertaal zouden jullie mij aanraden voor dit soort problemen en oplossingen?

[SchizoDuckie]

javascript?

elk probleem is te tackelen in elke programmeertaal. Het hangt van je eigen skill level af of JIJ het ook kan, en als je échte skillz hebt snapt elke programmeur ook nog wat je doet in je code

[ Voor 104% gewijzigd door SchizoDuckie op 17-05-2007 10:39 ]

[BestTested!]

Verwijderd schreef op donderdag 17 mei 2007 @ 03:03:
Om het minder brute force te maken kan je Alpha/Beta pruning gebruiken.

Het spel 4-op-een rij is al opgelost voor de meest standaard formaten. Inderdaad met alpha-beta pruning (of eigenlijk PVS of Negascout, maar dat is bijna hetzelfde). Hoewel Monte-Carlo het ook helemaal niet slecht doet in deze setting.
De meesta AI's voor x-op-een rij op een M x N veld werken met alpha-beta pruning, met een aantal uitbreidingen (Quiesence Search, Transposition Tables, Null-Move heuristic, Iterated Deepening, Killer moves en History Heuristics) = Lekker google materiaal.

Mocht je je standaard alpha-beta pruning hebben gemaakt, dan zijn al deze uitbreidingen zonder al te veel moeite toe te voegen, en heb een goede AI van redelijk niveau.

[Creepy]

Verwijderd schreef op donderdag 17 mei 2007 @ 03:03:
Om het minder brute force te maken kan je Alpha/Beta pruning gebruiken.

De link die Serpie heeft gevonden legt ook alpha-beta uit

[Grijze Vos]

Document wat ik gelinkt heb bevat uitleg over standaard minimax, alpha-beta pruning en iterative deepening.

[jochemh]

Het ziet er allemaal interressant uit, maar geen idee hoe ik dit allemaal in praktijk ga brengen. Dit vraagt wel heel wat uurtjes, maar het is toch een leuk onderwerp!

[Verwijderd]

http://www.jochemh.nl/4/2spelers.php?kolom=-35

zou nog wat debuggen...

[jochemh]

Verwijderd schreef op donderdag 17 mei 2007 @ 22:42:
http://www.jochemh.nl/4/2spelers.php?kolom=-35

zou nog wat debuggen...

IK zie het, maar eigenlijk gaat het bij mij meer om het uitproberen en toepassen van iedeen dan het werkelijk spelen van dit spel, alhoewel dat natuurlijk wel leuk zou zijn. Bedankt!