Ubuntu Sverige

Har spelat ganska mycket schack i mina år med några framgångar också. Spelar inte lika mycket idag tyvärr.
Häromdagen fick jag en ide om att jag skulle göra mitt egna schackprogram, troligtvis i java eftersom jag kan det bäst, och det är enkelt att göra ett gui samt att det är portabelt

Frågan är hur man gör en smart AI som motståndare man kan möta. Första tanken som slog mig var att den jämförde alla möjliga tänkbara drag som denne kan göra, och för varje drag jämför den vad motståndaren kan göra för drag, och för att sedan ytterligare göra en jämförelse vilket drag som är bäst i det skedet.
Det är inte så svårt att räkna ut att det blir en ENORM trädstruktur av tänkbara drag ganska snabbt, och troligtvis kommer CPUn inte få en lugn stund att beräkna alla drag och försöka dra en slutsats av det bästa draget.

Man kanske skulle låta datorn räkna max 10 drag framåt och försöka hitta drag där datorn har så få svagheter som möjligt (minst lika många pjäser, inga ensamna bönder, en skyddad kung, inga instängda pjäser osv)

Någon som har nåt tips?

Din första schackmotor kan du ju begränsa till 10 drag framåt på högsta svårighetsgraden och bara stegvis ta dig nedåt till 0 - vilket ungefär motsvarar mina kunskaper 

Då får du ju en uppfattning om HUR man kan bygga upp det utan att det blir för avancerat. Lite träning liksom...

Jo något sådant jag tänkte, problemet är att få datorn att förstå att denne står dåligt eller bra till efter 10 drag.

Laddade hem glchess till Ubuntu 7.04 och försökte begripa mig på koden, synd att jag inte kan någon Python syntax.

Ärligt talat skulle jag börja med att byggga en fungerande algoritm för 1 drag; "ryker min gubbe om jag ställer den där?"

Man kan studera Deep Blue som spöade Kasparov 

http://www.research.ibm.com/deepblue/home/html/b.html

upnorth skrev: Ärligt talat skulle jag börja med att byggga en fungerande algoritm för 1 drag; "ryker min gubbe om jag ställer den där?"

Problemet uppstår då datorn kan få in en snygg matt efter sin "bortsättning". I såfall skulle man kunna låta datorn kolla om den får in en matt inom ett antal drag längre fram, eller om den vinner något på den så får den lov att sätta en pjäs i slag

Antar att man kan göra olika aggressiva algoritmer, de som försöker rädda gubbarna så långt som möjligt och de som försöker ta så många som möjligt, alltså en motor som bara klarar ETT mål.

Då jag aldrig varit intresserad av schack (dock programmering) är det lite svårt att sätta sig in i hur beräkningarna skulle gå till...

Hittade det här om Deep Blue och Kasparov

http://www.research.ibm.com/deepblue/meet/html/d.2.html

Datorn är ju stendum men kan iterera massvis med kombinationer
och alltid välja bästa alternativet.

plun skrev: Hittade det här om Deep Blue och Kasparov

http://www.research.ibm.com/deepblue/meet/html/d.2.html

Datorn är ju stendum men kan iterera massvis med kombinationer
och alltid välja bästa alternativet.

Ja det finns ju vissa skillnader mellan en schackdator och en världsmästare. En dator kan inte bedöma en ställning rent positionellt utan är tvungen att göra beräkningar fram till slutet om det leder till vinst så kan den göra bedömningen att ställningen är bra. Jag hittade en algoritm som inte bara används till schackdatorer utan till andra 2 player brädspel också, som exempelvis tic tac toe

Algoritmen heter MiniMax och bygger på att man delar in alla drag i en trädstruktur som sedan analyseras från två tänkbara sidor (en för varje spelare) där den ena försöker vinna (maximera sina poäng) och den andra sidan försöker förhindra den första från att vinna o på så sätt öka sina egna chanser (minimera motståndarens poäng). Poängen får man för varje vinstvariant om jag förstått det hela rätt. Dock måste datorn i ett schackspel kapa av sina variant beräkningar nånstans eftersom annars blir det för stort. I ett schackparti kanske det finns 10 tillåtna drag löst räknat, och för varje drag finns det ytterligare 10 drag osv
Detta kan ju leda till att datorn missar något precis när den gör kapningen.

Hur allt detta ser ut i kod, eller pseudo kod är jag inte helt klar med än. Men det är något jag måste testa iaf