[algoritme] bordspel doorrekenen

[liquid_ice]

Een vriend van me heeft een bordspel gemaakt en ik wil de computer gebruiken om de hoogst mogelijke score te berekenen.

Het bordspel bestaat uit 3 bij 6 vlakken en op elk vlak kan je een kaart neerleggen.
Er zijn 31 soorten kaarten.
regel: elke kaart mag maar 1 keer voorkomen op het speelbord

Het aantal punten dat je krijgt is afhankelijk van de kaart en z'n buren (alle 8 zijn buren).
Ik heb een mooi stukje code dat vrij vlot het aantal punten van een ingevuld bord kan berekenen, dat is het probleem niet en dat gaat ook vrij snel.

Het probleem zit um in het aantal mogelijke bord combinaties.
als ik geen rekening hou met dat elke kaart maar 1 keer mag voorkomen heb ik 40^18 = +/- 7 * 10 ^ 26 mogelijkheden. M'n laptop is redelijk modern, maar ik ben bang dat de aarde eerder vergaat dan dat ik alle opties heb doorgerekent.
(Nu na 1 nacht brute-force rekenen ben ik bij vlak 7 van de 18, schiet niet op)

De vraag is dus hoe dat ik dit slimmer kan aanpakken om de maximum score te vinden zonder een leven lang te hoeven rekenen met m'n laptop.

[Dido]

Sowieso heb je natuurlijk maar 31! / 13! mogelijkheden.
(31 mogelijkheden voor vlka 1, 30 voor vlak 2, 29 voor vlak 3, etc.

Nu is 8.22 * 10²⁴ nog steeds geen fijn aantal mogelijkheden om te brute-forcen, maarhet zijn er toch een factor 5.30*10¹⁶ minder

[ Voor 3% gewijzigd door Dido op 25-02-2013 09:23 ]

[omgwtfbbq]

Als je wat tijd overhebt zou je kunnen kijken of je een parallel algoritme kan implementeren met behulp van CUDA. Zo kun je enkele duizenden mogelijkheden op hetzelfde moment uitrekenen wat, zeker bij een getal als 6,29 * 10^21 een behoorlijke speedup zal generen, mits goed geimplementeerd.

Just a heads up

[Zoijar]

Paden prunen. Als je al weet dat een bepaalde kaart leggen sowieso een lagere score geeft, dan hoef je dat hele pad niet te doen.

cuda etc is leuk als je het al slim doet. Het heeft geen nut om van 100.000 jaar rekenen naar 1000 jaar rekenen te gaan.

[ Voor 32% gewijzigd door Zoijar op 25-02-2013 09:59 ]

[Soultaker]

Parallelle implementaties helpen natuurlijk geen zier als je tien ordes van grootte verwijderd bent van een werkend algoritme. Je kunt dan beter iets slims doen, zoals Zoijar ook voorstelt.

Ik denk dat je met dynamic programming al een heel eind kunt komen. Als je drie rijen en zes kolommon hebt, en alleen directe buren relevant zijn, dan kun je het bord van links naar rechts gaan opvullen. Voor elke positie is alleen relevant: welke kaart de meest rechtse van elke rij is, en welke kaarten je verder al gebruikt hebt.

Dat levert maximaal 31³ × (31! / 15! / (31 - 15)!) = 8,953,392,949,245 mogelijkheden op (maar in de praktijk nog een stuk minder) en dat lijkt me een aantal dat redelijkerwijs door te rekenen is op gewone hardware.

[Zoijar]

Soultaker schreef op maandag 25 februari 2013 @ 10:01:
Als je drie rijen en zes kolommon hebt, en alleen directe buren relevant zijn, dan kun je het bord van links naar rechts gaan opvullen.

Alleen mag elke kaart maar een keer voorkomen. Je kan dus niet een stukje bord optimaliseren onafhankelijk van de rest. Hoewel je er wel misschien iets mee kan...

[Soultaker]

Dat zeg ik ook: je houdt de rechter drie kaarten bij én een ongeordende verzameling van eerder gebruikte kaarten (of nog bruikbare kaarten, wat natuurlijk op hetzelfde neerkomt). De ordening van die kaarten is niet meer relevant omdat je ze toch niet meer met andere kaarten kunt combineren (zeg ik op basis van de nogal vage beschrijving van hoe het spelletje werkt).

[liquid_ice]

Ik ben niet zeker of dat ik je idee begrijp.

Ik snap dat je idee werkt met een 'deck' van kaarten en als je er eentje gebruikt hebt, dat je dan minder kaarten in het deck hebt zitten en dus ook minder opties.

Wat ik niet zo goed snap is het bijhouden van de rechter 3 kaarten waar je het over hebt.

<< Als je info mist vanuit het spel voor het algoritme moet je het even specifiek vragen, mogelijk heb ik wat ervaringsblindheid omdat ik het al behoorlijk ken >>

[ Voor 21% gewijzigd door liquid_ice op 25-02-2013 11:30 ]

[Soultaker]

Misschien moet je even in detail uitleggen hoe de puntentelling precies werkt, dan kan ik het concreter uitleggen.

(Overigens zie ik al dat ik een foutje had gemaakt: je hebt het in de TS over “alle acht buren” van een kaart, en dan moet je de laatste vier gebruikte kaarten bijhouden, niet de laatste drie zoals ik suggereerde. Dat maakt de boel wel iets complexer, maar niet heel veel.)

[liquid_ice]

Soultaker schreef op maandag 25 februari 2013 @ 12:57:
Misschien moet je even in detail uitleggen hoe de puntentelling precies werkt, dan kan ik het concreter uitleggen.

(Overigens zie ik al dat ik een foutje had gemaakt: je hebt het in de TS over “alle acht buren” van een kaart, en dan moet je de laatste vier gebruikte kaarten bijhouden, niet de laatste drie zoals ik suggereerde. Dat maakt de boel wel iets complexer, maar niet heel veel.)

Die extra info komt vanavond.

De fout is niet aan jou kant, ik heb later (stiekempjes) de TS aangepast

[Kaw]

Wat ik begrijp is dat de volgorde van de kaarten rondom de kaart niet uitmaakt. Hierdoor kun je een hele reeks kaartcombinaties overslaan.
Stel je hebt:
1 2 3
4 5 6
7 8 9

Dat zou dan hetzelfde zijn als:
9 8 7
6 5 4
3 2 1

Maar ook als:
6 3 1
2 5 9
8 4 7

Etc.
Waar het nummertje een kaart voorsteld en nummer 5 de kaart is die in het midden ligt en berekent wordt aan de hand van de buren.

Wanneer je recursief door alle mogelijkheden heen loopt, dan zou je alle bordopstellingen kunnen skippen die in andere vorm al eerder zou zijn voorgekomen. Instinctief is meteen te zien dat je een bepaalde dek kaarten kan spiegelen of kantelen en dezelfde score zal krijgen. Die situaties moet je op 1 of andere manier skippen. Hoe je dat recursief doet weet ik zo niet. Er zijn teveel combinaties om met een hashtabel te werken. Maar als je kritisch er naar kijkt, dan denk ik dat je wel een oplossing vind om het recursief meteen goed te doen.

[liquid_ice]

Klopt, de volgorde maakt inderdaad niet uit voor de centerkaart.

uit jou voorbeeld:
Stel je hebt:
1 2 3 A
4 5 6 B
7 8 9 C

Levert dan WEL weer een ander totaal score dan:
9 8 7 A
6 5 4 B
3 2 1 C

Maar onderstaand is wel hetzelfde als de eerste:
C 9 8 7
B 6 5 4
A 3 2 1

[Kaw]

liquid_ice schreef op maandag 25 februari 2013 @ 13:57:
Klopt, de volgorde maakt inderdaad niet uit voor de centerkaart.

uit jou voorbeeld:
Stel je hebt:
1 2 3 A
4 5 6 B
7 8 9 C

Levert dan WEL weer een ander totaal score dan:
9 8 7 A
6 5 4 B
3 2 1 C

Maar onderstaand is wel hetzelfde als de eerste:
C 9 8 7
B 6 5 4
A 3 2 1

Dat is waar. Misschien is het dan niet op 'centercard'-niveau te knijpen, maar je zou de verschillende centercard-configuraties en hun bijbehorende scores wellicht wel kunnen cachen!
Daarnaast maak ik in deze situaties meestal een aantal shortcuts om dingen te speeden. Stel dat je de kaartcombinaties cached, dan weet je de maximale score voor elke kaart. Stel je moet nog 10 kaarten, maar zelfs als alle nieuwe kaarten de maximaal mogelijke score zouden hebben, dan zou er geen nieuwe highscore komen -> skip dit pad in de recursieve boom. Vaak kan dit nog veel intelligenter en met het halen van nieuwe highscores versnel je het proces steeds meer totdat je heel heel heel veel paden kan overslaan en je sneller dan verwacht het antwoord vind.

[timjuan]

Kun je de regels voor de puntentelling geven? Lijkt me een wiskundig vraagstuk, niet zozeer een programmeer probleem. Er leiden meerdere wegen naar Rome, alle mogelijkheden uitproberen brengt je ook bij de oplossing, maar vraag me af of het de snelste manier is. In elk geval een leuk puzzeltje!

[pedorus]

Afhankelijk van de regels lijkt me brute-forcen ook een beetje overkill. Waarschijnlijk is er wel iets slimmers mogelijk.

Soultaker schreef op maandag 25 februari 2013 @ 10:01:
Dat levert maximaal 31³ × (31! / 15! / (31 - 15)!) = 8,953,392,949,245 mogelijkheden op (maar in de praktijk nog een stuk minder) en dat lijkt me een aantal dat redelijkerwijs door te rekenen is op gewone hardware.

Ik neem aan dat je hier situaties/states bedoel, en geen mogelijkheden. 31³ is dan nogal een overschatting: de kaarten kunnen niet hergebruikt worden tussen die 3, en alleen de positie van de middelste kaart maakt uit vanwege symmetrie. Ook verderop kun je die 3 kaarten niet hergebruiken. Lijkt me dus 31*(30*29/2)*(28!/15!/(28-15!). Het totaal wordt dan 504,907,527,600. In de stap ervoor zijn het er 410,237,366,175. Tik- en denkfouten voorbehouden Dat kun je theoretisch wel doorrekenen op "gewone hardware", maar ik denk dat je dan toch al snel een 3TB-schijf als trage cache aan het gebruiken bent... Meer iets voor een clustertje

[Soultaker]

Ik gaf een bovengrens inderdaad, maar sowieso moet de boel nog even heroverwogen worden als liquid_ice de exacte regels post. Ik denk dat met een combinatie van dynamic programming met pruning (zoals Zoijar al voorstelde) de boel wel behapbaar moet zijn.

[liquid_ice]

Ik ben heel benieuwd naar jullie oplossingsrichting, moet mezelf even wat beter gaan inlezen in dynamic programming en pruning.

Iemand anders kwam nog met het idee van een evolutionair of genetisch algoritme, wat is jullie idee om dat in te zetten tegen dit probleem?

[Bosmonster]

Ik heb hier niet superveel kaas van gegeten, maar moet je werkelijk alle mogelijkheden brute forcen om "de hoogst mogelijke score" te achterhalen? Het gaat hier maar om 1 waarde uiteindelijk en volgens mij moet dat ook wel slimmer op te lossen zijn dan domweg alle mogelijkheden uit te werken.

Maar goed, dat hangt volgens mij erg van het puntensysteem af.

[ Voor 10% gewijzigd door Bosmonster op 25-02-2013 17:21 ]

[pedorus]

liquid_ice schreef op maandag 25 februari 2013 @ 17:20:
Iemand anders kwam nog met het idee van een evolutionair of genetisch algoritme, wat is jullie idee om dat in te zetten tegen dit probleem?

Het probleem daarvan is dat je wel een goede oplossing zult vinden, maar nooit zeker weet of dit ook daadwerkelijk het maximum is.

[liquid_ice]

Ik heb even overlegd in hoeverre ik deze info mag delen, maar het mag gewoon...

<< Als hier nog onduidelijkheden in zitten stel de vragen maar gewoon >>

Spelregels:

Het doel van het spel is om zoveel mogelijk verbindingen te maken. Iedere verbinding levert 1 punt op.
Leg kaarten uit je hand neer in het speelveld, aansluitend aan de
bestaande kaarten.

Er onstaat een verbinding wanneer de nieuwe kaart iets nodig heeft wat de
aanliggende kaarten leveren of andersom; als de nieuwe kaart iets levert
wat de aanliggende kaarten nodig hebben.

Op de kaart staat met iconen aangegeven wat de kaart nodig heeft en wat de kaart levert.

Verbindingen kunnen worden gemaakt met kaarten die zowel recht naast of
boven elkaar liggen, als schuin van elkaar liggen.

De iconen kunnen vaker gebruikt worden en dus niet opraken.

Details:

Iedere kaart heeft maximaal 4 inputs (iconen die aangeven wat de kaart nodig heeft) en 4 outputs (iconen die aangeven wat de kaart levert). Er zijn 11 verschillende iconen die als input/output kunnen dienen. Er zijn 31 verschillende soorten kaarten.

Speelveld:

code:

A B C D E F
G H I J K L
M N O P Q R

Voorbeeld rekenwijze voor vol veld:

Begin bij A

Kaart A ligt naast kaart B, G en H.
Voor iedere input van kaart A die B, G of H als output heeft krijg je een punt.

Als B en G beide een output leveren aan dezelfde input van A levert dat 2 punten op.
Als B 2 outputs levert die matchen met 2 inputs van A levert dat ook 2 punten op.
Ga door naar B

Etc.

(Kaart H kan een verbinding maken met: A,B, C, G, I, M, N en O.)


Tel dus voor iedere kaart alleen de verbindingen die door de input iconen van deze kaart zijn ontstaan. Als je namelijk ook de verbindingen die door de output iconen van die kaart zijn ontstaan meetelt, tel je al de verbindingen dubbel.

[Soultaker]

Het klopt dus dat een kaart met één icoon in principe negen omliggende kaarten van invoer kan voorzien?

Dan zou ik m'n aanpak iets veranderen en nog steeds alleen de laatste vier kaarten bijhouden (plus een verzameling van nog ongebruikte kaarten), behalve dat je van die vier kaarten moet bijhouden welke inputs nog ongematcht zijn. Zodra je een nieuwe kaart neerlegt match je direct alle beschikbare inputs én outputs met omliggende kaarten.

Het aantal toestanden wordt dan groter dan voorheen ingeschat omdat je behalve 31 soorten kaarten gedeeltelijk gematchte inputs hebt. De details hangen een beetje af van het gemiddelde aantal iconen per kaart (waarvan ik vermoed dat het niet belachelijk hoog is).

[liquid_ice]

Het klopt dus dat een kaart met één icoon in principe negen omliggende kaarten van invoer kan voorzien?

Een kaart met 1 output icoon kan alle 8 de omliggende kaarten van invoer voorzien.

[pedorus]

Ik vermoed dat geheugengrootte toch snel problemen gaat geven. Nog wat observaties:

Als je het probleem opdeelt in links en rechts, dan zijn er voor een gedeelte 5,080,338,900 relevante mogelijkheden (31*30*29/2*(28!/6!/(28-6)!)). Op goede hardware past dat wel in het geheugen. Dan is het een kwestie van (sorteren en) matchen. Alternatief zou je kunnen werken met groepjes van 9 kaarten zonder volgorde, hiervan zijn er maar 20,160,075, en dat past zeker in het geheugen. Als je geluk hebt sorteer je deze, en vind je snel een passende match als je bovenin kijkt. Wel is het probleem daarmee dat de kanten niet altijd passen. Opvallend is ook dat het al dan niet aanwezig zijn van 31 kaarten mooi in 32 bits (+1 bonus) past (of 2 GB geheugenspace bij maximaal 255 aan waarde).

Met die 11 resources zie ik niet direct veel perspectief, denk dat een tabelletje van 31*31 voor de kaarten net zo effectief is. (Of mag je maar 1 keer matchen op een input?)

Verder; als het met zekerheid vinden van het absolute maximum niet zo belangrijk is, zie ik meer mogelijkheden. Gezien de vorm van het probleem bijv. simulated annealing met verwisseling kaarten, al dan niet parallel (genoemde evolutionaire algoritmes). In theorie geeft dat onder voorwaarden ook gegarandeerd het maximum.

[Kaw]

liquid_ice schreef op maandag 25 februari 2013 @ 20:10:
Ik heb even overlegd in hoeverre ik deze info mag delen, maar het mag gewoon...

Wil je dan in abstractie ook de kaarten + iconen publiseren op het forum? Maken we er een korte battle van om de hoogste score te vinden
Vind ik wel leuk...
Dus niet letterlijk de kaarten, maar gewoon kaart 1: icoon 2,5,6
Kaart 2: icoon 2, 3, 7
Etc.

[ Voor 11% gewijzigd door Kaw op 26-02-2013 07:59 ]

[Big Womly]

pedorus schreef op maandag 25 februari 2013 @ 22:56:
Ik vermoed dat geheugengrootte toch snel problemen gaat geven. Nog wat observaties:

Dat mag geen probleem zijn. Worst case scenario wordt er geswapt, of moet TS zelf zaken naar de HDD gaan schrijven.

Ik heb dit topic niet volledig doorgelezen, maar wat je nog kan doen om je algoritme te optimaliseren is enkele heuristieken inbouwen.
Zo kan je bijvoorbeeld bij poker stellen dat wanneer 1 speler een Royal Flush heeft, geen enkele andere speler nog kan winnen, ongeacht hun kaarten. Het is dan ook zinloos om alle mogelijke situaties van de andere spelers te gaan evalueren.

[timjuan]

De vraag was wat het maximale aantal punten is dat je kunt halen.. Is het dan noodzakelijk om alle mogelijke combinaties door te rekenen?

Je hebt het hoogst mogelijk aantal punten als alle kaarten al hun buren van input voorzien en andersom. De kaarten liggen in een 6 x 3 vorm op tafel. De 4 kaarten op de hoeken hebben dus 3 buren. De 10 kaarten aan de randen hebben 5 buren en de 4 kaarten in het midden hebben 8 buren.

We tellen van elke kaart alleen de punten van de input. We tellen niet de output naar andere kaarten omdat we dan dubbel tellen. Het maximaal aantal punten is dan dus:

4 kaarten met 3 inputs = 12 punten
10 kaarten met 5 inputs = 50 punten
4 kaarten met 8 inputs = 32 punten
Totaal = 94 punten

Maar... Dat betekent wel dat die 31 kaarten samen de mogelijkheid moeten bieden om te zorgen dat alle inputs en outputs matchen... We moeten dus weten welke iconen er op alle 31 kaarten staan.

[Coocoocachoo]

Big Womly schreef op dinsdag 26 februari 2013 @ 10:26:
[...]
Zo kan je bijvoorbeeld bij poker stellen dat wanneer 1 speler een Royal Flush heeft, geen enkele andere speler nog kan winnen, ongeacht hun kaarten. Het is dan ook zinloos om alle mogelijke situaties van de andere spelers te gaan evalueren.

Semi-offtopic, maar dat is natuurlijk alleen zo bij community-card-poker (Texas Hold'Em bijv.) anders kan een ander net zo goed een Royal Flush krijgen en dus samen de winst delen.

timjuan schreef op dinsdag 26 februari 2013 @ 11:11:
De vraag was wat het maximale aantal punten is dat je kunt halen.. Is het dan noodzakelijk om alle mogelijke combinaties door te rekenen?

Je hebt het hoogst mogelijk aantal punten als alle kaarten al hun buren van input voorzien en andersom. De kaarten liggen in een 6 x 3 vorm op tafel. De 4 kaarten op de hoeken hebben dus 3 buren. De 10 kaarten aan de randen hebben 5 buren en de 4 kaarten in het midden hebben 8 buren.

We tellen van elke kaart alleen de punten van de input. We tellen niet de output naar andere kaarten omdat we dan dubbel tellen. Het maximaal aantal punten is dan dus:

4 kaarten met 3 inputs = 12 punten
10 kaarten met 5 inputs = 50 punten
4 kaarten met 8 inputs = 32 punten
Totaal = 94 punten

Maar... Dat betekent wel dat die 31 kaarten samen de mogelijkheid moeten bieden om te zorgen dat alle inputs en outputs matchen... We moeten dus weten welke iconen er op alle 31 kaarten staan.

Als ik het goed begrijp kan een kaart 4 punten opleveren aan zijn buurman door precies dezelfde outputs te hebben als de inputs van de buurman.

Dus als kaart A als input bloemetje, bijtje, vogel en kikker heeft en als output schaar, potlood, gum en vulpen en kaart B als input schaar, potlood, gum en lineaal en als output bloemetje, bijtje, vogel en olifant dan leveren die naast elkaar 6 punten op.

Het maximale aantal punten in dat geval zou dan dus 94*4 zijn, maar dan zou elke kaart hetzelfde zijn en dezelfde input als output hebben, wat het nogal een saai spel zou maken

[ Voor 14% gewijzigd door Coocoocachoo op 26-02-2013 12:00 ]

[timjuan]

Als ik het goed begrijp kan een kaart 4 punten opleveren aan zijn buurman door precies dezelfde outputs te hebben als de inputs van de buurman.

Dus als kaart A als input bloemetje, bijtje, vogel en kikker heeft en als output schaar, potlood, gum en vulpen en kaart B als input schaar, potlood, gum en lineaal en als output bloemetje, bijtje, vogel en olifant dan leveren die naast elkaar 6 punten op.

Het maximale aantal punten in dat geval zou dan dus 94*4 zijn, maar dan zou elke kaart hetzelfde zijn en dezelfde input als output hebben, wat het nogal een saai spel zou maken

Ja, ik denk dat je gelijk hebt. Mijn berekening hield geen rekening met 4 input en 4 outputs en het maximale aantal punten is in theorie dus 94*4, maar dan wordt het een heel saai spelletje.

Het vinden van de combinatie die de maximale punten oplevert is afhankelijk van de kaarten en de iconen die daarop staan. Aangezien werd aangegeven maximaal 4 inputs en maximaal 4 outputs neem ik aan dat er ook kaarten zijn met bijvoorbeeld 2 inputs en 1 output.

[Coocoocachoo]

timjuan schreef op dinsdag 26 februari 2013 @ 12:20:
[...]


Ja, ik denk dat je gelijk hebt. Mijn berekening hield geen rekening met 4 input en 4 outputs en het maximale aantal punten is in theorie dus 94*4, maar dan wordt het een heel saai spelletje.

Het vinden van de combinatie die de maximale punten oplevert is afhankelijk van de kaarten en de iconen die daarop staan. Aangezien werd aangegeven maximaal 4 inputs en maximaal 4 outputs neem ik aan dat er ook kaarten zijn met bijvoorbeeld 2 inputs en 1 output.

Zo begrijp ik het inderdaad ook.

En dat maakt het volgens mij ook aardig lastig om te prunen, want een bepaalde kaart aanleggen die op dat moment niet de hoogste waarde oplevert kan uiteindelijk wel de hoogste score opleveren. Ik zie niet zo in hoe je bepaalde paden vantevoren als slechter kan bestempelen zonder ze door te rekenen.
En alleen maar de gespiegelde en 180 graden gedraaide borden weghalen levert niet echt veel winst op.

Maar gelukkig ben ik geen expert, dus zullen anderen vast met slimme oplossingen komen om wel berekeningen te beperken. En daar ben ik dan ook erg benieuwd naar om weer wat te leren

[Kaw]

Ik hoop dat de kaarten hier neergezet worden. Het lijkt me leuk om er even mee aan de slag te gaan.

[liquid_ice]

@Kaw, je hebt geluk.

De spelmaker is bereid om de gegevens te publiceren.
Ik wil nog even contact opnemen met een van de modjes om hier een mooie vorm aan te geven.
Er moet iets van regeltjes komen om het netjes te laten verlopen.

Het vinden van de combinatie die de maximale punten oplevert is afhankelijk van de kaarten en de iconen die daarop staan. Aangezien werd aangegeven maximaal 4 inputs en maximaal 4 outputs neem ik aan dat er ook kaarten zijn met bijvoorbeeld 2 inputs en 1 output.

Klopt, volgens mij zijn er zelfs kaarten met 1 output en geen inputs (of anderom)

volgen mij is 4 * 94 = 376 inderdaad het theoretische maximum punten aantal als ALLE inputs en outputs op elkaar aansluiten, maar dat staan de kaarten niet toe, haha

Coocoocachoo schreef op dinsdag 26 februari 2013 @ 12:37:
[...]
En dat maakt het volgens mij ook aardig lastig om te prunen, want een bepaalde kaart aanleggen die op dat moment niet de hoogste waarde oplevert kan uiteindelijk wel de hoogste score opleveren. Ik zie niet zo in hoe je bepaalde paden vantevoren als slechter kan bestempelen zonder ze door te rekenen.

Je zou in een 3 * 3 opstelling een kaart kunnen vastzetten in het midden en dan berekenen wat de hoogste kaartscore is van die ene centercard.
als je dat doet met alle kaarten heb je een tabel met de max score per kaart.

Als je dan een stuk pad hebt weet je welke kaarten verbruikt zijn, welke score je nu al hebt en welke er nog over zijn. Ook weet je de huidige topscore natuurlijk.

Stel dat je pad nog 4 plaatsen vrij heeft, dan kan je kijken naar de 4 nog ongebruikte kaarten met de hoogste theoretische score.

als je zelfs met die hoogste theoretische score geen highscore kan behalen, kan je al stoppen.
Met 31 kaarten en 4 vrije plaatsen heb je 923.521 mogelijke combinaties overgeslagen in dit voorbeeld, bij 5 plaatsen skip je al 28 miljoen opties

[ Voor 59% gewijzigd door liquid_ice op 27-02-2013 13:50 ]

[Kaw]

liquid_ice schreef op woensdag 27 februari 2013 @ 10:56:
@Kaw, je hebt geluk.

De spelmaker is bereid om de gegevens te publiceren.

Mooi!
Nou, even afwachten dus...

[Soultaker]

Bump! Doe 's data posten.

[pedorus]

Data:

card 1 - in: 4, 8, 7, 9 out: 11, 5, 6
card 2 - in:  out: 7, 9, 1, 5
card 3 - in: 10, 4 out: 
card 4 - in: 6, 3, 1, 4 out: 
card 5 - in: 9, 1, 10, 2 out: 
card 6 - in: 9, 2, 7, 10 out: 
card 7 - in: 10, 2 out: 7
card 8 - in: 7 out: 
card 9 - in: 2, 3, 1 out: 
card 10 - in: 8, 10 out: 6
card 11 - in: 10 out: 9, 7, 3, 11
card 12 - in: 2, 9 out: 1
card 13 - in:  out: 9, 3, 7, 6
card 14 - in: 9, 3, 8 out: 
card 15 - in: 6 out: 10, 3, 5, 7
card 16 - in: 4, 10, 8 out: 6, 1, 5
card 17 - in: 5, 2, 9 out: 3, 11
card 18 - in: 4, 9, 5 out: 8
card 19 - in: 4, 1, 7 out: 2, 9, 11, 5
card 20 - in: 6 out: 10, 8, 11
card 21 - in: 11, 10, 2 out: 
card 22 - in: 3, 8, 7, 9 out: 4
card 23 - in: 11 out: 8, 3, 5, 1
card 24 - in:  out: 10, 4, 5, 11
card 25 - in: 3, 2, 4, 7 out: 
card 26 - in: 6, 2, 7 out: 4
card 27 - in: 10, 11, 6 out: 2, 9
card 28 - in: 1, 10, 3 out: 6, 7
card 29 - in: 3, 2 out: 7, 6, 9
card 30 - in: 2, 8 out: 3
card 31 - in: 7, 10, 2, 8 out: 3, 4

[Soultaker]

Hoe kom jij daar nu weer aan?!

edit:
Ik kom voorlopig op 26, bijvoorbeeld met deze kaarten:

 12  1 10 15 29  2
 11 19 27 20 28  6
 31 22 17  5 21 26

... maar ik kan niet bewijzen of dat per se het maximum is.

[ Voor 93% gewijzigd door Soultaker op 01-03-2013 23:38 ]

[liquid_ice]

Sorry dat het eventjes duurt.

Ik ben samen met de spelmaker en tweakers de contest vorm aan het geven.
Zo wordt het eerlijk en ook een contest met een gesloten eind.

Het spel bevat daarnaast nog een paar regels die nog niet benoemd zijn in dit topic

De dataset van pedorus is volgens mij zelf verzonnen, maar voldoet aan de feiten die in dit topic gegeven zijn.

[pedorus]

Soultaker schreef op vrijdag 01 maart 2013 @ 23:06:
Hoe kom jij daar nu weer aan?!

offtopic:
Ik wilde boss hibernation voorkomen

edit:
Ik kom voorlopig op 26, bijvoorbeeld met deze kaarten:

 12  1 10 15 29  2
 11 19 27 20 28  6
 31 22 17  5 21 26

... maar ik kan niet bewijzen of dat per se het maximum is.

Vreemd, dat lijkt mij een score van 59 op te leveren. http://jsfiddle.net/hbAGE/2

Ik ga er in mijn berekening van uit dat een output meerdere keren mag matchen (net als een input). Op zich is dat niet heel lastig te veranderen.

[liquid_ice]

Een losse kaart levert nooi punten op:

code:

12

score : 0

Als er nu een kaart naast wordt gelegd:

code:

12 1

score : 0
kaart 12 levert niets dat kaart 1 wilt hebben en andersom ook niet.

Als er nu een kaart naast wordt gelegd:

code:

12 1
11

score : 2
Kaart 11 kan zijn input 9 leveren ZOWEL aan kaart 12 als aan kaart 1.

Als er nu een kaart naast wordt gelegd:

code:

12 1
11 19

score : 7
Kaart 19 kan:
- input 1 krijgen van kaart 12
- input 7 krijgen van kaart 11
- output 2 leveren aan kaart 12
- output 9 leveren aan zowel kaart 1 als aan kaart 12

en zo verder

[Soultaker]

pedorus schreef op zaterdag 02 maart 2013 @ 12:29:

offtopic:
Ik wilde boss hibernation voorkomen

Psh, ik ben toch geen PHB!

Vreemd, dat lijkt mij een score van 59 op te leveren. http://jsfiddle.net/hbAGE/

Jij telt elke match los; ik ga er vanuit dat een input van een kaart maar één keer voldaan kan worden (en dan een punt oplevert). De outputs hebben deze restrictie niet voor zover ik weet.

[liquid_ice]

Zoals mijn voorbeeld hierboven weergeeft.

Per nieuw gelegde kaart (kaart A), kan elke input van A matchen met maximaal 1 output PER AANGRENZENDE KAART. Maximaal 8 punten per input dus.

Elke output van kaart A kan ook matchen met 1 input PER AANGRENZENDE KAART. Maximaal 8 punten per output dus.

De meest ideale nieuw gelegde kaart (met 8 aangrenzende buren) kan dus maximaal 64 punten opleveren.

LET OP:
Ga niet dubbel tellen:
Als kaart A zijn output aan de input van kaart B heeft geleverd en daarvoor punten heeft geleverd, dan moet je bij kaart B niet NOG EENS deze zelfde verbinding aan punten gaan tellen.

code:

function NumberOfSetBits(i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Zou je deze functie wat kunnen toelichten ?

[ Voor 17% gewijzigd door liquid_ice op 02-03-2013 20:34 ]

[.oisyn]

Da's een trucje om zonder een loop het aantal bits te tellen die op 1 staan. Er zijn tal van manieren om dat te doen. Dit is een van de wat minder intuitieve manieren, maar eentje die makkelijker te begrijpen is, is:

C:

unsigned numbits(unsigned i)
{
    i = (i & 0x55555555) + ((i >> 1) & 0x55555555); // 0x55555555 == 0b01010...0101
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333); // 0x33333333 == 0b00110011..00110011
    i = (i & 0x0f0f0f0f) + ((i >> 4) & 0x0f0f0f0f); // 0x0f0f0f0f == 0b00001111..00001111
    i = (i & 0x00ff00ff) + ((i >> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >> 16) & 0x0000ffff);
    return i;
}

De eerste regel telt alle even bits bij alle oneven bits op. Elk groepje van 2 bits in het resultaat geeft dan aan hoeveel bits er gezamelijk in dat groepje op 1 stonden. De volgende regels doen feitelijk precies hetzelfde, maar dan in groepjes van 4, 8, 16 en 32. Uiteindelijk hou je het aantal op 1 gezette bits in het gehele getal over.

[pedorus]

liquid_ice schreef op zaterdag 02 maart 2013 @ 15:53:
Als er nu een kaart naast wordt gelegd:

code:

12 1
11

score : 2
Kaart 11 kan zijn input 9 leveren ZOWEL aan kaart 12 als aan kaart 1.

Als ik dit blokje kopieer in de jsfiddle, dan krijg ik 3. Ik vermoed dat je hier de verbinding van resource 7 tussen kaart 1 en 11 bent vergeten te tellen? (En wat de totale score voor het blokje

code:

12 1
11 19

op 8 brengt)

liquid_ice schreef op zaterdag 02 maart 2013 @ 17:52:
Zou je deze functie wat kunnen toelichten ?

Zie hierboven Maar hij is o.a. te vinden op http://stackoverflow.com/...-bits-in-a-32-bit-integer
Comment neergezet in de source.

Wat ik dus doe is: Ik sla de resources die een bepaalde kaart als input of output heeft op in een int als bitarray. Resources 1-11 zijn bit 1-11 (en bit 0 is ongebruikt). De getallen in de inResources en outResources array zijn daarom met bijv. de windows calculator om te zetten in de bijbehorende resources. Dit maakt het mogelijk om met 'and' snel te kijken welke resources overeen komen, en met deze functie kun je bepalen hoeveel bits gezet zijn, dus wat de score wordt. Overigens kun je deze functie optimaler kiezen zolang er maar 11 resources en max. 4 kaarten zijn, zie SO-link. Maar eigenlijk is de 31x31 matrix vullen voor de waardes van verbindingen tussen kaarten waarschijnlijk toch sneller.

Soultaker schreef op zaterdag 02 maart 2013 @ 17:35:
Jij telt elke match los; ik ga er vanuit dat een input van een kaart maar één keer voldaan kan worden (en dan een punt oplevert). De outputs hebben deze restrictie niet voor zover ik weet.

Dan kom ik trouwens op 35 - http://jsfiddle.net/bnhsJ/ . Best makkelijk ergens een foutje hierin te maken (of zoals ik eerst had handmatig fout te tellen en dan op zoek te gaan naar de 'bug'). Maar dat lijkt me dus niet de goede methode.

Ik dacht dit eerst ook, maar dat sloot niet aan bij:

liquid_ice schreef op woensdag 27 februari 2013 @ 10:56:
volgen mij is 4 * 94 = 376 inderdaad het theoretische maximum punten aantal als ALLE inputs en outputs op elkaar aansluiten, maar dat staan de kaarten niet toe, haha

Dat is dus 4*8*4(midden)+10*5*4(kant)+4*3*4(hoek). Overigens ga ik er van uit dat een kaart geen inputs heeft die ook outputs zijn (hoewel het niet echt lastig is om de code daarvoor aan te passen). Dat zorgt gelijk ook voor een afname van het maximum naar 216.

[Soultaker]

liquid_ice schreef op zaterdag 02 maart 2013 @ 17:52:
Per nieuw gelegde kaart (kaart A), kan elke input van A matchen met maximaal 1 output PER AANGRENZENDE KAART. Maximaal 8 punten per input dus.

Aha, dat had ik blijkbaar verkeerd geinterpreteerd. Eigenlijk maakt dat het probleem alleen maar makkelijker omdat je niet hoeft bij te houden welke inputs er wel/niet voldaan zijn halverwege een oplossing.

pedorus schreef op zondag 03 maart 2013 @ 01:24:
Dan kom ik trouwens op 35 - http://jsfiddle.net/bnhsJ/ . Best makkelijk ergens een foutje hierin te maken (of zoals ik eerst had handmatig fout te tellen en dan op zoek te gaan naar de 'bug'). Maar dat lijkt me dus niet de goede methode.

Goed punt, dat was een implementatiefout (voor wie zich verveelt: zoek de fout ) nog los van de interpretatiefout. Ik zal m'n code eens reviseren.

[pedorus]

spoiler:

Het blijkt maar weer dat r en c erg op elkaar lijken..

Ik zie eventuele resultaten wel tegemoet Overigens vermoed ik dat het vinden van het maximum niet al te moeilijk is, het bewijzen dat dit echt het maximum is, is wel wat lastiger.

[Kaw]

liquid_ice schreef op zaterdag 02 maart 2013 @ 07:38:
Sorry dat het eventjes duurt.

Heb je een inschatting hoe lang het nog duurt?
Check dit topic koortsachtig elk uur...

[Soultaker]

Je kunt je altijd uitleven op pedorus' data set (ik zit ondertussen op 88, maar ik heb weinig succes met prunen).

[Kaw]

Soultaker schreef op maandag 04 maart 2013 @ 21:41:
Je kunt je altijd uitleven op pedorus' data set (ik zit ondertussen op 88, maar ik heb weinig succes met prunen).

Na 10 miljoen iteraties zat ik op 70 punten en na 1 miljard iteraties op 71 punten. Ik vermoed dat er veel mogelijke maximale combinaties zijn en dat je al snel aan een plafond zit, maar ik kan het mis hebben...
88 punten is cool, maar volgens mij zit er ergens een bugje in je proggie? Wat ik begrijp is dat je 1 punt krijgt voor elke card waarbij de input icon voorkomt in een naburig output icon. Dan kom ik op 71 punten uit.

Edit: sprak voor mijn beurt. Zit inmiddels op 73 punten.

[ Voor 4% gewijzigd door Kaw op 05-03-2013 14:23 ]

[pedorus]

Nee, dat is per combinatie van kaarten, niet per kaart. Een input kan dus meerdere keren matchen. Vergelijk even je scores met de scores uit http://jsfiddle.net/hbAGE/2/

[Kaw]

pedorus schreef op dinsdag 05 maart 2013 @ 14:26:
Nee, dat is per combinatie van kaarten, niet per kaart. Een input kan dus meerdere keren matchen. Vergelijk even je scores met de scores uit http://jsfiddle.net/hbAGE/2/

Ja, een input icon kan maximaal 8 punten opleveren omdat 8 omliggende kaarten allen die als output hebben. (of je ziet het precies andersom, maar dat maakt niet uit)
Een kaart kan 4 input icons hebben, dus theoretisch 32 punten als maximum score.

Edit: getest, gaat goed. Zelfde score.

[ Voor 3% gewijzigd door Kaw op 05-03-2013 14:56 ]

[Soultaker]

Kaw schreef op dinsdag 05 maart 2013 @ 14:05:
88 punten is cool, maar volgens mij zit er ergens een bugje in je proggie?

Volgens Pedorus' jsFiddle ding klopt 'ie wel.

(Dat jsFiddle ziet er handig uit — die moet ik onthouden!)

[Kaw]

Soultaker schreef op dinsdag 05 maart 2013 @ 15:10:
[...]

Volgens Pedorus' jsFiddle ding klopt 'ie wel.

(Dat jsFiddle ziet er handig uit — die moet ik onthouden!)

Dan heb ik nog huiswerk

[.oisyn]

Soultaker schreef op dinsdag 05 maart 2013 @ 15:10:
(Dat jsFiddle ziet er handig uit — die moet ik onthouden!)

Dan vind je liveworkspace.org vast ook wel aardig

[Kaw]

.oisyn schreef op dinsdag 05 maart 2013 @ 15:11:
[...]
Dan vind je liveworkspace.org vast ook wel aardig

Cool!
Hoever kun je gaan op liveworkspace.org?

Edit: gevonden. Je hebt een sandbox van 1mb om mee te spelen en je werkt met de GCC compiler onder Linux.

[ Voor 19% gewijzigd door Kaw op 05-03-2013 15:42 ]

[liquid_ice]

Soultaker schreef op maandag 04 maart 2013 @ 21:41:
Je kunt je altijd uitleven op pedorus' data set (ik zit ondertussen op 88, maar ik heb weinig succes met prunen).

waardoor komt het dat je weinig success hebt met prunen?

Ps : Ik heb met de spel maker een Openingspost voor de 'officiele' contest gemaakt, deze is nu onderweg naar Tweakers voor een review en ik hoop deze week nog online.

[Soultaker]

Als je er een contest van wil maken moet ik misschien niet te veel implementatie-details prijsgeven, maar vooruit:

liquid_ice schreef op dinsdag 05 maart 2013 @ 16:25:
waardoor komt het dat je weinig success hebt met prunen?

Ik gebruik nu een A*-achtige aanpak in de hoop een absoluut optimale oplossing te vinden (en daarmee ook te kunnen bewijzen dat mijn gevonden oplossing het beste is). Dit vereist een permissible heuristic die de maximale score die op een half-ingevuld bord te halen is niet onderschat, anders kan ik niet garanderen dat ik alleen suboptimale oplossing afkap.

Maar het is lastig om een heuristische inschatting te maken die enigzins dicht bij de daadwerkelijke oplossing ligt, wat nodig is om een groot aantal suboptimale deeloplossingen af te kunnen kappen. Momenteel krijg ik dus niet genoeg posities afgekapt om alle relevante toestanden door te rekenen.

[Kaw]

Heb inmiddels mijn algoritme multithreaded gemaakt, maar bedenk me net een behoorlijke performance-improvement op mijn oude algoritme. Dat moet maar een andere keer komen.

[Kaw]

Bump!
En? Is er al een wedstrijd?

[Kaw]

Kaw schreef op maandag 11 maart 2013 @ 08:34:
Bump!
En? Is er al een wedstrijd?

[liquid_ice]

De wedstrijd start moet nog gereviewd worden voor de mods. Daarna kunnen we vrij snel van start.

[Kaw]

Kom op mods!

[Creepy]

We're working on it

[Kaw]

Creepy schreef op vrijdag 15 maart 2013 @ 10:24:
We're working on it

Goed om te horen.

[Anoniem: 303530]

Waarom duurt het nu wéér zo lang

Ik kom momenteel op 87, met een algoritme waarvan de laatste stap in een kwartiertje in de trein in elkaar is gezet... Het draaien duurt ongeveer 5 minuten (niet getimed).

Ik heb wel hetzelfde probleem als Soultaker: het is niet te bewijzen dat het de beste oplossing is. Ik kan hem wel zo aanpassen dat dat bewijs wel geleverd kan worden, maar dan vermoed ik dat de tijdscomplexiteit door het plafond gaat. In tegenstelling tot Soultaker gebruik ik geen A* achtige search, maar iets wat meer weg heeft van bruteforce.

Edit; na 5½ uur rekenen poept mij algoritme ook de score 88 uit.

Hij berekent overigens verschrikkelijk veel dubbel, dus het kan een stuk sneller dan dat. Binnen een half uurtje zou tot de mogelijkheden moeten behoren.

[ Voor 16% gewijzigd door Anoniem: 303530 op 29-03-2013 15:07 ]

[Anoniem: 303530]

Victory.

Ik heb mijn algoritme wat aangepast. En heb wederom de score 88 gevonden. Maar deze keer kan ik wel bewijzen dat deze score de beste is. Ik weet alleen niet hoeveel het er zijn en welke, want dat sla ik niet op

Het duurt ongeveer een uur of 6 om alles door te rekenen.

Kunnen de mods even zeggen of er nog wel of geen contest komt? Dan kan ik mijn algoritme en wiskundige proof toelichten.


Edit: volgens mij is dit de enige oplossing:

code:

16 20 27 17 19 18
31 28 1 29 22 2
25 15 26 13 6 11

...en transformaties daarvan. Runtime: tegenwoordig 125 minuten met een grotendeels singlethreaded algoritme.

[ Voor 21% gewijzigd door Anoniem: 303530 op 07-04-2013 21:57 ]

[Creepy]

De contest komt er. Als het goed is deze week. Let wel: wij (de mods) organiseren de boel niet. De toestemming is gegeven. Ik help zelf mee met het runnen van de entries op mijn systeem, maar that's it. Er wordt aan gewerkt, maar er is nu 1 iemand ff met vakantie. Als hij terug is wordt als het goed is het topic geopend.

[.oisyn]

Wat voor GPU heeft jouw systeem?

[Creepy]

Die vraag had ik al verwacht ja. Evenals welke CPU erin zit em hoeveel geheugen er in mijn systeem zit. Ik zit nog te twijfelen om dat te gaan noemen. Als ik dat al doe, dan pas op het moment dat de contest echt van start gaat. Laten we het er voor nu maar op houden dat op mijn systeem prima te gamen is

[Bolukan]

Binnen 1 seconde rekent excel voor me uit dat de score maximaal 102 is.
Edit: 96 (= 12/6 * 47 + 2)

[ Voor 22% gewijzigd door Bolukan op 09-04-2013 23:29 ]

[Kaw]

Bolukan schreef op dinsdag 09 april 2013 @ 22:59:
Binnen 1 seconde rekent excel voor me uit dat de score maximaal 102 is.
Edit: 96 (= 12/6 * 47 + 2)

Zo, jij bent echt goed!

[curvemod]

Bolukan schreef op dinsdag 09 april 2013 @ 22:59:
Binnen 1 seconde rekent excel voor me uit dat de score maximaal 102 is.
Edit: 96 (= 12/6 * 47 + 2)

Jeetje, dat je daar Excel voor moet gebruiken en dat het dan nog mis gaat

[Bolukan]

Het ging niet mis, het was een nog scherpere benadering.
(102 = 13/6 * 47)

En het is meer de plafondscore waar de echte maximale score nooit boven zal komen; te gebruiken door het zoek-algoritme voor de echte maximale score ...

(Hmmm, ja de originele post is een beetje verwarrend daarin)

En ik ben benieuwd of Soultaker voor zijn A* een soortgelijke eerste benadering maakt.

[ Voor 16% gewijzigd door Bolukan op 11-04-2013 21:56 ]

[Kaw]

Creepy schreef op zondag 07 april 2013 @ 21:54:
[..] Als het goed is deze week. [..]

Contest, contest, waar ben je?

[Anoniem: 303530]

Hij staat online.
[Programming Contest 5] Tuintopia

De opzet is iets anders dan in dit topic. Daarom kan ik mijn huidige algoritme wel weg gooien
Wat ik nu heb, dus wat gebaseerd is op het spel wat in dit topic is beschreven met het dataset van pedrus, lukt het mijn algoritme om in minder dan 3 minuten (singlethreaded, sandy bridge CPU) te verifiëren dat 88 de maximale score is. Ik verwacht dat dat met relatief weinig moeite tot de helft te reduceren is, maar dan is de grens wel bereikt.

[ Voor 2% gewijzigd door RobIII op 16-04-2013 22:11 . Reden: Kleine correctie v.w.b. contest nummer :P ]