mboost-dp1
No Thumbnail
Kan egentlig ikke se det vilde i det. Det er jo bare at lade computeren stå og tygge i den algoritme og så er den skid slået.
Det er det samme i det noget mindre avancerede kryds og bolle - der kan selv jeg altid mindst opnå uafgjort.
Det er det samme i det noget mindre avancerede kryds og bolle - der kan selv jeg altid mindst opnå uafgjort.
Hvis den/de har stået i 18 år er det vel fordi de ikke har udskiftet computeren i mellemtiden.. Så hvis man startede med de computere vi har i dag ville det tage 2 måneder :D
Og nej jeg synes heller ikke det er imponerende i et så simpelt spil som det her... Det bliver noget andet med poker, der tror jeg det bliver meget svært for et program at blive god. Ja selvfølgelig kan den udregne den præcise sandsynlighed for at den har den bedste hånd til hver en tid. Men den har nok meget svært ved at læse modstanderens ud fra hans draws/calls/bets osv.
Og nej jeg synes heller ikke det er imponerende i et så simpelt spil som det her... Det bliver noget andet med poker, der tror jeg det bliver meget svært for et program at blive god. Ja selvfølgelig kan den udregne den præcise sandsynlighed for at den har den bedste hånd til hver en tid. Men den har nok meget svært ved at læse modstanderens ud fra hans draws/calls/bets osv.
#3 Lav selv et program til det, og du vil se det svære i det, der er ikke bare tale om "brute force" simuleringer af an talrække, det er faktisk ikke helt let at simulere diverse brætspil.
#7 Det er svært at tro, men matematikere er faktisk ikke idioter, og nej, man lader ikke bare én dedikeret computer stå med udregninger. Typisk lader man et netværk stå for det, så er det sågar muligt for dem der holder styr på computerne, løbende at tilslutte "nutidens computere" og derefter lade dem bidrage til udregningerne. Det er de færeste tunge beregninger man vil overlade til en enkelt cpu.
#7 Det er svært at tro, men matematikere er faktisk ikke idioter, og nej, man lader ikke bare én dedikeret computer stå med udregninger. Typisk lader man et netværk stå for det, så er det sågar muligt for dem der holder styr på computerne, løbende at tilslutte "nutidens computere" og derefter lade dem bidrage til udregningerne. Det er de færeste tunge beregninger man vil overlade til en enkelt cpu.
#13 Et simpelt spil er ingen garanti for at en computer klarer sig godt. Lige netop i dam er det at computeren spiller godt fordi brikkerne skal bevæge sig i nogle faste baner, men selv med disse fastlagte træk kræver det meget effektiv programmering. Go (http://en.wikipedia.org/wiki/Go_%28game%29) er, på samme måde som dam, et "enkelt" spil. På trods af dette klarer computerne sig forholdsvist elendigt.
Ja, det måtte jo ske på et tidspunkt. Men 18 år er stadig rimelig lang tid.
---
#3 - Hvordan er det overhovedet muligt at spille uafgjort i kryds og bolle?
#7 - Et computerprogram kan ikke laves til at spille perfekt poker. Såvel som et computerprogram heller ikke kan forudsige terningekast. Det kan simpelthen ikke lade sig gøre.
Men hvis man dropper at det skal spille perfekt, så kan man da (med det rette hardware og ikke kun software) godt optimere programmet til at spille bedst muligt til en hvis grænse. Men perfekt - nej.
---
#3 - Hvordan er det overhovedet muligt at spille uafgjort i kryds og bolle?
#7 - Et computerprogram kan ikke laves til at spille perfekt poker. Såvel som et computerprogram heller ikke kan forudsige terningekast. Det kan simpelthen ikke lade sig gøre.
Men hvis man dropper at det skal spille perfekt, så kan man da (med det rette hardware og ikke kun software) godt optimere programmet til at spille bedst muligt til en hvis grænse. Men perfekt - nej.
#15 kryds og bolle er uafgjort når der ikke kan lægges flere brikker. Og bare fordi der er stokastiske variable, kan man godt have en optimal strategi. Denne vil være "perfekt" også selvom den taber et stokastisk antal hænder så længe den over tid vinder flere hænder end en hvilken som helst anden strategi.
Det er faktisk relativt simpelt at lave en algoritme der finder alle mulige træk i et zero-sum spil (altså et spil hvor det der tabes og det der vindes giver nul når det lægges sammen).
Min-Max algoritmen (eller minimax som den også kaldes) bruges til at opbygge et træ over alle mulige træk i det pågældende spil.
I kryds og bolle ville første niveau således være 9 forskellige muligheder, alt efter hvor spilleren vælger at sætte sin bolle. For hver af de 9 muligheder er der så derefter 8 muligheder for hvor den anden spiller sætter sit kryds. Så er der 7 muligheder, og sådan fortsætter det så til spillet når et punkt hvor en spiller har vundet, eller det er uafgjort (disse punkter kaldes for terminal states). Hver terminal state bliver så givet en vægt (utility value) alt efter om det er computeren der vinder (+1), modstanderen der vinder (-1) eller om det bliver uafgjort (0). Disse vægte bliver så sendt opad i træet og bliver brugt til at vælge et træk.
Valget foregår ved at computeren går ud fra at modstanderen vil vælge det træk der er bedst for ham selv og værst for computeren. Det prøver computeren så at undgå ved at vælge det træk der vil føre til en terminal state som er den bedste af de dårlige.
Et andet eksempel på valget kunne være hvis jeg tilbød en bruger på newz at vælge mellem to poser, hvorefter jeg så vælger en ting i een af de to poser som vedkommende får. I pose nummer et er der nøglerne til en Ferrari og en rådden sild. I den anden pose er der 100kr og nøglerne til en anden Ferrari. Det bedste valg vil i den forbindelse være posen med nøgler og 100kr, fordi man (eller computerens min-max algoritme) vil gå ud fra at jeg vil vælge det dårligste at give væk.. Så man får ikke en Ferrari, men i det mindste fik man da 100kr i stedet for en rådden sild.
Der er dog et par problemer med min-max algoritmen, det største er at jo flere muligheder og brikker der er i et spil, jo længere tid vil det tage at analysere alle træk til bunds. Det har man opfundet et par løsninger på, f.eks. alpha-beta pruning som bruges ved at man holder øje med om en terminal state er dårligere end den man allerede har fundet, og hvis den er, kan man ignorere resten af den del af træet. Som i eksemplet med poserne: Først ser man at den ene pose har 100kr og bilnøgler.. Man ser så at pose nummer to har en rådden sild, og så er det lige meget hvor godt resten af indholdet er, for man ved at man får fisken hvis man vælger den pose. Problemet med den fremgangsmåde er at hvis man ser det dårligste til sidst hver gang man kigger i en pose, vil søgningen gennem træet stadig tage lige så lang tid som hvis man ikke brugte alpha-beta pruning.
En anden løsning er at man på forhånd vælger hvor mange træk man vil se på, og derefter kun lader træet søge til den dybde (cut-off search).. Tilstanden af brikkerne og deres placering vurderes derefter som hvis det var en terminal state. Det vil sige at i kryds og bolle vil to på stribe blive vægtet højere, end to placeret tilfældigt. Ulempen ved den slags søgning er at algoritmen bliver sårbar overfor langsigtede strategier. I skak vil det f.eks. være svært for computeren at gennemskue et forsøg på at flytte en bonde hele vejen til den anden ende af brættet for at få en dronning. I professionelle skakspil bruger man derfor normalt en cut-off search hvor en anden algoritme derefter kigger på de mulige træk og søger længere i dybden med ting der ser interessante ud (så som den med at flytte bonden).
Jeg formoder dog at Chinook har søgt hele træet med muligheder i bund, siden det har taget så mange år. Kunne være interessant at se hvor lang tid det ville tage for en moderne computer.
Min-Max algoritmen (eller minimax som den også kaldes) bruges til at opbygge et træ over alle mulige træk i det pågældende spil.
I kryds og bolle ville første niveau således være 9 forskellige muligheder, alt efter hvor spilleren vælger at sætte sin bolle. For hver af de 9 muligheder er der så derefter 8 muligheder for hvor den anden spiller sætter sit kryds. Så er der 7 muligheder, og sådan fortsætter det så til spillet når et punkt hvor en spiller har vundet, eller det er uafgjort (disse punkter kaldes for terminal states). Hver terminal state bliver så givet en vægt (utility value) alt efter om det er computeren der vinder (+1), modstanderen der vinder (-1) eller om det bliver uafgjort (0). Disse vægte bliver så sendt opad i træet og bliver brugt til at vælge et træk.
Valget foregår ved at computeren går ud fra at modstanderen vil vælge det træk der er bedst for ham selv og værst for computeren. Det prøver computeren så at undgå ved at vælge det træk der vil føre til en terminal state som er den bedste af de dårlige.
Et andet eksempel på valget kunne være hvis jeg tilbød en bruger på newz at vælge mellem to poser, hvorefter jeg så vælger en ting i een af de to poser som vedkommende får. I pose nummer et er der nøglerne til en Ferrari og en rådden sild. I den anden pose er der 100kr og nøglerne til en anden Ferrari. Det bedste valg vil i den forbindelse være posen med nøgler og 100kr, fordi man (eller computerens min-max algoritme) vil gå ud fra at jeg vil vælge det dårligste at give væk.. Så man får ikke en Ferrari, men i det mindste fik man da 100kr i stedet for en rådden sild.
Der er dog et par problemer med min-max algoritmen, det største er at jo flere muligheder og brikker der er i et spil, jo længere tid vil det tage at analysere alle træk til bunds. Det har man opfundet et par løsninger på, f.eks. alpha-beta pruning som bruges ved at man holder øje med om en terminal state er dårligere end den man allerede har fundet, og hvis den er, kan man ignorere resten af den del af træet. Som i eksemplet med poserne: Først ser man at den ene pose har 100kr og bilnøgler.. Man ser så at pose nummer to har en rådden sild, og så er det lige meget hvor godt resten af indholdet er, for man ved at man får fisken hvis man vælger den pose. Problemet med den fremgangsmåde er at hvis man ser det dårligste til sidst hver gang man kigger i en pose, vil søgningen gennem træet stadig tage lige så lang tid som hvis man ikke brugte alpha-beta pruning.
En anden løsning er at man på forhånd vælger hvor mange træk man vil se på, og derefter kun lader træet søge til den dybde (cut-off search).. Tilstanden af brikkerne og deres placering vurderes derefter som hvis det var en terminal state. Det vil sige at i kryds og bolle vil to på stribe blive vægtet højere, end to placeret tilfældigt. Ulempen ved den slags søgning er at algoritmen bliver sårbar overfor langsigtede strategier. I skak vil det f.eks. være svært for computeren at gennemskue et forsøg på at flytte en bonde hele vejen til den anden ende af brættet for at få en dronning. I professionelle skakspil bruger man derfor normalt en cut-off search hvor en anden algoritme derefter kigger på de mulige træk og søger længere i dybden med ting der ser interessante ud (så som den med at flytte bonden).
Jeg formoder dog at Chinook har søgt hele træet med muligheder i bund, siden det har taget så mange år. Kunne være interessant at se hvor lang tid det ville tage for en moderne computer.
#20
det der pruning er jo noget snavs.
hvis vi antager der er poser:
pose 1) ferrari + sild
pose 2) ferrari + 100kr
efter det er der igen et valg mellem 2 poser
pose 1->1) fantasiliard kr + kød
pose 1->2) fantasiliard kr + pengetank
pose 2->1) knappenål
pose 2->2) badeand
hvis der bliver brugt dit pruning koncept så vil man jo gå glip af en fantasiliard kr + pengetank og i stedet ville man få en badeand. dette scenarie kan jo findes overalt på et træ og det vil derfor være dumt at begynde at prune før en kamp er afgjort.
selvfølgelig er det vigtigt at tænke på at de forskellige branches kan have variable "utility values", men selv der vil det blive et problem idet computeren stadig skal udregne enhver mulig situation for at bedømme om et givent træk er bedre end et andet på længere sigt.
sådan noget i den stil.
det der pruning er jo noget snavs.
hvis vi antager der er poser:
pose 1) ferrari + sild
pose 2) ferrari + 100kr
efter det er der igen et valg mellem 2 poser
pose 1->1) fantasiliard kr + kød
pose 1->2) fantasiliard kr + pengetank
pose 2->1) knappenål
pose 2->2) badeand
hvis der bliver brugt dit pruning koncept så vil man jo gå glip af en fantasiliard kr + pengetank og i stedet ville man få en badeand. dette scenarie kan jo findes overalt på et træ og det vil derfor være dumt at begynde at prune før en kamp er afgjort.
selvfølgelig er det vigtigt at tænke på at de forskellige branches kan have variable "utility values", men selv der vil det blive et problem idet computeren stadig skal udregne enhver mulig situation for at bedømme om et givent træk er bedre end et andet på længere sigt.
sådan noget i den stil.
#17 - Vi tænker vist på to forskellige spil.
Er kryds og bolle ikke spillet hvor den ene spiller har tre kryds-brikker og den anden har tre cirkler (boller), og man så skal få tre på stribe på en 3x3 bane?
Men du tænker nok på det, hvor man ikke må flytte brikker. Det er en version jeg ikke kan se nogen mening i, da man altid bliver uafgjort, medmindre den ene spiller ikke kender spillet. Det er ikke et spil.
Er kryds og bolle ikke spillet hvor den ene spiller har tre kryds-brikker og den anden har tre cirkler (boller), og man så skal få tre på stribe på en 3x3 bane?
Men du tænker nok på det, hvor man ikke må flytte brikker. Det er en version jeg ikke kan se nogen mening i, da man altid bliver uafgjort, medmindre den ene spiller ikke kender spillet. Det er ikke et spil.
Opret dig som bruger i dag
Det er gratis, og du binder dig ikke til noget.
Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.
- Forside
- ⟨
- Forum
- ⟨
- Nyheder
Gå til bund