Hej jag håller på att göra en liten spelar boot till ett schack spel jag gör. Boten är ingen mästare på scack men den ska inte vara helt hjärn död heller. Jag har alldrig gjort något liknande och undrar därför om någon kan hjälpa mig att förklara vilka metoder man använder för att göra en sådan AI allt bygger ju på regler men verkar lite drygt att sitta och köra if-sattser för alla möjliga kombinationer ;) Kan ni gen någon bra hänvisning till litteratur eller www adresser så skulle jag vara tacksam. Eller det kanske rent av finns någon som man direkt kan konsultera där ute.

MVH Henrik L

Hej,

Kul uppgift! Har flera gånger själv börjat skriva schack-spelande program men aldrig riktigt slutfört det...hoppas du kommer längre.

Det finns hur mycket teori som helst för att skriva ett schackprogram och jag kan inte dra allt här (för jag vet inte allt :-). Men några fundamentala delar är :

* Spelets regler
* Skapa ett träd av giltiga drag
* Målfunktion, dvs hur bra är ett visst drag (eller snarare positionen efter att draget är utfört).
* Välj ut bästa draget
* Optimeringar

Låt oss gå igenom dom något mer detaljerat.

* Spelets regler

Skapa en funktion som genererar en lista med alla giltiga drag. Här måste du ta hänsyn till alla spelets regler, schack matt, schack, rockad, pjäsuppgradering, en passant m m. Denna lista används för att bygga upp sökträdet.

* Skapa ett träd av giltiga drag

Skapa en rotnod som representerar den nuvarande positionen på brädet. För varje giltigt drag, skapa en barnnod till rotnoden med positionen efter att respektive drag är genomfört. Detta är det som på engelska kallas för en "ply" (en term du kommer att stöta på säkert om du söker vidare på internet), dvs ett drag oavsett om det är svart eller vit som gjort draget. För varje nod på nivå ett så genererar du en lista av giltiga motdrag och lägger in dessa i trädet och så har du skapat ply 2, o s v. Hur många nivåer du ska studera beror på hur lång betänketid du har, processorhastighet m m. Se även under optimering nedan.

* Målfunktion

Målfunktionen ska utifrån en viss position, ett visst läge i spelet, räkna ut vem (svart eller vit) som "leder". Skapa en funktion som returnerar ett flyttal (t ex mellan -1000 och +1000) där positiva värden representerar en schackposition som är gynsam för dig och negativa värden tvärtom gynsamma för motspelaren. Om positionen innebär att en spelare står i schackmatt så ska -1000 eller +1000 returneras. Tal nära noll innebär förstås att spelet är jämnt för tillfället. Hur denna funktions ska skrivas är omöjligt att säga, det är här dina schackkunskaper kommer in. Ju bättre din funktion "räknar ut" ställningen på brädet, desto bättre kommer ditt program att kunna spela. Du måste ta hänsyn till båda material (pjäser) och position...

* Välj ut bästa draget

En annan lite knepig del av ditt program. En hyffsat enkel algoritm är minimaxalgoritmen eller alpha-beta-algoritmen som jag också tror den kallas. Sök på dessa namn på internet så hittar du bättre beskrivningar på den. Här handlar det iallafall om att MAXIMERA värdet på målfunktionen i nivå ett i trädet (du vill ju göra ett så bra drag som möjligt), men samtidigt måste du förutsätta att din motspelare gör sitt bästa motdrag så på nivå två måste du MINIMERA värdet. Om din målfunktion säger att du har ett drag som ger värdet +20 så kanske du tycker att du ska välja det, men om ett av motspelarens svar på ditt drag ger -30 så är det ju inte bra för dig. Förutsätt alltid att din motspelare spelar lika bra eller bättre än du.

När din tid är ute, eller när du grävt klart i trädet av möjliga spelmöjligheter så måste du bestämma dig för ett drag. Du måste nu leta upp den nod på lägsta nivån (alltså noder som inte har några andra barnnoder) som har det högsta värdet (vilket ju är bra för dig, negativa värden på målfunktionen är bra för motståndaren).

* Optimering

Om du har ett giltigt drag som direkt leder till ett stort negativt värde så ska du kanske överväga att inte gräva djupare i den noden eftersom det kan vara svårt att repa sig efter ett sådant nederlag. Bättre är kanske att gräva djupare i ett drag som verkar positivare. Att hela tiden gräva ett visst antal nivåer kommer aldrig leda till ett riktigt bra program. Förr eller senare måste du gallra och titta nogrannare på mer intressanta drag. Se upp för horisontproblemet...det kanske ser ut som om du förlorar ett torn, men om du hade analyserat ett drag eller två till hade du kanske vunnit en dam!! Kanonsvårt att bedöma var man ska söka vidare.


Jag har säkert glömt något väsentligt, men hur som helst...Det är ingen liten uppgift du har framför dig dock. Lycka till...

En bra länk som beskriver minimax, negamax samt alphabeta-algoritmerna :

http://www.fierz.ch/strategy1.htm

Tackar för den fina beskrivningen. Vet du någon bra bok som behandlar det där med att skapa träd och sedan söka i dem. Gärna en bok på svenska men engelaska böcker funkar också.

MVH Henrik L

Tyvärr inte...jag har själv några ganska tunga böcker om algoritmteori där algoritmerna finns beskrivna men de är knappast idealiska för att bara lösa ett enskilt problem. Jag skulle nog hellre kontakt en datorschackklubb eller en vanlig schackklubb och be om tips. Det finns garanterat med praktiska böcker än algoritmteoriböcker som är tunglästa...

det finns en jätte bra bok som tar upp hur man gör ai spelar i schack..
"spel programmering på 3 veckor med visual basic"
tror den går att köpa på pagina.se