[Delphi] Checkers denktijd

[Verwijderd]

Ik ben bezig met het maken van dammen(Checkers) in Delphi ik heb hierin een soort van AI gemaakt die door middel van een algoritme alle mogelijke zetten bij langs gaat tot een bepaalde diepte en dan het beste resultaat teruggeeft.

Het is onmogelijk om alle mogelijke zetten bij langs te gaan dus ik moet het programma niet meer dan 8 zetten diep laten zoeken anders duurt het veel te lang.

Ik moet nu dus van te voren een diepte opgeven en dan is het maar afwachten hoe lang het programma erover doet voordat hij op die diepte is en de beste zet terug geeft.

Is het ook mogelijk het algoritme zo te maken dat hij bijvoorbeeld 10 seconden zoektijd krijgt, deze volledig benut met het zoeken en dan exact na 10 seconden de beste zet teruggeeft ? Dit is handiger dan een bepaalde diepte opgeven want de "denktijd" verschilt nu afhankelijk van het aantal zet mogelijkheden en de snelheid van de computer.

[Fulcrum2000]

Tip: Ga eens zoeken naar het minimax-algoritme.

[Verwijderd]

Fulcrum2000 schreef op vrijdag 03 juni 2005 @ 18:26:
Tip: Ga eens zoeken naar het minimax-algoritme.

Ik gebruik het minimax algoritme ook, met een alpha beta cutoff, dus op zich is hij al vrij snel, maar ik zit nu dus met de tijd. Heb liever dat ik de denktijd van de computer kan instellen dan dat ik hem gewoon maar tot een bepaalde diepte moet laten rekenen en dan maar afwachten hoe lang het duurt.

[Fulcrum2000]

Verwijderd schreef op vrijdag 03 juni 2005 @ 18:32:
[...]

Ik gebruik het minimax algoritme ook, met een alpha beta cutoff, dus op zich is hij al vrij snel, maar ik zit nu dus met de tijd. Heb liever dat ik de denktijd van de computer kan instellen dan dat ik hem gewoon maar tot een bepaalde diepte moet laten rekenen en dan maar afwachten hoe lang het duurt.

Gewoon na elke niveau checken hoeveel tijd verstreken is.
bv 4 ply diep en tijd < 10 sec --> volgende ply, 5 ply diep en tijd < 10 sec --> volgende ply etc.

Hier heb je inderdaad niet exact 10 sec, maar dat zou je kunnen inbakken door na 10 sec de beste score van de laatste volledig doorrekende ply te nemen.

[ Voor 14% gewijzigd door Fulcrum2000 op 03-06-2005 18:40 ]

[Verwijderd]

Is het dan niet zo dat hij maar 1 branche 10 seconden lang gaat doorzoeken ? Ik werk niet met Threads namelijk

[ Voor 4% gewijzigd door Verwijderd op 03-06-2005 18:48 ]

[Fulcrum2000]

Verwijderd schreef op vrijdag 03 juni 2005 @ 18:45:
Is het dan niet zo dat hij maar 1 branche 10 seconden lang gaat doorzoeken ? Ik werk niet met Threads namelijk

Threads zijn niet nodig. De truc van goede schaakprogramma's (implementatie technisch hetzelfde als checkers) is eerst alles volledig door te rekenen op 1 ply, daarna alles tot 2 ply etc. Dus 'horizontaal' door je boom heen en niet vertikaal. Dit wordt geloof ik ook wel eens het iteratieve alfa-beta algoritme genoemd.

Een goed boek over deze materie is overigens : Schaken voor computers van Peter van Diepen & Jaap van den Herik

[ Voor 12% gewijzigd door Fulcrum2000 op 03-06-2005 18:57 ]

[Verwijderd]

Dat kan toch nooit erg efficient zijn, dan bereken je de eerste ply's meerdere keren overnieuw, dat kost toch meer tijd dan dat je meteen tot een bepaalde diepte rekent ?

Dan kan ik volgens mij beter het programma door laten zoeken naar een bepaalde diepte die altijd wel binnen bijvoorbeeld 10 seconden te doen is dan steeds de eerste ply's weer overnieuw te doorzoeken.

[whoami]

Threads hebben hier geen nut; de operaties worden niet tegelijkertijd uitgevoerd mbhv threads, en aangezien je geen I/O ofzo doet, maar de hele tijd cpu-tijd nodig hebt, zal multi-threading zelfs nadeliger zijn.

[Fulcrum2000]

Verwijderd schreef op vrijdag 03 juni 2005 @ 19:05:
Dat kan toch nooit erg efficient zijn, dan bereken je de eerste ply's meerdere keren overnieuw, dat kost toch meer tijd dan dat je meteen tot een bepaalde diepte rekent ?.

Deze tijd schijn je weer ruimschoots terug te winnen doordat je betere alpha-beta cut-offs krijgt op deze manier. Kijk eens rond op internet (bv open source schaakprogramma's) en probeer een copy te krijgen van dat boek.

[Verwijderd]

Fulcrum2000 schreef op vrijdag 03 juni 2005 @ 19:20:
[...]


Deze tijd schijn je weer ruimschoots terug te winnen doordat je betere alpha-beta cut-offs krijgt op deze manier. Kijk eens rond op internet (bv open source schaakprogramma's) en probeer een copy te krijgen van dat boek.

Aha ja dat is ook zo, dus gewoon een kwestie van alles tot 1 diep berekenen, dan sorteren (beste zet eerst) dan op 2 diep, en zo door.
Dan is alpha beta cutoff indeed een stuk effectiever. en kan ik ook beter rekening houden met de tijd.
Bedankt , hier kan ik wel mee verder !

[Soultaker]

Fulcrum2000 schreef op vrijdag 03 juni 2005 @ 18:55:
De truc van goede schaakprogramma's (implementatie technisch hetzelfde als checkers) is eerst alles volledig door te rekenen op 1 ply, daarna alles tot 2 ply etc. Dus 'horizontaal' door je boom heen en niet vertikaal. Dit wordt geloof ik ook wel eens het iteratieve alfa-beta algoritme genoemd.

Horizontaal zoeken is hier absoluut niet handig, omdat je in een korte tijd veel meer nodes genereert dan je in je geheugen op kunt slaan; ik denk dat je een vrij oud boek hebt gelezen of het verkeerd hebt begrepen.

De truc van steeds een stap dieper gaan heet trouwens iterative deepening.

Verwijderd schreef op vrijdag 03 juni 2005 @ 19:05:
Dat kan toch nooit erg efficient zijn, dan bereken je de eerste ply's meerdere keren overnieuw, dat kost toch meer tijd dan dat je meteen tot een bepaalde diepte rekent?

Dat geeft niet. Stel dat je een branching factor van 20 hebt (dat zijn dus gemiddeld 20 zetten in elke situatie) dan doorzoek je met een diepte van 9 dus 20⁹ + 20⁸ + .. + 20 = 538.947.368.421 stellingen; dat lijkt veel, maar het is vrij weinig vergeleken met de 20¹⁰ = 10.240.000.000.000 stellingen die je de volgende keer doorzoekt (het is rond de 6% overhead).

Verwijderd schreef op vrijdag 03 juni 2005 @ 19:29:
Aha ja dat is ook zo, dus gewoon een kwestie van alles tot 1 diep berekenen, dan sorteren (beste zet eerst) dan op 2 diep, en zo door.
Dan is alpha beta cutoff indeed een stuk effectiever. en kan ik ook beter rekening houden met de tijd.

Klopt, zetten goed sorteren is erg belangrijk. Een praktische manier om dat te doen (in tegenstelling tot wat Fulcrum2000 voorstelde) is in je zoekalgoritme eerst alle zetten met een gereduceerde diepte te doorzoeken, ze op het resultaat daarvan te sorteren, en dan 'echt' te gaan zoeken. Dit kost (met eenzelfde redenering als hierboven) weinig extra tijd, die je hoopt terug te winnen met een groter aantal afkappingen.

Overigens kun je als je een goede transpositietabel gebruikt ook nog beginnen met kleinere alfa-beta vensters (waarvoor je de waarden die je in eerdere iteraties met iterative deepening had gevonden kunt gebruiken) waardoor je meer afkappingen krijgt; als je dan niet direct een beste zet vind maak je het venster wat groter.

[Fulcrum2000]

Soultaker schreef op vrijdag 03 juni 2005 @ 20:05:
[...]

Klopt, zetten goed sorteren is erg belangrijk. Een praktische manier om dat te doen (in tegenstelling tot wat Fulcrum2000 voorstelde) is in je zoekalgoritme eerst alle zetten met een gereduceerde diepte te doorzoeken, ze op het resultaat daarvan te sorteren, en dan 'echt' te gaan zoeken. Dit kost (met eenzelfde redenering als hierboven) weinig extra tijd, die je hoopt terug te winnen met een groter aantal afkappingen.

Volgens mij is dit precies wat ik bedoelde, ik legde het alleen een stuk onduidelijker uit

[BasieP]

het nadeel aan die methode is, dat je nooit een ECHT inteligente AI zult hebben, want 'opoffering' word dan al snel nadeling op de korte termijn, en zal zo nooit als een 'goede zet' behandeld worden

wat ook slim is, is om terwijl de user aan zet is ook alvast dingen te berekenen. dit kost wel extra rekenkracht (omdat je alle zetten van de tegenstander van die buurt er bij moet doen) maar scheeld vast wel iets

[ Voor 39% gewijzigd door BasieP op 03-06-2005 23:24 ]

[Soultaker]

Hmm, wat ik dus bedoel is zoiets: (pseudo-code natuurlijk)

code:

negamax(depth)
{
    if(depth == 0)
        return evaluate();
    else
    {
        moves = generate_moves;
        if(depth > 2) {
            for each move {
                do move;
                estimate[move] = -negamax(depth - 3);
                undo move;
            }
            sort moves by estimates;
        }

        for each move {
            do move;
            value[move] = -negamax(depth - 1);
            undo move;
        }
        return best move;
    }
}

Het cruciale punt is dat je niet de zoekboom in je geheugen houdt ofzo en daarin gaat sorteren; je hebt alleen de lijst zetten waar je nu mee werkt. Je geheugen bewaar je om een zo groot mogelijke transpositietabel in te zetten, zodat je zonder grote bezwaren efficiënte window searches kunt doen.

Ik dacht dat jij voorstelde om de boom horizontaal te doorzoeken, wat betekent dat je een queue in een orde grootte van de zoekboom moet bijhouden. Dat was vroeger een zinnige strategie maar op moderne computers die wel heel snel rekenen maar relatief weinig en vooral traag geheugen hebben echt niet meer verstandig. Als je dit niet zo bedoelde, dan mijn excuses.

[Fulcrum2000]

Yep, ik geloof dat dit het ongeveer was. Ik heb vele jaren geleden eens geprobeerd een schaakprogrammatje in pascal te programmeren. Helaas ben ik er nooit echt ver mee gekomen

Het boek dat ik aanhaalde is inderdaad al redelijk gedateerd, zaken (trucjes) als de Null-Move en dubbele Null-Move staan er volgens mij niet in.

[Soultaker]

BasieP schreef op vrijdag 03 juni 2005 @ 23:22:
het nadeel aan die methode is, dat je nooit een ECHT inteligente AI zult hebben, want 'opoffering' word dan al snel nadeling op de korte termijn, en zal zo nooit als een 'goede zet' behandeld worden

Volgens mij kan echte 'opoffering' ook nooit uit; als je het opofferen van stukken voor een verbeterde stelling bedoelt: dat kan wel en zal een goede AI ook doen, omdat dat meegenomen wordt in een goede evaluatiefunctie.

wat ook slim is, is om terwijl de user aan zet is ook alvast dingen te berekenen. dit kost wel extra rekenkracht (omdat je alle zetten van de tegenstander van die buurt er bij moet doen) maar scheeld vast wel iets

Mja, echt opschieten doet het niet echt, want je denkt dan met een snelheid van 1 gedeeld door de branching factor; wat die bij dammen is weet ik niet precies maar bij schaken soms wel iets van 15-20. Misschien kan je dan beter van alleen de meest waarschijnlijke (paar) tegenzet(ten) uitgaan, want die had je toch al bedacht.

[Fulcrum2000]

Nog een mooie link gevonden waar je zeker wat ideeen kunt opdoen: Chess Programming Theory
http://www.frayn.net/beowulf/theory.html

[Verwijderd]

https://gathering.tweaker...message/51294349#51294349

[Creepy]

In het topic waar je naar linkt was het niet duidelijk genoeg? Je kicket een topic uit 2005! Let aub even op voordat je post.