Użytkownik "slawek" <s...@h...pl> napisał w wiadomości grup
dyskusyjnych:hmgu2e$23d$...@a...news.neostrada.pl
...
> Ja tam "nie myślę" - tzn. nie stosuję jakiegoś formalnego algorytmu. Więc
> raczej blado od tej strony. :)

Jeszcze uzupełnienie - wystarczy np. zajrzeć do "Tetris is Hard, Even to
Approximate" http://arxiv.org/abs/cs.CC/0210020 aby nabrać podejrzeń, że
problem jest Bardzo Trudnym Problemem NPC.

Jednak to nieprawda - nie chodzi o program idealnie grający - ale o coś, co
w miarę będzie działać, czyli może robić błędy i może przegrywać.

slawek

do góry

W dniu 2/28/2010 11:58 PM, slawek wrote:
>
> Użytkownik "jacem" <j...@1...pl> napisał w wiadomości grup
> dyskusyjnych:hmb9gb$jnh$...@n...news.neostrada.pl.
..
>> No dobrze, temat chyba już wyczerpany.
>
> To jeszcze jedna prośba - padły różne propozycje - stąd moje kolejne
> pytania.
>
> Ile czasu potrzebowalibyście, aby w waszym ulubionym języku napisać
> program grający w Tetris? I jak długi - według was - byłby to program?
>
> Nie chodzi rzecz jasna o napisanie kolejnego klona Tetrisa - lecz o
> program, który dysponując danymi o kolejnych klockach (tak jak człowiek)
> potrafiłby w miarę sensownie układać te klocki zgodnie z regułami gry
> Tetris.
>
> Nie potrzeba mi takiego programu! Ale myślę, że tego rodzaju problem nie
> jest zupełnie trywialny. Chciałbym jedynie, abyśmy mieli jakieś
> porównanie, coś czym moglibyśmy uzupełnić dyskusję nt. dydaktycznych
> języków programowania.

Przy tak postawionych kryteriach zastanowiłbym się nad Pythonem.
Elegancja, elastyczne struktury danych, spora efektywność pracy nad kodem.

Pozdrawiam,
Arkadesh

do góry

Użytkownik "Arkadiusz Dymek" <a...@n...bedzie> napisał w wiadomości grup
dyskusyjnych:4b8c48ae$...@n...home.net.pl...
> Przy tak postawionych kryteriach zastanowiłbym się nad Pythonem.
> Elegancja, elastyczne struktury danych, spora efektywność pracy nad kodem.

To już wiem. Choć - moim zdaniem - Phyton jest bałaganiarski, a pomysł z
wcięciami... tragiczny bardziej niż 73 kolumna.

Nowe pytanie brzmiało jednak: ile roboczo-dni i ile linii kodu - w ulubionym
języku? Orientacyjnie. Na coś co WYGLĄDA jak program rozwiązujący tetris.

slawek

do góry

Użytkownik "slawek" <s...@h...pl> napisał w wiadomości
> Ja tam "nie myślę" - tzn. nie stosuję jakiegoś formalnego algorytmu. Więc
> raczej blado od tej strony. :)

Mózg przetwarza, i to intensywnie.
Zagraj w tetris.
A potem przyłóż dłoń do czoła.
Przekonasz się jakie gorące. ;-)

Podejmujesz decyzje "odruchowo", to jasne. Ale nie są przypadkowe.
Czymś się kierujesz.

> Kiedyś napisałem program grający w kółko i krzyżyk - algorytm był
> jednolinijkowy, do dziś pamiętam:
> n = (n + 1) mod 9
> Sprawdza się na planszy 3x3, AI zawsze jako druga, numeracja pól jakoś
> tam sobie szła. Nie wygra i nie przegra. Czysty minimax.

A na planszy 5x5?

>> Ludzie, którzy na codzień zajmują się tworzeniem gier, na pewno dadzą
>> wyczerpującą odpowiedź. Przypuszczam, że tego typu problemy mają już
>> dawno rozpracowane.
> Zgoda, ale NIE chodzi o to aby ZROBIĆ TO - ale aby zastanowić się JAK
> DUŻE TO BYŁOBY WYZWANIE.

> I odpowiedź niekoniecznie nieomylna - może algorytm da się streścić w
> paru linijkach? A może porządny algorytm to jakieś 10 tysięcy linii
> kodu? Mnie nie interesuje, by taki napisać (bo i po co?) - ale aby
> zorientować się, jak bardzo ufacie swoim ulubionym językom
> programowania. Jeżeli ktoś np. pisze, że PHP jest cool - a potem nie
> potrafi ocenić, ile musiałby naklepać tego PHP aby mieć "program
> rozwiązujący łamigłówkę Tetris" - to czy PHP jest taki cool? Zamiast
> PHP podstawcie sobie inne języki, przeiterujcie.


Nie mam swojego ulubionego języka.
To tylko narzędzie.
Może być C++, Java, C#...

> Jeszcze jedno - zakładam że program nie musi być the best - takim
> "terisowym mistrzem" - patrz Głęboko Niebieski i gra w szachy. Chodzi
> tylko o to, by grał sportowo, uczciwie. Dlatego odpadają programy
> upuszczające klocki tak jak są, albo upuszczające je z losowym obrotem
> i przemieszczeniem. Pewnym utrudnieniem mogłoby być przesuwanie klocków
> tak, aby wlazły pod inne (pozwalamy opaść w pewnym położeniu... i myk w
> lewo lub prawo gdy będą już na dole) - więc załóżmy że tego robić nie
> wolno.
> Ja bym próbował np. tak jak poniżej. Nie twierdzę, że to dobre
> rozwiązanie.
> Przesunięć jest może 10, obroty mnożą to przez 4, symetria może
> zredukować. Czyli jakieś do 40 pozycji do rozpatrzenia, powiedzmy 2^5.
> Typów klocków jest może z 2^4. Stąd przewidywanie jakie przyjdą kolejne
> dwa (mając już jeden) i spasowanie ich daje łącznie (2^5)^3 * (2^4)^2 =
> 2^23 = 8 milionów kombinacji. To niedużo - jeżeli jeszcze uda nam się

Skoro klocki pojawiają się przypadkowo, to jaki sens przewidywania?
A ty przewidujesz, który klocek następny podczas układania bieżącego?

> ograniczyć trochę (usunąć te, które są ewidentnie złe, odfiltrować
> symetryczne). Czyli wstawiamy klocek tak, aby optymalnie pasował -
> biorąc pod uwagę kolejne dwa, których jeszcze nie ma. I od nowa.
> Musimy jeszcze jakąś reprezentację mieć planszy, klocków, definicję
> "optymalności" - nie mówię że to łatwe i nie jest pracochłonne.
> Ale zakładam, że program ma prawo się mylić - tzn. nie musi sprawdzać
> wszystkich możliwości, może używać funkcji random (jeżeli to uzasadnione).
> Trzebaby pogooglać - może są jacyś entuzjaści tego typu programów. Ale
> nie chodzi o sam program - lecz o zagadnienie, które: a. można
> zaprogramować; b. nie jest to "typowe" programowanie
> kadry-płace-excel-webmastering-cholera-wie-co; c. fajne jakieś takie
> wyszło.
> Moim zdaniem ciekawiej jest porównywać "jak duży ma być program
> układający Tetris" - niż programy "Hello, I am Jan... Jan B."
> slawek

Wszystko zależy od poczynionych założeń początkowych i uproszczeń.
Im prościej, tym bardziej elegancko. :-)

Przypuszczam, że najkrótszy (ale najmniej czytelny) kod byłby w Ruby'm.
(pomijam Perla)




j.

do góry

Użytkownik "jacem" <j...@1...pl> napisał w wiadomości grup
dyskusyjnych:hmihh9$n69$...@a...news.neostrada.pl
...
> Skoro klocki pojawiają się przypadkowo, to jaki sens przewidywania?
> A ty przewidujesz, który klocek następny podczas układania bieżącego?

Nie mam dziś ochoty tłumaczyć rzeczy aż tak oczywistych.

> Wszystko zależy od poczynionych założeń początkowych i uproszczeń.
> Im prościej, tym bardziej elegancko. :-)

Niekoniecznie. Sortowanie szybkie jest przy twojej definicji bardzo
"nieeleganckie". Sama prostota niewiele warta, jeżeli daje nieefektywne lub
wręcz błędne rozwiązania.

> Przypuszczam, że najkrótszy (ale najmniej czytelny) kod byłby w Ruby'm.
> (pomijam Perla)

Ok, wreszcie coś konstruktywnego od ciebie. Więc ile linii w Ruby i jak
długo - orientacyjnie - trwałoby napisanie? Dzień? Tydzień? Miesiąc? Dłużej?

slawek

do góry

Użytkownik "slawek" <s...@h...pl> napisał w wiadomości
news:hmi6ln$qi$1@atlantis.news.neostrada.pl...
> Użytkownik "Arkadiusz Dymek" <a...@n...bedzie> napisał w wiadomości
> grup dyskusyjnych:4b8c48ae$...@n...home.net.pl...
>> Przy tak postawionych kryteriach zastanowiłbym się nad Pythonem. Elegancja,
>> elastyczne struktury danych, spora efektywność pracy nad
>> kodem.
> To już wiem. Choć - moim zdaniem - Phyton jest bałaganiarski, a pomysł z
> wcięciami... tragiczny bardziej niż 73 kolumna.
> Nowe pytanie brzmiało jednak: ile roboczo-dni i ile linii kodu - w
> ulubionym języku? Orientacyjnie. Na coś co WYGLĄDA jak program
> rozwiązujący tetris.

Zdolny gimnazjalista, który zna podstawy algorytmiki, biegle posługuje się swoim
ulubionym językiem (np. python, ruby, delphi, c#, c++, czy co tam innego...),
zakładając, że nie poświęci wiele czasu na oprogramowanie UI (może być w trybie
znakowym), to zajmie mu to nie więcej niż 2 wieczory i kilkaset linii kodu.



j.

do góry

Użytkownik "jacem" <j...@1...pl> napisał w wiadomości grup
dyskusyjnych:hml85o$6ql$...@a...news.neostrada.pl
...
> Zdolny gimnazjalista, który zna podstawy algorytmiki, biegle posługuje się
> swoim ulubionym językiem (np. python, ruby, delphi, c#, c++, czy co tam
> innego...), zakładając, że nie poświęci wiele czasu na oprogramowanie UI
> (może być w trybie znakowym), to zajmie mu to nie więcej niż 2 wieczory i
> kilkaset linii kodu.

Ok, wpisuję to do "bazy danych" - czyli "jacem" twierdzi że program
układający (tzn. AI podejmująca decyzję gdzie wstawić losowo generowane
klocki znając w każdej chwili wyłącznie jeden klocek) - co jest jak "wszyscy
wiemy" problemem NP-zupełnym - zajęłoby mu gdyby był zdolnym gimnazjalistą:

1. Phyton 10 godzin 500 linii kodu
2. Ruby 10 godzin 500 linii kodu
3. Delphi 10 godzin 500 linii kodu
4. C# 10 godzin 500 linii kodu
5. C++ 10 godzin 500 linii kodu

Komentarz A.: założyłem że dzień to 24 godziny które dzielą się na "rano",
"po obiedzie", "wieczorem", "w nocy" itp., czyli "dwa wieczory" to mniej
więcej 2 razy po pięć godzin, możliwe że to jest także bliższe 12 czy 14
godzinom albo też krótszemu czasowi (zwłaszcza że taki gimnazjalista/ka musi
wieczorem zęby umyć i parę jeszcze rzeczy zrobić - wiadomo, rodzice).

Komentarz B: 500 linii kodu, bo kilkaset to mniej niż tysiąc i więcej niż
sto. Może trzeba było napisać 500 +/- 400, czy jakoś tak.

Komentarz C: wątpię - widzę raczej kolejny przykład chciejstwa - samo
przemyślenie projektu to jeden dzień. Kodując 500 linii w 10 godzin
mielibyśmy 50 linii na godzinę, czyli 1 linię na minutę plus 10 minut
przerwy na fizjologię, kompilację, cokolwiek. Takie tempo jest możliwe, ale
gdzie i kiedy w takim razie uruchomienie - czyli debugging? Jeżeli w po
kilku godzinach zmieni się koncepcja - to będzie jeszcze gorzej. Brak czasu
na sporządzenie dokumentacji: takiej "autodocowej" i takiej w postaci
helpu/instrukcji dla użytkownika. Pomijam złotą regułę 40% (w praktyce 4x) -
"jeżeli planujesz że coś zabierze x roboczogodzin, to będzie to gotowe po
czasie o 40% dłuższym". Mniejsza liczba linijek? Owszem, ale wymagać to
będzie bardziej przemyślanej konstrukcji algorytmu...

Nie raz widziałem gieroji, którzy chwalili się, jak szybko zrobią dany
projekt - zwykle padał magicznie termin jednotygodniowy. Mam na nich dość
konkretny sposób - zakładam się o skrzynkę piwa. Piwa mi nie brakuje.
Bezalkoholowego oczywiście ;)

slawek

do góry

slawek pisze:
>
> Użytkownik "jacem" <j...@1...pl> napisał w wiadomości grup
> dyskusyjnych:hml85o$6ql$...@a...news.neostrada.pl
...
>> Zdolny gimnazjalista, który zna podstawy algorytmiki, biegle posługuje
>> się swoim ulubionym językiem (np. python, ruby, delphi, c#, c++, czy
>> co tam innego...), zakładając, że nie poświęci wiele czasu na
>> oprogramowanie UI (może być w trybie znakowym), to zajmie mu to nie
>> więcej niż 2 wieczory i kilkaset linii kodu.
>
> Ok, wpisuję to do "bazy danych" - czyli "jacem" twierdzi że program
> układający (tzn. AI podejmująca decyzję gdzie wstawić losowo generowane
> klocki znając w każdej chwili wyłącznie jeden klocek) - co jest jak
> "wszyscy wiemy" problemem NP-zupełnym - zajęłoby mu gdyby był zdolnym
> gimnazjalistą:
[ciach]

Zwróć uwagę, że napisałeś powyżej coś w stylu "nie musi wygrywać" - w
tetrisa nie da się "wygrać", można tylko mieć więcej punktów niż inni,
można więc chyba założyć, że chodziło Ci o to, że program nie musi grać
optymalnie. To poważnie zaniża poziom konkursu i jednocześnie sprawia,
że Twoje uwagi powyżej do ustalonych przez Ciebie zasad konkursu chyba
nie pasują.

JD

PS. Oczywiście dwa wieczory na program grający optymalnie to, nazwijmy
to, grube niedoszacowanie.

do góry

Użytkownik "Jędrzej Dudkiewicz" <j...@g...com> napisał w
wiadomości grup dyskusyjnych:hmlrvl$pi5$...@n...onet.pl...
> Zwróć uwagę, że napisałeś powyżej coś w stylu "nie musi wygrywać" - w
> tetrisa nie da się "wygrać", można tylko mieć więcej punktów niż inni,
> można więc chyba założyć, że chodziło Ci o to, że program nie musi grać
> optymalnie.

Zgoda, nie musi grać optymalnie. Jednak powinien grać uczciwie. Powiedzmy...
powinien grać na tyle dobrze, aby nie grać gorzej niż człowiek ;)

>To poważnie zaniża poziom konkursu i jednocześnie sprawia, że Twoje uwagi
>powyżej do ustalonych przez Ciebie zasad konkursu chyba

Nie ma konkursu. Po prostu chodzi mi o to, że każdy (chyba) potrafi sobie
wyobrazić, jak taki program mógłby próbować stworzyć: ile czasu i jaki duży.
Czy te wyobrażenia w jakikolwiek sposób są zgodne z rzeczywistością/prawdą?
To nie jest istotne... Bo nie chodzi mi o program, ale o to jak ludzie
używający różnych języków widzą poziom złożoności zagadnienia. Innymi słowy:
jak wybrany przez programistę język wpływa na wyobraźnię programisty.

Były propozycje różnych dydaktycznych języków. W Small Basic jest np.
przykładowy Tetris (ale grać w to ma człowiek). Zainteresowało mnie, ile
razy dłuższy byłby ten program w Small Basic, gdyby musiał sam sobie klocki
układać i to nie oszukując. I jak byłby to długie/duże/trudne - gdyby
zamiast Small Basic brać np. Pascala czy C++ z STL ?

> PS. Oczywiście dwa wieczory na program grający optymalnie to, nazwijmy to,
> grube niedoszacowanie.

Zgoda, lecz jak na razie "w bazie danych" mam że 500 linii i 10 godzin w
przypadku prostych języków obiektowych ogólnego stosowania, takich C#.

slawek

do góry

Użytkownik "slawek" <s...@h...pl> napisał w wiadomości

> Komentarz A.: założyłem że dzień to 24 godziny które dzielą się na
> "rano", "po obiedzie", "wieczorem", "w nocy" itp., czyli "dwa wieczory"
> to mniej więcej 2 razy po pięć godzin, możliwe że to jest także bliższe
> 12 czy 14 godzinom albo też krótszemu czasowi (zwłaszcza że taki
> gimnazjalista/ka musi wieczorem zęby umyć i parę jeszcze rzeczy zrobić
> - wiadomo, rodzice).

Widać, że jako nastolatek, nie miałeś w rękach komputera. :-)))
Oni potrafią non stop ryć przy klawierze po kilkanaście godzin dziennie.

Trochę nonszalancko się wyraziłem:
Pisząc "wieczory", miałem raczej na myśli dwa dni intensywnej pracy.
Co można w 10 godzin zrobić? Sam wiesz.
Licząc wg twoich kryteriów niech to będą 4 wieczory.

> Komentarz B: 500 linii kodu, bo kilkaset to mniej niż tysiąc i więcej
> niż sto. Może trzeba było napisać 500 +/- 400, czy jakoś tak.

Raczej bliżej do 1000 niż 500.
Powiedzmy, że ok. 800.

> Komentarz C: wątpię - widzę raczej kolejny przykład chciejstwa - samo
> przemyślenie projektu to jeden dzień. Kodując 500 linii w 10 godzin


Jeśli ktoś jest pochłonięty problemem, to ten młody człowiek nawet siedząc na
sedesie, będzie go zgłębiał.
Ogólny zarys będzie miał po kilku godzinach.

> mielibyśmy 50 linii na godzinę, czyli 1 linię na minutę plus 10 minut przerwy
> na fizjologię, kompilację, cokolwiek. Takie tempo jest możliwe,
> ale gdzie i kiedy w takim razie uruchomienie - czyli debugging? Jeżeli
> w po kilku godzinach zmieni się koncepcja - to będzie jeszcze gorzej.
> Brak czasu na sporządzenie dokumentacji: takiej "autodocowej" i takiej
> w postaci helpu/instrukcji dla użytkownika. Pomijam złotą regułę 40% (w
> praktyce 4x) - "jeżeli planujesz że coś zabierze x roboczogodzin, to
> będzie to gotowe po czasie o 40% dłuższym". Mniejsza liczba linijek?
> Owszem, ale wymagać to będzie bardziej przemyślanej konstrukcji
> algorytmu...

Im dalej w las, tym więcej drzew. To prawda.
Jeśli życzyłbyś sobie dokumentacji, to niestety, ale jeszcze jeden wieczór
należałoby dodać.

A testy?

Trzeba przeprowadzić testy, aby zakwalifikować produkt.
Zagrać: maszyna kontra człowiek.

I należałoby ustalić, że program jest ok, jeśli zwycięży np. w 30% rund (3 na
10).


No tak, przy twoich wymaganiach z 2 wieczorów zrobi się 5!

> Nie raz widziałem gieroji, którzy chwalili się, jak szybko zrobią dany
> projekt - zwykle padał magicznie termin jednotygodniowy. Mam na nich dość

Ja ich często widuję. ;-)

A jeszcze częściej widuję bossów, którzy oczekują, że ktoś im projekt wykona w
tydzień (np. wg moich szacunków w 5 tyg.) za przysłowiowe dwa piwa.
Wtedy odsyłam ich do "gieroji", o których wspomniałeś powyżej. :-)))

> konkretny sposób - zakładam się o skrzynkę piwa. Piwa mi nie brakuje.
> Bezalkoholowego oczywiście ;)

A co to?
Niepijący alkoholik? :-)))


j.

do góry