[es] - Pomoć oko algoritma za kontra-tablić

TheBatA
Miljan Komatina
Senior software developer, QUANTUM -
AutoMARKET
Beograd

Član broj: 25309
Poruke: 64
*.adsl.sezampro.yu.

Sajt: www.AutoMARKET.rs

Profil

Pomoć oko algoritma za kontra-tablić

^{04.05.2005. u 19:37 - pre 230 meseci}

E, na šta sve može muka da natera čoveka...

elem, moja lepša polovina obožava da igra kontra tablić, dok ja i nisam neki zaljubljenik, t.j. volim da igram samo ako pored sebe imam dovoljno piva i još par ljudi koji će igru da učine zanimljivijom. Da bih se rešio stomaka koji sam dobio od piva, ja reših da napravim kontra tablić na kompjuteru.

Sve je u početku išlo glatko, napravim ti ja sve potrebne klase, povežem ih nekako, ali onda dođem do problema oko nošenja karata.

evo kako to sve izgleda
Igru radim u C#.
Od klasa u programu imam Karta i Igrač.
špil sam napravio kao niz karata(logično zar ne :) )

igrač poseduje niz od 6 karata, gde se čuvaju njegove karte.

karte koje su na talonu se čuvaju u nizu talon.

Pitanje:
kako napraraviti algoritam koji će, kada igrač izbaci kartu, vratiti niz karata koje treba da ponese (naravno, ako ima šta)?

malo objašnjenje, za one koji nisu igrali kontra tablić:
pravila su ista kao kod običnog tablića, samo što treba nositi što manje karata.prioritet prilikom nošenja imaju kombinacije koje u sebi imaju najviše štihova, a zatim one sa najviše karata.Takođe ne zaboraviti da 10 karo vredi 2 štiha a "mala dvojka" jedan...

pomagajte ljudi, dok nisam postao pravi alkos :)

Ashes to ashes - dust to dust. Zejtin to ulje - mast to mast.

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Pomo� oko algoritma za kontra-tabli�

^{05.05.2005. u 08:55 - pre 230 meseci}

Navedi par primera. Recimo sta igrac mora da nosi ako na:

[3 4 5 6] igra 9 (opcije su (3,6) i (4,5))

[2+ 4 10+ J] igra K (opcije su (2+,J) i (4,10+))

[2 3 4 5 6] igra A (opcije su (2,3,6) i (2,4,5))

Da li mora sve da pokupi, ili moze da bira samo jednu opciju?

Odgovor na temu

toroman
Srećko Toroman
www.wowd.com
Beograd / Banja Luka

Član broj: 52673
Poruke: 159
*.dialup.blic.net.

Sajt: toroman.wordpress.com

Profil

Re: Pomoć oko algoritma za kontra-tablić

^{05.05.2005. u 16:36 - pre 230 meseci}

Nisam siguran jer nisam nikad to igrao, a nisi ni odgovorio na Cvetanovićev post, ali predpostavljam da se ovdje radi o dinamičkom programiranju ili nekoj rekurzivnoj funkciji.

Tebi dakle treba algoritam koji matetmatički rečeno, u skupu brojeva q = {a1, a2 ... an} pronalazi poskupove brojeva ciji zbir elemenata iznosi X. Jel tako? Pa za ovakvu stvar, rekurzija je mozda najbolja ... Malo pojasni pa cu ti rado pomoci :)

Programeri su odgovorili na Hamletovo pitanje "Biti il ne biti?" :
0x2B | ~0x2B = 0xFF
(kao ono - ff - teško pitanje!)

Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.nat-pool.nsad.sbb.co.yu.

Profil

Re: Pomoć oko algoritma za kontra-tablić

^{05.05.2005. u 18:30 - pre 230 meseci}

Taj problem sto si ti toromane naveo je klasicno dinamicko programiranje. Svodi se na problem ranca (knapsack).

Don’t do drugs, sleep deprivation is better.

Odgovor na temu

TheBatA
Miljan Komatina
Senior software developer, QUANTUM -
AutoMARKET
Beograd

Član broj: 25309
Poruke: 64
*.adsl.sezampro.yu.

Sajt: www.AutoMARKET.rs

Profil

Re: Pomoć oko algoritma za kontra-tablić

^{06.05.2005. u 16:07 - pre 230 meseci}

evo da objasnim ceo tok igre.
Špil klasično ima 52 karte. na početku se prvo izbacuju 4 random karte na talon, a zatim se deli po 6 karata svakom igraču. Prilikom izbacivanja karata na talon se, naravno, može desiti i da budu sve 4 karte iste, pa treba i na to obratiti pažnju.
Cilj igre je nositi što manje karata. To podrazumeva prvenstveno što manje štihova, a zatim što manje karata, pošto na kraju igrač koji je odneo više karata, dobija i "tri na karte". Karta A ima vrednost 1 ili 11, u zavisnosti od potrebe.
primeri:
talon=[10 A] karta=A, igrač bi nosio obe karte, pošto im je zbir 11.
talon=[A 2] karta=3, kombinacija=[A 2] pošto u ovom slučaju A vredi 1.

prilikom nošenja se nosi sve što izbačena karta može da ponese, ali tako da se prvenstveno odnese najveći broj štihova, a zatim se obraća pažnja na broj karata.
primer:
talon=[2 2 4 10] karta=14, kombinacija=[10 2 2].

kada izbace svi igrači karte koje imaju, dele se preostale karte.
Na kraju,kada nema više karata za deljenje, igrač koji je poslednji nosio nosi i preostale karte sa talona.
To bi ukratko bilo to.
Još malo primera...

npr. ako se na talonu nalazi:

[ 2+ 3 4 5 6 7 8 9 10+ A 12 13 14]

a izbaci igrač npr kartu 14, onda mora da ponese
[(14) (13 A) (12 2) (10+ 3) (9 5) (8 6)]

u slučaju da postoje dve kombinacije, npr. kao što je naveo mihajlo:

[2 3 4 5 6] igra A (opcije su (2,3,6) i (2,4,5))

nebitno je koja će se kombinacija nositi, pošto obe imaju jednak broj karata. Jedino da je umesto 2 bilo 2+ onda bi morala da se nosi kombinacija sa 2+.

...

Kao što rekoh, špil predstavlja niz karata. Svaka karta ima atribute: broj (ispisan na karti) i vrednost( t.j. broj štihova, npr. karte od 2-9 imaju vrednost 0 sa izuzetkom male dvojke, 2+, koja vredi 1. karte od 10 - 14 imaju vrednost 1, opet sa izuzetkom 10+, koja vredi 2.).
Moja ideja je da napravim matricu sa svim mogućim kombinacijama i da iz nje na kraju izvučem onu koja odgovara gorenavedenom kriterijumu. ali, problem mi je kako da pronađem sve kombinacije?

Ashes to ashes - dust to dust. Zejtin to ulje - mast to mast.

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Pomoć oko algoritma za kontra-tablić

^{06.05.2005. u 17:28 - pre 230 meseci}

Pošto se asevi različito interpretiraju algoritam treba sprovesti za sve različite kombinacije aseva na tabli, tj. ako ima N aseva na tabli onda sprovodiš algoritam N+1 puta. Za tri asa sve različite kombinacije su (1 1 1), (1 1 11), (1 11 11) i (11 11 11).

Algoritam traga za maksimalnim skupovima koji zadovoljavaju uslov da sve karte iz skupa mogu da se nose, i da je skup podskup skupa "talon".

Svaki put kad algoritam naleti na novi skup koji je bolji od starog (po štihovima i po kartama) onda briše sve skupove koje je zapamtio i pamti ovaj novi skup, a kao trenutnu maksimalnu vrednost pamti vrednost novog skupa.

Vrednost skupa je uređeni par (S, K), gde je S broj štihova, a K broj karata. Svaki put kad algoritam naleti na novi skup koji ima istu vrednost kao i trenutna maksimalna vrednost onda pamtimo i taj skup (tj. pamtimo sve skupove sa maksimalnom vrednošću).

Novi skup mora po svojim elementima da se razlikuje od svih trenutno zapamćenih skupova. Elementi skupa su brojevi 2 - 10, A, J, Q, K, 2+ i 10+, ima ih ukupno 15, a prvih 13 mogu da se pojavljuju više od jednom u skupu.

Kad završimo sa pretragom možemo da imamo nula, jedan ili više zapamćenih skupova. Nula znači da se karta baca na tablu, jedan znači da kompjuter odmah može da nosi karte iz skupa, a više znači da moramo da pitamo korisnika koji skup želi da nosi.

E, sad, još samo da se napravi taj algoritam...

Odgovor na temu

TheBatA
Miljan Komatina
Senior software developer, QUANTUM -
AutoMARKET
Beograd

Član broj: 25309
Poruke: 64
*.adsl.sezampro.yu.

Sajt: www.AutoMARKET.rs

Profil

Re: Pomoć oko algoritma za kontra-tablić

^{06.05.2005. u 18:44 - pre 230 meseci}

samo još algoritam...
Imao sam jednu ideju, a to je bilo da napravim više prolaza kroz špil, koji je prethodno sortiran po broju štihova, tako da tražim prvu kartu koja je <= izbačenoj karti. u slučaju da je jednaka, dodaje se u niz (ili matricu). Ako je manja, traži se prva karta koja je <= razlici bačene i pronađene, itd., dok rezultat pretrage ne bude 0.
Pretpostavljam da se ovo radi pomoću neke rekurzivne funkcije, ali ja nisam koristio rekurziju u dosadašnjem radu, pa bi mi malo koda dobro došlo...

Ovo nije baš najbolje rešenje, pošto se ovakvim algoritmom ne odabiraju najbolje kombinacije, ali u nekim slučajevima može da koristi.
Primer:

talon=[10+ 14 13 12 A 2+ 9 8 7 6 5 4 3]
karta=13

prethodnim algoritmom se dobija
kombinacija=[ (10+ A 2+) (13) (9 4) (8 5) (7 6)]. ovde se dobija: štihova 5, karata 10.

bolja kombinacija=[ (10+ 3) (13) (12 A) (2+ 7 4) (8 5)]. štihova 6, karata 10.

Predpostavljam da bi algoritam za ovo bilo nešto kao:
Pronalazi se u sortiranom nizu prva karta koja je <= bačenoj. U slučaju da je manja, kreće se od kraja niza i traži se prva koja je <= razlici, itd.

Ovo sam smislio za ovakav talon, nisam još isprobao kako radi sa drugačijim talonom...
Ovo je moja ideja, sugestije, ispravke, kritike a naročito pohvale

su dobrodošle.

Ashes to ashes - dust to dust. Zejtin to ulje - mast to mast.

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Pomoć oko algoritma za kontra-tablić

^{09.05.2005. u 08:48 - pre 230 meseci}

Algoritam ne treba da se zaustavi kad nađe jedno rešenje, nego mora da proveri sva moguća rešenja, prvo zato što možda ima i bolje, a drugo da bi ponudio igraču sve opcije najboljeg rešenja.

Uzgred, možda je bolje da se talon sortira po vrednosti, umesto po broju štihova, tj.

talon=[14 13 12 11 10+ 9 8 7 6 5 4 3 2+] u prvom prolazu, i
talon=[14 13 12 10+ 9 8 7 6 5 4 3 2+ 1] u drugom prolazu.

Odgovor na temu