Hexspel
Hur hittar man på en värderingsfunktion för postioner i Hex ?
Vad är Hex? Pratar du om hexadecimala tal?
I så fall: på samma sätt som det decimala talet 2025 är samma sak som 2*103 + 0*102 + 2*101 + 5*100 så är det hexadecimala talet 2025sexton samma sak som 2*163 + 0*162 + 2*161 + 5*160.
Nej, ett spel för två personer på ett bräde som består av hexagoner.
Bedinsis skrev:Vad är Hex? Pratar du om hexadecimala tal?
I så fall: på samma sätt som det decimala talet 2025 är samma sak som 2*103 + 0*102 + 2*101 + 5*100 så är det hexadecimala talet 2025sexton samma sak som 2*163 + 0*162 + 2*161 + 5*160.
Som Laguna beskrev så är Hex ett brädspel med hexagoner som positioner. Två personer splar mot varandra genom att koppla ihop sin sida till motsående sida. Till exempel spelare 1 försöker att koppla ihop vänster till höger sida och spelare 2 topp- till bottensida. Varje splear får sätta en pjäs på en hexagon åt gången.
jag är inte säker på vad en evalueringsfunktion är.
Men typ: 100 spelare 1 har vunnit -100 om spelare 2 har vunnit.
Osäkra positioner, räkna proportionen av möjliga sätt spelare 1 kan vinna och antal sätt spelare 2 kan vinna.
En evalueringsfunktion i spel är ett talvärde som räknas ut från den aktuella ställningen och kan användas för att bedöma hur bra den spelaren står. T.ex. används den när man vill hitta bästa möjliga nästa drag: man låtsas att man gör draget och räknar ut evalueringsfunktionen, för alla möjliga drag, sedan tar man det bästa draget.
Ok men jo jag fattade att det typ var det.
Problemet här blir lite, vad är det för funktion man söker.
Å ena sidan är hex ett deterministiskt spel utan möjlighet till oavgjort så fundamentalt sett skulle den ideala funktionen vara binär, 1 om spelare 1 vinner 0 om spelare 2 vinner. Men för att hitta den funktionen behöver man lösa spelet och det känns inte som att det är det som efterfrågas.
Så antagligen efterfrågas en heuristisk funktion, något som ger en hyfsad indikation av vilken spelare som står bättre. Något i stil med "räkna poäng" i schack. Frågan är sedan hur enkel rent beräkningsmässigt den funktionen behöver vara.
Jag föreslog en heuristisk funktion ovan men den är antagligen väl beräkningstung för enklare syften. En mindre beräkningsintensiv funktion skulle kunna vara att räkna antal möjliga vinnande stigar spelare 1 har jämfört med antal möjliga vinnande stigar spelare 2 har. Den kvoten exvis. observa dock att en spelare kan ha 0 möjliga vinnande stigar så man får hantera det specialfallet, men då har ju spelare också förlorat (om spelare x inte kan vinna så har spelare y redan vunnit eftersom oavgjort är omöjligt)
Sen om den föreslagna funktionen är bra eller inte får man väl testa, se hur stark en hexdator som spelar enligt den algoritmen blir. Alltså en dator som väljer det drag som maxar den kvoten.
Smutsmunnen skrev:Ok men jo jag fattade att det typ var det.
Problemet här blir lite, vad är det för funktion man söker.
Å ena sidan är hex ett deterministiskt spel utan möjlighet till oavgjort så fundamentalt sett skulle den ideala funktionen vara binär, 1 om spelare 1 vinner 0 om spelare 2 vinner. Men för att hitta den funktionen behöver man lösa spelet och det känns inte som att det är det som efterfrågas.
Så antagligen efterfrågas en heuristisk funktion, något som ger en hyfsad indikation av vilken spelare som står bättre. Något i stil med "räkna poäng" i schack. Frågan är sedan hur enkel rent beräkningsmässigt den funktionen behöver vara.
Jag föreslog en heuristisk funktion ovan men den är antagligen väl beräkningstung för enklare syften. En mindre beräkningsintensiv funktion skulle kunna vara att räkna antal möjliga vinnande stigar spelare 1 har jämfört med antal möjliga vinnande stigar spelare 2 har. Den kvoten exvis. observa dock att en spelare kan ha 0 möjliga vinnande stigar så man får hantera det specialfallet, men då har ju spelare också förlorat (om spelare x inte kan vinna så har spelare y redan vunnit eftersom oavgjort är omöjligt)
Det står ingenting om det är heuristisk eller någon annan sorts funktion. Dock refererar uppgiften till en annan tidigare uppgift i boken där man använder ett sådant träd för att förutse näst bästa draget för spelare 1 i ett spel som schack:
Anslutningslägen (terminal positions) i trädet är 3, 0 och -3. Spelare 2 minimerar resultaten och får 0 utav 3 och 0 och -3 utav 0 och -3. Däremot försöker spelare 1 maximera sin poäng som leder till 0. 
Marx skrev:
Jamen jag menar det som är problemet är väl snarare vad 0, -3 och 3 representerar? Alltså det är väl det som är evalueringsfunktionen. Schack är ju på samma sätt ett deterministiskt spel, i och för sig med möjlighet till remi, så i princip är varje position antingen vit vinst, remi eller svart vinst. Men eftersom schack är så komplext vet man normalt sett inte med matematisk säkerhet vilken position som är vad, så man använder heuristiska värderingar. Nybörjare brukar ge varje pjäs ett poängvärde bonde =1, häst,löpare=3, torn =5, dam =9 och addera. Schackdatorer har mer avancerade funktioner, men fortfarande heuristiska, typ en dubbelbonde är inte längre värd 1 utan 0,9, riktigt avancerade schackdatorer maskininlär sina egna värderingsfunktioner men det är fortfarande heuristiska funktioner.
Hex är nog mindre komplext än schack men jag tror att det fortfarande väsentligen inte är lösbart som studentuppgift. Så jag vet inte om jag missförstår uppgiften men i princip tolkar jag uppgiften som att den går ut på att hitta på en hyfsat rimlig heuristisk värderingsfunktion.
Smutsmunnen skrev:Marx skrev:
Jamen jag menar det som är problemet är väl snarare vad 0, -3 och 3 representerar? Alltså det är väl det som är evalueringsfunktionen. Schack är ju på samma sätt ett deterministiskt spel, i och för sig med möjlighet till remi, så i princip är varje position antingen vit vinst, remi eller svart vinst. Men eftersom schack är så komplext vet man normalt sett inte med matematisk säkerhet vilken position som är vad, så man använder heuristiska värderingar. Nybörjare brukar ge varje pjäs ett poängvärde bonde =1, häst,löpare=3, torn =5, dam =9 och addera. Schackdatorer har mer avancerade funktioner, men fortfarande heuristiska, typ en dubbelbonde är inte längre värd 1 utan 0,9, riktigt avancerade schackdatorer maskininlär sina egna värderingsfunktioner men det är fortfarande heuristiska funktioner.
Hex är nog mindre komplext än schack men jag tror att det fortfarande väsentligen inte är lösbart som studentuppgift. Så jag vet inte om jag missförstår uppgiften men i princip tolkar jag uppgiften som att den går ut på att hitta på en hyfsat rimlig heuristisk värderingsfunktion.
Det är exakt så som du beskriver "Nybörjare brukar ge varje pjäs ett poängvärde bonde =1, häst,löpare=3, torn =5, dam =9 och addera".
Och ja uppgiften lyder så här:
Hitta på en värderingsfunktion för Hex lik den för schack och sedan implementera funktionen i ett program som kan se k steg framför sig. Om funktionen fungerar korrekt så bör spelare 1 med k=2 förlora mot spelare två med k=3 där båda spelarna styrs av datorn.
Det sista kriteriet är ju lite komplicerat ett en dator med k=2 ska förlora mot en dator med k=3, det är inte uppfyllt i fallet schack med den värderingsfunktionen.
En superenkel funktion vore kanske något i stil med: spelare xs poäng= antal drag i rad spelare x skulle behöva spela för att vinna. Det vill säga antal missing links så att säga. Om det är mitt drag och jag behöver 1 drag för att vinna så är det det draget jag ska spela. Strategi skulle kunna vara: minimera mina poäng/motståndarens poäng . Om jag har 1 poäng och det är min tur så ska jag spela det vinnande draget, då blir min kvoten 0, kan aldrig bli lägre. Om min moståndare har ett vinnande drag så ska jag stoppa det annars får han 0 poäng vilket maximerar kvoten.
