☰

» »

Klondike

Klondike

«
1
2

Thomas ::

No, mene pa zanima, je na Slotechu junak, ki bi znal sprogramirati Klondike pasjanso. Z majhnim twistom, tako da bi vedno kazalo, kako verjetno je da se se igra zloži, če igramo optimalno.

Verjetnost mora biti na 1% natančna in zelo real time.

Ni treba tega zares narest, dovolj bo rečt - znam ali ne znam.
Man muss immer generalisieren - Carl Jacobi

SFfreak ::

ne znam...

Thomas ::

Po nekaj letih občasnega razmišljanja sem zadnjič prišel do ideje, kako to narest.

Samo ne bom.
Man muss immer generalisieren - Carl Jacobi

Monster ::

kk sploh zgleda tale pasjansa ;).. se mi ne da googlat
Ka zaboga...

CCfly ::

Na prvi pogled bi šlo, na drugega verjetno malo manj, ...
Žal mi je Thomas , če bi imel čas bi verjetno zagrabil za tole.
"My goodness, we forgot generics!" -- Danny Kalev

Thomas ::

Tkole.
Man muss immer generalisieren - Carl Jacobi

CCfly ::

Uh verjetnost +- 1% bi bila precej težka, še posebej v realtime. Raje bom rekel ne znam.
"My goodness, we forgot generics!" -- Danny Kalev

Thomas ::

Ene 8 let nazaj sem učil svojega triletnika igrati Klondike. Niti malo se ni naučil še vse do današnjega dne. Edino kar je zanimivega pripomnil je blo:

A zej ksva tole karto gor dava, se je pa mrbitnost da se zloži pa povečova?

To takrat na začetku, potem pa nikoli več nič o tem!

No, jest sem študirov po tistem skoz, kako bi se dala ta "mrbitnost" sproti računat. Pa to seveda na podlagi informacij o vid(e)nih kartah, jasno.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Simko ::

Ampak, če bi računalnik računal verjetnost, bi 'gledal' vse karte - tiste vid(e)ne in tisti ki to niso, mar ne?

Če ni skrivnost - koliko otrok pa imaš? :)

Thomas ::

Ne, ne bi smel gledati vseh kart. Tudi če jih vidi, bi se "moral delat da jih ne".

Verjetnost je zanimiva za igralca z njegove, igralčeve perspektive na podlagi kart, ki jih je že videl. Da mu računalnik napiše 0%, ni zanimivo. Čeprav je razvidno iz kart ki jih igralec ne vidi.

To je pomembno.

Otrok? Huh ...
Man muss immer generalisieren - Carl Jacobi

OwcA ::

Je vsaka začetna delitev ob optimalni igri rešljiva?

Ker če ni, potem samo na podlagi ob pričetku obrnjenih kart težko kaj preveč sodiš igro (ali se motim?).
Otroška radovednost - gonilo napredka.

Thomas ::

Večina razdelitev ni rešljiva. Recimo, da 93%. Zato bi ti moral pred postavitvijo kart kazat 7%. Ko se namečejo, pa recimo 12%. Ker 12% vseh postavitev, s temile znanimi, se zloži. Potem poklikaš eno karto in na novo se preračuna verjetnost. Recimo 6%.

Ko je programu jasno, da zložiti ne moreš, napiše 0%, vendar se ti lahko dalje trudiš.

Če mu postane jasno da zdej pa zaneslivo lahko, napiše 100% in ponudi da sam dokonča razporejanje kart.
Man muss immer generalisieren - Carl Jacobi

Jst ::

A je to FreeCell v Windowsih?
Islam is not about "I'm right, you're wrong," but "I'm right, you're dead!"
-Wole Soyinka, Literature Nobelist
|-|-|-|-|Proton decay is a tax on existence.|-|-|-|-|

Thomas ::

Ne, Solitaire je. W WindoWsih.
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

hmm, zakaj pa ne bi začeli na 100% ?
Abnormal behavior of abnormal brain makes me normal...

demoness ::

Zato, ker sploh še ni dokazano, da je vsaka igra rešljiva (če se motim, naj me kdo prosim popravi).
Kar se pa programiranja tiče - hm, nisem sicer ravno na tekočem, kako se programirajo analize iger z nepopolno informacijo (kot hoče Thomas, da bi se simuliralo), ampak recimo da podobno kot tiste s popoolno in da smo zdaj nekje sredi igre. Znanih nam je k pozicij kart, neznanih 52-k. Za vseh teh 52-k kart je treba narediti drevo vseh možnosti, kje so katere. In za vsako od teh možnosti preveriti, ali je ob optimalni igri rešljiva, potem pa izračunati procente.

OK, recimo da bi se igralca (oz. vsaj poznavalca pravil) na podlagi popolne informacije dalo sprogramirati. Konec koncev so pravila, kvaliteta poteze in kdaj je igra zaključena precej jasno določeni pojmi, tako da ene evaluacijske funkcije za trenutno stanje (po kateri bi sodili, ali smo že končali in ali sploh še lahko) niti ne bi bilo tako težko napisati.

Zdi se mi, da bi bil tukaj večji problem prostor in čas. 52-k kart na 52-k pozicijah. Precej kombinacij. Za vsako od njih celo igralno drevo z vsemi možnimi potezami. Na vsakem koraku je možnih precej potez. Alfa-beta iskanje ne pride v poštev, ker moramo vedno pregledati VSE poti. Kombinatorična eksplozija pa v oblake...

No, mogoče se zadeve čisto narobe lotevam... moram pogledat, kako kaj delujejo računalniški igralci bridža in tako dalje. Ampak mislim, da je zadeva teoretično rešljiva, praktično pa mogoče, če imaš par terabajtov RAMa. :)
Don't you want to die, walk beside me evermore,
Don't you feel alive, like you never felt before...?

CCfly ::

Problem je samo zahtevana natančnost, ker rabiš skoraj popolno oceno. Če bi bila lahko natančnost manjša, ne bi bilo treba graditi vseh dreves, ampak samo približno s hevristiko oceniti število poti, ki so ustrezne.
"My goodness, we forgot generics!" -- Danny Kalev

demoness ::

Res je. :) Ampak Thomas je neusmiljen - ali nam hoče pa samo razmigati možgane in procesorje... :)
Don't you want to die, walk beside me evermore,
Don't you feel alive, like you never felt before...?

Thomas ::

Seveda, da vam hočem razmigati možgane. Tukaj na tem forumu je precej pametnih ljudi, pa se dela škoda, če ne migajo s svojimi intelekti. To prvo.

Kar se tiče Vesoljčevega vprašanja. Ja ne, ni 100% v začetku. Vsako 14. boš zložil od prilike. Kar da 7% za vsako. Potem ko se pokažejo 4 asi, pa je jasno, da teh 7% naraste. Če.

Kar se tiče demonessine pripombe, da "sploh še ni znano", vidim da je pomešala z "osvobodi kralja". Ne. Mislim na Klondike, tadrugo pasjanso iz Windowsow. Tam se VE, da je večina postavitev nerešljiva.

Mislim pa na setup, kjer je ENA karta naenkrat vidna, Las Vegas, in no timed. Edino tako je igra plemenita in vredna ukvarjanja. Ne bomo zdej z vsako šoango se šli, ane?
Man muss immer generalisieren - Carl Jacobi

demoness ::

Res je. Zamešala. :8) Hvala, Thomas.

Sem šla prav zanalašč igrat zdajle, da vidim. Zagamana igra. :) Ampak mogoče bi ravno zagamanost delovala v naš prid - ker je na vsakem koraku možnih manj potez, je število kombinacij (in s tem velikost drevesa) manjše. Še vedno je pa treba za vsako od nevidnih kart obdelati vse možnosti. Zadeva se še malo poenostavi, če predpostavimo, da je igralec "dober" in da si je zapomnil/zapisal, katere karte so se že odkrile zgoraj na kupu. Se pravi moja ideja ostaja.

Skratka, kaj rabimo? Seznam odkritih kart skupaj z njihovo pozicijo in enim status flagom dostopna/nedostopna (to so karte zgoraj na kupu in tiste, ki so zložene spodaj, pa tudi tiste , ki so na "končnih kupih" na vrhu, ker se jih tudi sme premikati). Evaluacija igre je število pospravljenih kart na zgornjih kupih - več ko jih je, bolje je. Maksimalna vrednost igre, to je zmaga, je torej 52. Poraz je vrednost, manjša od 52 in nobene možne poteze več (skupaj s preverjanjem ciklanja, da ne bi ene karte v nedogled nekonstruktivno prestavljali z enega kupa na drugega).

Če imamo seznam odkritih kart, imamo tudi seznam tistih, ki še niso odkrite. In jih na vsakem koraku premešamo v vse možne kombinacije in generiramo vse možne poteze po drevesih navzdol do zmage ali poraza. Potem pa preštejemo liste na najbolj spodnjem nivoju - tiste, ki imajo vrednost 52 in tiste, ki imajo kaj manj, in zračunamo procente.
Don't you want to die, walk beside me evermore,
Don't you feel alive, like you never felt before...?

Thomas ::

Razmišljaš v tapravo smer demoness. Težava je v tem, da je lahko odkritih 2^52 (~=10^15) različnih skupin kart. Pa da še ni vseeno kje so.

Kombinatorična eksplozija je tukaj ... pregrozna.

Ampak sama smer pa JE taprava.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Bottom line, prišel sem do tega - no, potem ko je uni Marc G. povpraševal po točno istem - da bi šlo edinole na sledeči način:

- program, ki je optimalen reševalec Klondiketa

- mora biti zmožen odigrati par milijonov partij na sekundo

- mora znati začeti od vsake zatečene pozicije naprej

- verjetnost, da je naša pozicija sestavljiva, je empirično dobljena zadeva. Program je od tu naprej preigral milijon možnih, naključnih pozicij, konsistentnih z videnim na ekranu. Delež dobljenih je enak verjetnosti da zmagamo.

No, zdej lahko kdo naredi.
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

ouch...

kolk operacij bi rabil za eno celo "random" igro?
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

Računam da 1000. Potem bi se nekako izšlo.

Če pa 10 krat več, bi sampliral na 100 tisoč testiranjih, namesto na milijon.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Recimo, da bi uspelo spraviti en premik karte v eno operacijo in ena primerjava, če karto lahko premaknemo na enega izmed 11 oz. 10 možnih pozicij, tudi eno operacijo. Potem bi imeli vsaj 24 * 11 (24 kart na začetku na kupčku, 4 + 7 možnih mest za premik) + 7 * 10 (7 kart na stolpcih, 10 možnih mest za premik) operacij v primeru, da nobene karte iz kupčka ne bi mogli nikamor premakniti. 334+ operacij torej po res super optimistični napovedi in še to le v primeru, da bi bila igra res totalno nerešljiva.

Bolj realno bi bile vsaj 3 operacije na eno primerjanje, s tem da računamo na dobro jump predikcijo procesorja, ki bi večinoma pravilno napovedala, da karte ne moremo premakniti. Ampak moramo potem prišteti okoli 20-30 ( koliko je že dolg cevovod v pentiumu 4?) operacija (izgubljeni cikli) vsakič, ko karto dejansko uspemo nekam premakniti.

Če še ostanemo pri oceni 1 operacije na eno primerjavo dobimo v igri, kjer bi premaknili le eno karto: (23*11)[karte ki jih ne moremo premakniti] + 5 + 1[karta ki jo premaknemo, a bomo v povprečju pregledali vsaj 5 mest, preden ji najdemo ustrezno pozicijo] + 30[false jump prediction penalty] + 7*10[isto kot zgoraj] + 23*11[še enkrat pregledamo celoten kupček] = 253 + 36 + 70 + 253 = 612+ operacij.

Tako da je 1000 operacij na igro absolutno preoptimistična ocena. Tudi 10000 mi je še vedno slišati too good to be true, zaradi vseh dodatnih stvari, ki jih je treba izvesti, pa jih tu še nisem upošteval.

Ok, sem moral malo zatežiti z matematiko 8-) Upam le da se nisem kje preveč zmotil.

Thomas ::

Meni se pa zdi 1000 operacij na partijo kar realno. Ponavadi sklikaš kakšno polovico kart ven, recimo 30. Težko, da je potrebno dosti več kot 15 operacij na karto, da najde svoje mesto v kupčku. in še petnajst za tiste ki ostanejo samo odkrite in 0 za tiste, ki jih nikoli ne vidiš.
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

no ja, sej v biti ni važno, bo pač sample rate manjši -> manjša natačnost verjetnosti. ko bo cpu hitrejši bo pač rezutat boljši... le glejte da bo MT ready :)
Abnormal behavior of abnormal brain makes me normal...

Gundolf ::

Poskusi za začetek koliko časa traja random mešanje tistih 30 kart, ki jih ne vidiš

Gundolf ::

Se pa drugače strinjam, da je to čisto dober sistem za reševanje problema. Samo še kako optimizacijo bi bilo treba izbrskati kje, pa bi bilo realno rešljivo.

Thomas ::

Zanemarljivo. Veš zakaj?

Ker najprej (za prvi test) jih kar pobereš iz zaporednega kupa in nafilaš. Za naslednji test samo dvema random zamenjaš mesti.

In tako naprej, skozi milijon testov. 2 milijona psevdorandom števil, če imaš nek pameten algoritem - tisočinka sekunde!
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

a začnemo?

enum CardType
{
   ctAce       = 1,
   ctTwo       = 2,
   ctThree     = 3,
   ctFour      = 4,
   ctFive      = 5,
   ctSix       = 6,
   ctSeven     = 7,
   ctEight     = 8,
   ctNine      = 9,
   ctTen       = 10,
   ctJack      = 11,
   ctQueen     = 12,
   ctKing      = 13
}

enum CardColor
{
   ccHearts    = 1,
   ccSpades    = 2,
   ccDiamonds  = 3,
   ccClubs     = 4
}
Abnormal behavior of abnormal brain makes me normal...

Zgodovina sprememb…

  • spremenil: Vesoljc ()

Thomas ::

ccDiamonds

ccClubs

:))
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Zakaj si že končal, vesojc?

Thomas, to sicer v principu deluje, vendar se mi dozdeva da bi tako preizkal en lokalen del prostora rešitev, kar pa nikoli ni dobro, če hočeš najti približek verjetnosti za rešljivost celotnega prostora.

CCfly ::

Ni imel inspiracije za preostali dve barvi kart :)
@Thomas: In kako boš na tak način imel napako le 1% ?
"My goodness, we forgot generics!" -- Danny Kalev

Thomas ::

Ne Gundolf. Vsaka informacija o začetni situaciji se po par deset swapih čisto izgubi.

Tako recimo nazadnje deluje tudi mešamje šopa kart. Korelacija med začetnim stanjem in po 100 swapih je nična.

Ta metoda je OKay, trust me!
Man muss immer generalisieren - Carl Jacobi

Thomas ::

CCfly,

Jah, kako verjetno je, da se pri milijon poskusih razlikuje relativna frekvenca od verjetnosti za več kot 0,01?

V sili vzameš Bayesa ali atomsko bombo ... in ni hudič, da ne dobiš rezultata.
Man muss immer generalisieren - Carl Jacobi

Vesoljc ::

gremo naprej, podatkovne strukture:

navadni array-i? ali ksni vektorji?
Abnormal behavior of abnormal brain makes me normal...

OwcA ::

Vektorji (ali nekaj sorodnega), da bo manj kode (za razna razporejanja in sortiranja lahko uporabimo kar STL).
Otroška radovednost - gonilo napredka.

Vesoljc ::

ok vector it is...
imamo torej začetni kup, velikost je kolk že?

imamo 4 kupe za nalaganje in pa kolk že, sedem igralnih kupov?
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

Za začetek predlagam 12 arrayev, ki so na igralni plošči. Samo imena? :\
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Hm, ne bi rekel da tako deluje mešanje kart. Navsezadnje ne zamenjaš le mesta dvema kartama in razdeliš znova. Če že daš kupček na pol in zamenjaš mesto polovicama je to veliko drugače. Pri običajnem mešanju pa to storiš še večkrat in z bolj drobno razdelitvijo kot le na polovice.

Kombinacij za 30 kart je 2.6 e+32. Z menjanjem dveh kart se ti po tem prostoru po polžje plaziš. Res je da po nekaj 10 menjavah verjetno ne bo več vidne korelacije s prvotno razporeditvijo, a obiskan del prostora bo še kako lokalen.

Če pa želiš metodo popraviti in premešati več kart naenkrat si kmalu spet pri randomiziranju vseh kart, ki jih ne vidiš. Verjetno pa bi se zaradi dovolj velikega števila ponovitev dalo najti srednjo pot a popolnoma zanemariti pomembnosti dobrega mešanja ne gre. Če bi bili zelo natančni bi prezirali tudi pseudo random generatorje a v te vode raje ne pojdimo.

Gundolf ::

Odpri windows pasjanso vesoljc :)

24 na kupčku
7 na spodnjih stolpcih, desni ima eno karto več od levega, prvi ima le eno karto.

statične tabele char-ov, ker želimo majhne strukture in lokalnost dostopov (ce ta spil ne gre cel v cache potem pa tud ne vem kaj gre)

Owca: tudi navadne arraye lahko urejamo & sortiramo s STLjem.

Zgodovina sprememb…

  • spremenil: Gundolf ()

Vesoljc ::

ne smem špilat igrc :))

statične tabele? joj no, kdo bo pa potem VSE te algoritme napisal? ;)

imena?
a) PopingDeck?
b) StartDeck?
c) DeckFromWhichWePullCards ?

:P
Abnormal behavior of abnormal brain makes me normal...

Thomas ::

UPS - kupov je 13!¨Še tisti ob talonu, kamor odlagamo.

Najprej je treba narest modul DEALER ki zna:

- razporediti 52 kart random po kupu in za spodnjih sedem prikazati zgornje.

- odgovarjati na sledeče akcije:

- move(n,m) (prenesi karto iz kupa n na kup m)

- obrni karto na kupu n, če ni obrnjena

- undo last move & reset undo option

- ignorirati napačne ukaze

- (sam zložiti do konca)

To rabmo.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

Coolska imena, samo še pretvori jih v kratice da bodo krajša in predvsem bolj razumljiva ;)

Poskusi z
deck
stack
destination ali destinationStack

Thomas ::

> obiskan del prostora bo še kako lokalen.

Ne, ne bo. Obiskane točke v tem prostoru bodo dovolj random.

Ne moreš rečt, da igramo karte s specifičnimi razdelitvami, ker prodajajo samo posortane.

Nikoli tudi ne naredimo v njih milijon swapov, so prej zanič. Pa ni lokalnisti tukaj nobene.

Ne se bat.
Man muss immer generalisieren - Carl Jacobi

Gundolf ::

No sej, če bo vesoljc mal pohitel >:D bomo lahko sprobal.

OwcA ::

Še nekaj trivijalne kode ;) 

class Card {
public:
  enum Type
  {
     ctAce       = 1,
     ctTwo       = 2,
     ctThree     = 3,
     ctFour      = 4,
     ctFive      = 5,
     ctSix       = 6,
     ctSeven     = 7,
     ctEight     = 8,
     ctNine      = 9,
     ctTen       = 10,
     ctJack      = 11,
     ctQueen     = 12,
     ctKing      = 13
  } m_type;

  enum Color
  {
     ccHearts    = 1,
     ccSpades    = 2,
     ccDiamonds  = 3,
     ccClubs     = 4
  } m_color;

  bool m_faceUp = false;

  Card(Type type, Color color) : m_type(type), m_color(color) {}
};


@Gundolf: imaš prav, ampak še vseeno je bolj srčkano. ;)
Otroška radovednost - gonilo napredka.

Zgodovina sprememb…

  • spremenilo: OwcA ()

Vesoljc ::

vesoljcu se nič ne mudi 8-)

ma tud druge zadeve za kodirat ;)
Abnormal behavior of abnormal brain makes me normal...

Gundolf ::

Uh, samo ne shranjevat podatka a kako je karta obrnjena. Itak vemo da je najvišja karta face-up. Na destination kupčkih rabimo vedt le najvišjo številko karte, ki je odložena na posameznem (ze prej dolocimo kater kupček bo za katero barvo) Za deck rabimo veded le katere karte so v njem in katera je trenutno na vrhu. Zato tudi ne rabimo funkcije "obrni karto na kupu n" (in ti thomas bi rad resil eno igro v 1000 ciklih?). Da ne omenjam da nimam pojma zakaj rabimo undo?

Za se malo optimizacije:
union {
   struct {
      char m_color;
      char m_type;
   };
   int m_colorAndType;
};


tako imamo krajšo strukturo, kopiramo lahko le en int (bolje od dveh intov ali dveh charov) pa se primerjat, ali gre karta na dolocen kupcek, bi se dal vse z istim intom.
«
1
2

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Hearthstone: Heroes of Warcraft (strani: 1 2 3 4 … 15 16 17 18 )

Oddelek: Igre		887113330 (7295) Jerry000
»

Blackjack v igralnici

Oddelek: Loža		256071 (1521) #000000
»

Verjetnosti pri kartah (strani: 1 2 3 4 … 10 11 12 13 )

Oddelek: Znanost in tehnologija		60444139 (25346) itak37
»

Šnops igra za PC ?

Oddelek: Igre		4725895 (20713) BOCo.
»

Karte remi pravila

Oddelek: Loža		774007 (71454) cbr2005

Več podobnih tem