(Warszawa) Regularne spotkanie testowe - Monsoon Group

[Karol Madaj]

Jacku nie muszę chyba pisać, że już teraz Twoje dokonania są imponujące. Chciałbym mieć połowę takiej wiedzy jak Twoja i Michała.
Dzięki za analizę!

A więc okazuje się chyba, że napisanie programu nie jest takie proste jak się z początku wydawało. Dziś testowałem JZT? na młodzieży z poprawczaka i szukanie błedów najbardziej ich pasjonowało (mało który rozpoznawał na zdjęciu Wałęsę ). Znaleźli jeszcze kilka błędnych połączeń. Po naniesieniu tego na moja "mapę" okazało się, że zepsucie wynika z ludzkich błędów przy wklepywaniu danych, a nie błędu systemu czego się najbardziej obawiałem. Wygląda na to, że po jeszcze kilku (kilkunastu) godzianch pracy będzie ok. Metoda ręczna jednak oszczędza prawie 100 tyś. lat .

Moja siatka ma na jednej osi numer karty (1-133) a na drugiej numer symbolu (1-133), następnie siatka podzielona jest na kwadraty 12 na 12 i w ramach tych kwadratów przeprowadzone są ukośne linie wyznaczające odpowiednie punkty. Sztuka polega na odpowiednim kącie ukosnej linii i rozpoczęciu linii w odpowiednim miejscu. Trudno mi to wytłumaczyć spróbuję wrzucic zdjęcie. Czasem metody starożytne sie sprawdzają.

[Jan Madejski]

Udało mi się też wymyślić dość szybką metodę sprawdzania czy dana karta "pasuje" do listy wcześniej wygenerowanych

To jest dość proste:(...)

Dużo mniej kosztowne sprawdzanie kart: przy zapisie binarnym karty (gdzie każdy bit odpowiada jednemu symbolowi) wykonujemy koniunkcję binarną z pozostałymi kartami - tam, gdzie wyjdzie inna wartość, niż 1 wspólny bit, zwracamy błąd.
Ale skoro Karol już ma rozwiązanie, to dalsze rozważania chyba są niepotrzebne

[zephyr]

Fajne zadanie na OI czy inny konkurs algorytmiczny

Dla informatyków (tylko):

Spoiler:

Te 2 tablice do szybkiego testu wyglądają naprawdę dobrze, mocno ograniczają przestrzeń.
IMO jakiś constraint satisfaction tree search na nich oparty byłby dość szybki i znajdował optymalny podział, brakuje tylko dobrej heurezy na wybór gałęzi (pewnie coś w stylu używania liczb o najmniejszej ilości możliwych opcji byłoby dobre) i jakiegoś sposobu na odróżnianie praktycznie takich samych opcji (izomorficznych z dokładnością do indeksów)

W skrócie chodzi o przejście drzewa możliwych wyborów kart. Każdy węzeł drzewa to dodanie nowej karty, jego synowie to karty które można dodać. Naiwna implementacja DFSa to brute force - przechodzi wszystkie opcje. Z powyższymi tablicami można sprawdzać po każdej dodanej karcie i odcinać jak się nie da dodać bez psucia warunku. Dodatkowo warto skleić synów którzy są tacy sami z dokładnością do permutacji indeksów, bo to też sporo wytnie. Jak się znajdzie jakieś rozwiązania odcina się wszystkie które na pewno nie będą lepsze (tu się przyda oszacowanie na bazie zapełnienia tablicy zakazów)

Nie zajmuje za dużo pamięci bo przechowuje się tylko aktualnie analizowaną ścieżkę, najwygodniej jedną funkcją rekurencyjną. [jak zajmuje za dużo lista wszytskich możliwych kart do dodania można spróbować generować je po jednej, ale to bardzo utrudnia szukanie identycznych i wybór lepszej opcji wcześniej]
[edit]Hmm jednak lista nowych kart jest dużo za duża i trzeba to przechodzić sprytniej... ale dalej mam wrażenie że da się coś z tego wycisnąć filtrując na etapie generowania następnej opcji[/edit]

najlepszyDotad = -inf
SzukajNajlepszy(układ_kart, tablice){
...noweUklady = generuj(układ_kart, tablice) // dodaje 1 nową kartę na kazdy mozliwy sposob
...noweUklady = wyrzucIdentyczne(noweUklady)
...noweUklady = posortujOdNajlepszego(noweUklady)

...if (noweUklady is empty){
......najlepszyDotad = max(najlepszyDotad , val(układ_kart))
...} else
...for ( u in noweUklady){
......if (mozliwyMax(u) > najleszyDotad)
.........SzukajNajlepszy(u, tabliceDlaU)
...}
}

to na pewno sprawdzi wszystkie opcje, ale szybkie cięcia i dobra kolejność powinny ograniczyć czas, przy okazji można wypisywać każde znalezienie lepszego rozwiązania, co sprawia że nawet jak przejście całości będzie zbyt długie wypisze się jakiś sensowny wynik

jakiegoś bardziej trickowego super sposobu nie widzę, ale nie jestem za dobry z trudnych zadań algorytmicznych, z mojego doświadczenia mogą okazać się banalne po zauważeniu jakiejś zależności albo NP bo akurat ma się pecha mimo że wyglądało fajnie

[stalker]

Fajne zadanie na OI czy inny konkurs algorytmiczny

Zupełnie niezależnie od tego, że Karol znalazł sposób na rozwiązanie problemu, można by zorganizować konkurs na gamesfanatic — myślę, że IPN mógłby ufundować kilka gier dla najlepszej implementacji przy okazji byłoby to reklamą gry

[piotrsmu]

przy zalozeniu ze kazdy symol wystepuje na conajmiej 2 kartach mona uzyskac k*(k-1)+1 kart uzywajac tyle samo symboli. bez tegoo zalozeni da sie uzyskac nioraniczona liczbe kart

[Jan Madejski]

bez tegoo zalozeni da sie uzyskac nioraniczona liczbe kart

Ano właśnie - bez pewnych założeń może wyjść model matematycznie idealny, ale zupełnie niegrywalny Z punktu widzenia designera najlepszy jest zestaw, w którym każdy symbol występuje w talii taką samą liczbę razy (maksymalizowanie liczby kart jest drugorzędne).

[ja_n]

Z punktu widzenia designera najlepszy jest zestaw, w którym każdy symbol występuje w talii taką samą liczbę razy (maksymalizowanie liczby kart jest drugorzędne).

Nie zgodzę się, trzeba pamiętać o założeniach dla gry. Karol ma do dyspozycji 133 symbole. Znalezienie więcej jest trudne, nie da się tego zwielokrotnić, zresztą nie ma sensu - celem gry jest nauczenie się ich przez uczniów w klasie. Nie ma sensu robić gry, której nie da się nauczyć - chodzi o to, żeby nauczenie się symboli pomagało w wygrywaniu, to gra edukacyjna. Z drugiej strony chodzi też o to, żeby jedną talią można było obdzielić całą klasę, która będzie rozgrywać pojedynki 1 na 1 w ławkach. Więc tak, chodzi tu o maksymalizację liczby kart przy ograniczeniu zbioru ikon. Wydaje mi się, że wyrównywanie częstotliwości występowania symboli ma mniejsze znaczenie - oczywiście lepiej unikać drastycznych rozbieżności, ale nie ma sensu dążyć do pełnej równości.

[zephyr]

@piotr,

mógłbyś rozwinąć tą wypowiedź, bo albo ja nie zrobiłem jakiejś obserwacji która bardzo to upraszcza/nie kojarzę jakiejś teorii albo ty nie rozumiesz problemu

chodzi o stworzenie algorytmu który wydajnie generuje karty o tej własności że każde 2 mają dokładnie jeden wspólny symbol

3 symbole wg twojego wzoru to 7 kart... powodzenia

po 1 symbolu na karcie da się zrobić 1 kartę
po 2 da się zrobić 3: 12 13 23
po 3 da się zrobić 1 kartę

[edit] dobra, coś mi się porąbało, ale dalej nie rozumiem skąd to k(k-1)+1

[Jan Madejski]

po 3 da się zrobić 1 kartę

Dla 3 kart ze wzoru wychodzi 7 symboli i 7 kart: 123 145 167 246 257 347 356
EDIT - ech, już niepotrzebnie...

Wydaje mi się, że wyrównywanie częstotliwości występowania symboli ma mniejsze znaczenie - oczywiście lepiej unikać drastycznych rozbieżności, ale nie ma sensu dążyć do pełnej równości.

Nie Jeśli w grze można zastosować elegancki balans, to powinno się go stosować. Przechył w stronę kilku symboli zmniejsza wartość edukacyjną i prawdopodobieństwo, że wszyscy uczestnicy gry będą mieli równe szanse na wygraną. Przypuśćmy, że jakiś symbol - dajmy na to Złoty Banan - występuje w talii najrzadziej. Dostaję kartę, która go zawiera, symbol mi się podoba i zaczynam wypatrywać do niego pary. Mam jej nie znaleźć, bo designer schrzanił sprawę? Jeśli grą chcemy obdzielić całą klasę, to należy przynieść więcej talii, które i tak drogie pewnie nie będą. Albo, mimo wszystko, zwiększyć liczbę symboli (a co za tym idzie możliwych kart).

[MichalStajszczak]

Fajne zadanie na OI czy inny konkurs algorytmiczny

Myślę, że na taki konkurs to jest zadanie zbyt proste, bo udało mi się zapisać algorytm w kilkunastu linijkach. Czasu wykonania nie mierzyłem, ale jest poniżej sekundy.
Jak kogoś interesuje algorytm:

Spoiler:

For i = 1 To 12
A(i, 1) = 1
For j = 2 To 12
A(i, j) = 11 * (i - 1) + j
Next j
Next i
For i = 13 To 133
A(i, 1) = (i + 9) \ 11
A(i, 2) = (i + 9) Mod 11 + 13
For j = 3 To 12
A(i, j) = A(i, j - 1) + (i + 108) \ 11
If A(i, j) > 11 * j + 1 Then A(i, j) = A(i, j) - 11
Next j
Next i

[ja_n]

Jak kogoś interesuje algorytm:

Niedokładnie zrozumiałem co oznacza "\" w Twoim zapisie. Spróbowałem go zinterpretować jako dzielenie całkowite jak i jako modulo i za każdym razem dostałem błędne wyniki...

[MichalStajszczak]

\ to dzielenie całkowite (dzielenie modulo też występuje w algorytmie w postaci Mod)

[piotrsmu]

potwierdzam działanie algorytmu Michała.
przy k*(k-1)+1 symbolach/kartach można uzyskujemy pełną symetrie symboli

[edit] dobra, coś mi się porąbało, ale dalej nie rozumiem skąd to k(k-1)+1

wzór oczywiście wziął się z ograniczenia że każda para ma występować w równej ilości
i że jedna karta zawiera k*(k-1)/2 par
oszacowanie w drugą stronę jest znacznie trudniejsze, sprowadza się do pokazania że istnieje lista cykliczna k liczb całkowitych których każdy przedział sumuje się do innej liczby całkowitej z przedziału 1..k(k-1)+1
tak dla 6 symboli
na karcie n są symbole n n+1 n+8 n+11 n+13 n+17 stosujemy arytmetykę modularną k*(k-1)+1

ps
druga część wypowiedzi to był oczywiście żart ze źle zdefiniowanego zadania oczywiście można dać jeden wspólny symbol na wszystkich kartach a reszta losowa unikalna

[ja_n]

OK, znalazłem błąd w mojej implementacji tego algorytmu. Z dzieleniem całkowitym wszystko się zgadza, program generuje poprawny zestaw 133 kart. Michał podszedł do problemu z przeciwnej strony - najpierw wymyślił jak te karty powinny wyglądać, a potem napisał program, który to robi. Ja kombinowałem jak napisać program, który generuje karty po to, żeby dopiero po ich wygenerowaniu zobaczyć jak wyglądają . Moje gratulacje, problem rozwiązany.

[Karol Madaj]

I ja gratuluję!

[stalker]

Teraz na podstawie wygenerowanego zbioru trzeba jeszcze zautomatyzować skład.

[Karol Madaj]

Nie trzeba, porównam 133 tuziny liczb wygenerowanych przez Michała ze 133 tuzinami liczb wygenerowanych metodą tabelkową i z porównania powinny wyjść te tuziny w których się pomyliłem. Potem przygotujemy na nowo grafikę tylko tych kilku (kilkanastu?) kart.

[gibon]

Moje sprawozdanie ze środowego spotkania:

Jedwab Ciekawa zabawa polegająca na doborze sprzeczności, fajny pomysł któy należy rozwijać dalej. Przeszkadzały niewyraźne kolory. Być może sprawę poprawiłoby zastosowanie GRUBEJ czcionki i zmniejszenie liczby kolorów. Nie do końca jasne były zasady pojedynku.

Piramida Mustafy Świetna mechanika pozyskiwania zasobów, niestety cała reszta mało nawiązuje do budowania piramidy. Brakuje mi jakiejś mechaniki, która w naturalny sposób wymuszałaby na graczach budowanie kolejnych kondygnacji. W tej chwili piramidę mógłby równie dobrze zastąpić tor punktacji.

SAR Nie nosi to znamion gry. Wrzucam na dłuższy czas do beczki, niech skiśnie może nabierze smaku.

Piramida Jaśka Przyglądałem się tylko. Wygląda na poprawnie działającą grę logiczną. Właściwie jest to jakaś wiariancja domina. Jeśli już miałbym ponarzekać to może na małą rozmaitość tego co dzieje się w tej grze. Jest to z drugiej strony niewątpliwa zaleta, bo mogą w nią grać sześciolatki.

[sipio]

Dla ścisłości ja doliczyłem się 11 protypów.
Dzięki wielkie za testy i wszelkie uwagi.

Picasso ... może gra powinna uwzględnić jakieś złożone obrazki-scenki (jak Dixit) i gracze rysowaliby coś co kojarzy się z obrazkiem?

Coś bardzo podobnego już jest i zwie się Telestrations w wersji komercyjnej a w orginale Eat Poop You Cat.
Ale będę myślał, bo podsunąłeś mi pewną myśl.

Ja zaliczyłem grę w Migawki. Po przerwie zagrałem i super, że poprawiona została mapa (w tym znaki A i B) i weszły patyczki. Dzięki nim nie miałem żadnego problemu z ogarnięciem połączeń pomiędzy regionami. Zastanawiałem się tylko czy nie da się lekko podrasować patyczki tak by każdy z nich miał czarną końcówkę. Wtedy jeden rzut na mapę i będę widział w którym kierunku ludzie jadą. Oczywiście mogę to zrobić patrząc na karty graczy ale tak by było łatwiej, choć nie wiem czy lepiej. Poza tym lekko mnie męczy to że mam 7 specjalnych kart, które też gdzieś muszę trzymać. Fajnie gdyby to były jakieś nieduże żetony (trzy kółka, cztery kwadraty), które miałby miejsce na planszy gracza gdzieś z boku. A w ręku czy na stole chodziły by tylko karty jednego rodzaju.

Na koniec chylę czoła przed chłopakami od algorytmów. Żałuje, że w szkole nie uważałem na zajęciach z informatyki to może być nieco więcej z tego rozumiał .

[stalker]

Dzięki Piotrek za uwagę Zanotowałem, ale tego to już na pewno nie będę sam sprawdzał Lepsze by były znaczniki kierunkowe… ale takie miałem pod ręku i są najtańsze

Przecież to nie informatyka, a algorytmika (lepiej jednak nie będę zabierał głosu, bo dyskusję, owszem, rozumiem, ale brak mi prawidłowego słownictwa i odpowiedniego zaplecza, więc i tak wyjdę na głupiego )

[Jan Madejski]

Lepsze by były znaczniki kierunkowe… ale takie miałem pod ręku i są najtańsze

Tańsze od paczki zapałek?

[stalker]

Nie sądzę, aby potencjalny wydawca chciał umieścić w pudełko zapałki a poza tym chciałem się na własnej skórze przekonać, jak się patyczki sprawdzają

[Jan Madejski]

Zawsze możesz zanurzyć wszystkie patyczki jednym końcem w farbie i będą kierunkowe.

[stalker]

Nie zrozum mnie źle, oczywiście, że mógłbym, ba, mam nawet taki patyczyki-strzałki które wskazują kierunek… ale to już są komponenty wymagające specjalnego zamówienia.

[Jan Madejski]

Jasne, że takie liczmany są kosztowo najwydajniejsze (możliwe, że nawet tańsze od wykałaczek, które dostałem w pewnej polskiej grze ) ale jako projektant mógłbyś sprawdzić jeszcze na etapie prototypu czy takie drobne usprawnienie nie zwiększa nagle czytelności i frajdy z gry na tyle, by równoważyło potencjalne koszty!
No dobra, w tym przypadku nie zwiększy... Czepiam się