lonewolf - 2005-02-09, 19:21 Temat postu: Konkurs problemów VCF Zainspirowany ostatnią lekcją na renjuclass proponuję zrobić mały konkurs. Chodzi o stworzenie (samodzielne) pozycji, w której następuje wygrana przez VCF w możliwie największej liczbie ruchów i w której nie ma innego, krótszego VCF'a. Ponieważ teraz są ferie, sesje, itp. proponuję dać czas do końca lutego. Jest ktoś chętny? Szczegóły typu gdzie wysyłać rozwiązania, czy można przysłać więcej niż jedną pracę, itp. są oczywiście do ustalenia. Barfko - 2005-02-09, 22:37 Fajne. Jak sprawdzić, że nie ma krótszego VCF? adik - 2005-02-09, 22:40 W RenLibie jest chyba pliczek gdzie są VCFy - może nie są one trudne, ale zawsze to coś.. Pozdrawiam, Adik. Ece - 2005-02-09, 22:55 Barfko, RenLib dazy do najkrotszego VCFa z tego co widzialem (moze poza osatnim testowym). Zreszta nie widze problemu w sprawdzeniu samemu. Adik, nie chodzi o to. Na ostatniej lekcji bylo o tym, ze Japonczycy tworza rozne uklady do znajdywania VCFow. Taki ich trening. Yamaguchi zrobil uklad z VCFem w 84 ruchach (zajelo mu to tydzien - jedynie goban), a mowil ze najdluzszy jaki widzial, to 87 ruchow. Piatka zostaje postawiona na ostatnim wolnym polu na planszy. Pomysl fajny, ale niestety beze mnie 
adik - 2005-02-09, 23:28
Tylko, że Yamaguchi nosi pingle ala Stępień z 13 Posterunku, ma 17 gobanów w domu, a psa karmi kamieniami. Ja mógłbym w Gomoku zrobić na siłę jakiś VCF 120 ruchów, ale póki co - ciesze się młodością i nie chce o lasce dokładać 119 pionka. Taki VCF to dupka, bo rzadko się zdarza - właściwie nie można go przewidzieć - po prostu widzi się pewne powiązania, itd.. - tworzyć VCFy to głupota - fajniej je rozwiązywać, ale nie wiedząc, że owy VCF jest - wtedy ma się zupełnie inny punkt widzenia, jest ciekawiej. Kiedy jesteś nastawiony na to, żeby łączyć czwórki - nic z tego nie będzie, bo nawet ja początkujący Gomokowiec, debil Renju jestem w stanie takiego VCF ułożyć. Sądze, ze ten VCF Kawaguchiego można szybciej zakończyć. Pozdrawiam, Adik. Ece - 2005-02-09, 23:36 VCF w 120 ruchach to 240 kamieni, podczas gdy plansza ma 225 pol - jak Ci sie uda, to Ci mistrzostwa swiata w Gomoku w Witkowie zorganizuje ![:]](images/smiles/krzywy.gif ":]")
Tego VCFa nie da sie szybciej zakonczyc, a tak autorytatywne wypowiedzi kogos o tak malym autorytecie sa po prostu zalosne. Barfko - 2005-02-09, 23:39 Może i dąży RenLib do najkrótszego, ale żeby mieć pewność, że jest najkrótszy trzeba wykonać algorytm o złożoności obliczeniowej (optymistycznie patrząc) wykładniczej względem długości najkrótszego VCF. Mam wersję 3.4.2, która tego nie robi z oczywistych względów : w ogólności znalezienie najkrótszego VCF przy założeniu, że ma on długość 50 ma pesymistyczny koszt czasowy ~2^50, czyli mój komputer spłonąłby w zewnętrznych warstwach czerwonego słońca zanim by to policzył. Sprawdzenie "samemu" też ma złożoność wykładniczą i nie da się tego ominąć (dla wtajemniczonych : łatwy argument z tzw. wyrocznią). Mam/miałem przykłady VCF długości ~30, których znalezienie wymagało wykonania ponad 5.000.000 operacji. Samemu się po prostu nie da. A algorytm wyszukiwania VCF w RenLibie nie ma nawet "dowodu poprawności", nie mówiąc już o tym, że nie ma dowodu, że znajduje najkrótszy. Proponuję zdefiniować długość VCF za pomocą długości VCF znalezionego z użyciem RenLiba w wersji 3.4.2 (niestety w tej i we wcześniejszych wersjach są błędy w algorytmie, natomiast wersja testowa tamtych błędów nie ma, za to znajduje długie VCFy). bad_mojo - 2005-02-09, 23:51 Rozumiem, że ma to być plansza 15x15, ilość ruchów po jednej i po drugiej stronie taka sama, tyle samo białych i czarnych kamieni na gobanie (różnica oczywićie jednego ewentualnie), a zasady jakie? renju? czy gomoku? P.S. podobał mi się text o płonącym kompie  nawet bardzo...
Barfko - 2005-02-10, 14:48 Sądzę, że 15x15, renju głównie z powodu RenLiba. VCF białymi może zakończyć się zmuszeniem do faulu. Wszystko właśnie po to, żeby dało się to obrabiać pod RenLibem, ale według mnie RenLib jest dość niefortunnym narzędziem do tworzenia takich VCFów. Szczęśliwi posiadacze desek i kamieni są w uprzywilejowanej sytuacji. Można używać programów typu RenBase OLE server, ale deska ... heh .... lonewolf - 2005-02-10, 14:54 W takich problemach VCF'a mają czarne, więc kończy się ustawieniem piątki. Trzeba uważać, żeby nie zrobić faulu, dodatkowo overline białych wygrywa. W gomoku byłoby znacznie łatwiej. Barfko - 2005-02-10, 15:01 Kolko kiedyś pisał o VCFie białych zakończonym faulem czarnych na ostatnim wolnym polu na planszy. Dla mnie to jest szczyt możliwości w tym rzemiośle. Długie VCFy czarnymi to wystarczające wyzwanie, węc spoko - może być tylko czarnymi. angst - 2005-02-10, 17:47
Pozdrawiam Angst Chaosu - 2005-02-16, 09:22 . . .Może darujemy sobie ideę konkursu, a poprostu damy możliwość zainteresowania się problemem? Dla przykładu ja jestem ciekawy, jak inny podchodzą do problemu. Mi 2godziny zajęło to co zrobiłem (od zera). Niestety tych czwórek wyszło jakoś mało... i nie wiem czy nie ma krótszego wina u którejś ze stron. lonewolf - 2005-02-16, 13:10 Konkurs odwołany ze względu na brak chętnych. Po prostu, jeżeli ktoś coś zrobi, to pokaże tutaj, tak jak to zrobił Chaosu. Barfko - 2005-02-16, 15:20 Tak chyba najlepiej. Nad długimi VCF-ami pracuje się dość długo. Barfko - 2005-04-12, 00:16 Post poniekąd nie do końca bez związku z tematem. Chodzi o następujące zadanko: Czy na nieskończonej planszy (gomoku) istnieje taki układ skończonej liczby kamieni czarnych i białych, że można wykonać nieskończenie wiele czwórek (z blokami). Czyli chodzi o taki nieskończony "VCF". Według mnie piękny problemik. Nie mam śmiałości zakładać dla niego nowego tematu. Rozwiązanie może kiedyś podam... bad_mojo - 2005-04-12, 00:40 OK, na chłopski rozum: "jeżeli jest skończona ilość kamieni, to w końcu nie będzie z czego robić piątek, bo wszystko będzie poblokowane, a ta w ogóle to skrót "vcf" zakłada zwycięstwo, więc koniec czwórek...". Z doświadczenia wiem, że zaraz będzie mi ktoś chciał udowodnić, że tak nie jest i że jest to jakieś podchwytliwe pytanie i że w ogóle to chodzi tylko o oznaczenia 
Barfko - 2005-04-12, 01:44 Nie napisałem jakie są warunki zwycięstwa w grze, którą opisałem . Poza tym VCF umieściłem w cudzysłowiu.
Żeby nie było, że to takie łatwe: gdyby chodziło o "4 w rzędzie", to istnieje taki układ skończnej liczby czarnych kamieni i nieskończonej liczby białych, że czarne mogą w nieskończoność robić trójki bez "cięć" (nie doprowadzając do otwartej trójki, co jest równoważne zwycięstwu). Czyli nie da się wszystkiego poblokować. Rozwiązanie musi więc wykorzystywać fakt, że się gra do pięciu w rzędzie. wicherek - 2005-04-15, 20:09 dobre pytanie, sam kiedys zastanawialem sie dlaczego w pente nie ma remisow.. czy da sie zapelnic plansze w pente ? bez zdobycia 10 pkt przez przeciwnika ? ja mysle ze jest to mozliwe ale trzeba by bylo to dobrze rozplanowac ktos kiedys wspominal (chyba Chaosu) ze jest rodzaj gry pente w ktorym po postawieniu X*OX OO znika co umozliwia zdobycie remisu, ciekawe. Chaosu - 2005-04-19, 15:47 . . .Poof pente zaimplementowane na pente.org, jednak tam remisów nie ma, bo jest ustalone, że któreś bicie dzieje się pierwsze (lub że po 10:10 gra się dalej do 12), ale na forum brainking.com swego czasu można było trochę pogadać o puzzlach w poof-pente dających remisy. |
