Forum.Gomoku.pl Strona Główna Forum.Gomoku.pl
Forum Polskiego Stowarzyszenia Gomoku, Renju i Pente

FAQFAQ  SzukajSzukaj  UżytkownicyUżytkownicy  GrupyGrupy  StatystykiStatystyki
RejestracjaRejestracja  ZalogujZaloguj

Poprzedni temat «» Następny temat
Sekwencyjność go-moku
Autor Wiadomość
jopq 
retired


Dołączył: 10 Cze 2004
Posty: 737
Skąd: Warszawa
Wysłany: 2007-10-09, 11:11   Sekwencyjność go-moku

Ostatnio czytając o sekwencyjnych strukturach danych, wzorcach, algorytmach ich przeszukiwania zadałem sobie pytanie: na jaką powierzchnię wokół na planszy ma oddziaływanie każdy ruch? Pytanie wcale nie takie głupie, bo może udało by się całą grę zapisać w postaci skończonej maszyny stanów, gdzie dla każdej możliwości wykonywało by się parę operacji wyceniających daną pozycję. Być może kamień ma wpływ na otoczenie rzędu 4 pól? Kto wie. Gdyby mieć narzędzie w postaci API jakiegoś dobrego programu do gomoku, to można by się pobawić. Czym różni się to podejście od heurystyk? Ano choćby tym, że tutaj istotna jest kolejność ruchów.
Ludzki mózg przecież nie sprawdza wszystkich możliwości, nie ocenia też czysto heurystycznie, bo "działa" w oparciu o właśnie poznane sekwencje, których uczy się i ulepsza cały czas. Może ktoś będzie miał ochotę podzielić się swoimi przemyśleniami :P
 
 
utratos 

Dołączył: 28 Kwi 2004
Posty: 789
Skąd: Warszawa
Wysłany: 2007-10-09, 13:42   

jopq napisał/a:
Ostatnio czytając o sekwencyjnych strukturach danych, wzorcach, algorytmach ich przeszukiwania zadałem sobie pytanie: na jaką powierzchnię wokół na planszy ma oddziaływanie każdy ruch? Pytanie wcale nie takie głupie, bo może udało by się całą grę zapisać w postaci skończonej maszyny stanów, gdzie dla każdej możliwości wykonywało by się parę operacji wyceniających daną pozycję. Być może kamień ma wpływ na otoczenie rzędu 4 pól? Kto wie


Hmn jeśli dobrze zrozumiałem odpowiedz brzmi 15 pól czyli maks. Wyobraż sobie vcf zaczynanego z A1 i kończącego się się cutem na na K1 gdyż stoi kamień na O1 dzięki któremu tworzy się cut. Więc nie można zagrać A1 a np A2 trzeba..
 
 
jopq 
retired


Dołączył: 10 Cze 2004
Posty: 737
Skąd: Warszawa
Wysłany: 2007-10-09, 14:11   

Czy ruch postawiony w grze, który został obudowany dookoła (skrajny i kiepski przykład: czarny i 8 białych wokół), ma jeszcze znaczenie przy szukaniu kolejnych?
 
 
utratos 

Dołączył: 28 Kwi 2004
Posty: 789
Skąd: Warszawa
Wysłany: 2007-10-09, 14:46   

Znaczy zmienia w tym sensie , że
- czarny został przyblokowany
- czarny mógł też w danym polu stworzyć układ szóstkowy a teraz może wybrać inne pole na planszy , które mogło być zajęte przez białego gdyby nie postawilł tam swojego ruchu
Natomiast dla białych -"nie biorących pod uwagę czarnych" ten kamień nic nie daje w osiągnięciu zwycięstwa( jest zmarnowany) ale to sytuacja hipotetyczna:)
 
 
Barfko 

Dołączył: 30 Kwi 2004
Posty: 556
Skąd: 49°25'N8°45'E
Wysłany: 2007-10-13, 00:23   

Są tu dwa pytania.

1. Czyli istnieje "dobra" funkcja ewaluująca pozycję na planszy mająca małą złożoność.
2. Które kamienie mają wpływ na taką hipotetyczną funkcję.

Pierwsze pytanie ~łatwo sprowadzić do "P=NP".

Na drugie pytanie można dość łatwo odpowiedzieć. Wystarczy zdefiniować obszar zapełniony kamieniami następnie zdefiniować inteligentnie brzeg tego obszaru o grubości 5. Kamienie siedzące głębiej, niż 5, są nieistotne, o ile odrzucić overline, co jest tanim uproszczeniem, bo i bez overline pytanie numer 1 jest równoważne "P=NP".

Zalążkiem ciekawej funkcji ewaluującej może być Energia, zdefiniowana jako ogólna liczba swobód wszystkim kamieni danego koloru na planszy. Łatwo kontrolować energię i łatwo różne rzeczy o jej zachowaniu wraz z rozwojem gry udowodnić. Można np. pokazać, że nie istnieje nieskończony VCF na nieskończonej planszy rozpoczęty od skończonego układu kamieni.

Krótko mówiąc idea bardzo szczytna i w dodatku za odpowiedź na owe pytania dostaje się aktualnie 1.000.000$.
_________________
O-jôzu desu ne!
 
 
jopq 
retired


Dołączył: 10 Cze 2004
Posty: 737
Skąd: Warszawa
Wysłany: 2007-10-13, 03:13   

http://portal.acm.org/citation.cfm?id=1143954
 
 
angst 
Członek Zarządu
Kapitan IRP

Dołączył: 28 Kwi 2004
Posty: 4998
Skąd: Płock
Wysłany: 2007-10-13, 08:17   

Barfko napisał/a:
Można np. pokazać, że nie istnieje nieskończony VCF na nieskończonej planszy rozpoczęty od skończonego układu kamieni


Przekładając to na język praktyczny - co to jest nieskończony VCF? Bo coś takiego nie istnieje z definicji :D

Pozdrawiam

Angst
 
 
 
Barfko 

Dołączył: 30 Kwi 2004
Posty: 556
Skąd: 49°25'N8°45'E
Wysłany: 2007-10-13, 20:14   

Skoro prowadzi to do nieporozumień i ktoś w ogóle to czyta, to sprecyzuję.

Dla każdego skończonego układu kamieni na planszy zbiór VCF, wszystkich możliwych zwycięstw poprzez sekwencję czwórek, jest skończony.
_________________
O-jôzu desu ne!
 
 
zukole 

Dołączył: 04 Paź 2004
Posty: 4356
Skąd: Polska
Wysłany: 2007-10-13, 20:39   

Ostatnie zdanie brzmi jak definicja pierdoł podanych przez moją nauczycielkę od matmy.

Były już rozważania na temat otwarć, programów itd, teraz będzie szereg dyskusji na temat "nieskończonego vcf-a" ? :lol: . Może coś w praktyce zamiast suchych wypowiedzi o_O
 
 
bad_mojo 
recenzent ludzkości


Dołączył: 10 Lip 2004
Posty: 1569
Skąd: Konstancin-Jez.
Wysłany: 2007-10-13, 21:32   

Barfko napisał/a:
Dla każdego skończonego układu kamieni na planszy zbiór VCF, wszystkich możliwych zwycięstw poprzez sekwencję czwórek, jest skończony.

Jest coś nieskończonego, co by się opierało tylko na rzeczach skończonych? Miałem świetnego fizyka w podstawówce, przy okazji omawiania prędkości światła, podał nam przykłądy rzeczy, które mogą się poruszać z prędkością większą od prędkości światła: zajączek na ścianie, punkt na przecięciu się ramion nożyczek- ponieważ nie mają masy, nie dotyczą ich też ograniczenia.
_________________
Think for yourself. Question authority. / People tell me what to say, what to think and what to play.
 
 
 
templar 


Dołączył: 14 Maj 2006
Posty: 657
Skąd: toruń
Wysłany: 2007-10-13, 22:26   

bad_mojo napisał/a:
Jest coś nieskończonego, co by się opierało tylko na rzeczach skończonych?

Zależy w jakim sensie pytasz. Bo czy w ogóle można mówić o nieskończoności w świecie rzeczywistym? Wątpię. A jeśli się poruszamy w świecie matematyki, to mogę Ci mnóstwo przykładów podać, choć podejrzewam, że i tak nie zadowolą Cię. :)

Pozdrawiam
templar

P.S. coś nie tak jest gramatycznie z tym moim ostatnim zdaniem.
_________________
"...and remember - anger leads to the dark side!" (kyle katarn)
 
 
Barfko 

Dołączył: 30 Kwi 2004
Posty: 556
Skąd: 49°25'N8°45'E
Wysłany: 2007-10-14, 02:58   

Cytat:
Może coś w praktyce zamiast suchych wypowiedzi.

Za rozstrzygnięcie "P=NP" jest 1 mln USD, dostaje się z dużym prawdopodobieństwem 2 nagrody, Fields i Nevalina, każda też dość opłacalna oraz w przypadku pozytywnego rozstrzygnięcia tej hipotezy można złamać większość używanych na świecie szyfrów. Dla mnie to dość konkretne, hehe, i znacznie praktyczniejsze od wygrania gazyliona turniejów na kurniku.
_________________
O-jôzu desu ne!
 
 
angst 
Członek Zarządu
Kapitan IRP

Dołączył: 28 Kwi 2004
Posty: 4998
Skąd: Płock
Wysłany: 2007-10-14, 08:19   

Barfko napisał/a:
Dla każdego skończonego układu kamieni na planszy zbiór VCF, wszystkich możliwych zwycięstw poprzez sekwencję czwórek, jest skończony.


Mając na myśli aspekt praktyczny chyba nie chodzi nam o pieniądze, tylko o przełożenie tego na realia gomoku.

Mam więc pytania, do cytowanego stwierdzenia:

1. Skończony układ kamieni - czyli, jak rozumiem, jest ich znana ilość, np. 120?
2. Czy sekwencja czwórek może powstać i kilkadziesiąt ruchów później? (ale wtedy chyba zmierzamy w stronę nieskończoności)
3. Czy vcf to także jedna czwórka? (swoją drogą kiedyś w trakcie naszych dyskusji wypracowałem piękną definicję vcf i wysłalem na priv - masz ją jeszcze? :) )
4. Czy kamienie w tym skończonym układzie mają ustaloną pozycję na planszy, czy też możemy je przekładać?

Odpowiedzi na powyższe pytania dałyby mi możliwość przemyślenia poważnie tej kwestii. A na 1 000 000 USD i tak nie mam szans, więc próbuję od dwóch lat wygrać sobie jakiegoś oficjala :)

Pozdrawiam

Angst
 
 
 
ermijo 


Dołączył: 07 Maj 2005
Posty: 1950
Skąd: N49°37`E20°42`
Wysłany: 2007-10-14, 09:21   

Nie ma czegoś takiego jak nieskończony VCF, ponieważ aby wykonać jakiś VCF musi zaistnieć odpowiednia sytuacja na planszy już nie mówiąc o tym czy jest ona powstała naturalnie czy ułożona. Wydaje mi się również, że nie ma takiej początkowej sytuacji kamieni na planszy, żeby dysponując nieskończoną planszą, przy optymalnych ruchach utrzymać wartości funkcji oceniającej na stabilnym poziomie(mam na myśli stabilność na granicy oscylacji). Uważam, że układ kamieni nie pozostanie stabilny, gdyż jedna ze stron będzie miała przewagę. Ciężko za to powiedzieć, ile ruchów stanowi minimum do wyjścia z bardzo wyrównanej dla obydwu stron pozycji przechylając szale na zwycięstwo. Myślę też, że nie potrzeba przeglądać bardzo daleko(w sensie odległości od biorących udziału w gdzie kamieni) planszy. Jak tutaj wspomniano, ważne są brzegi zagrożeń czyli graniczne pozycje na planszy rozdzielające 2 obszary:

- obszar, w obrębie którego nie jesteśmy w stanie skutecznie zaatakować, gdyż będziemy "zamykani" czy tez otaczani przez przeciwnika
- obszar, w obrębie którego oddajemy przeciwnikowi zbyt duże pole a on rozbudowuje przewagę - np. jakiś długi ruch na 5 pól od właściwego układu...

Zatem wydawać się może, że ta ów granica między obszarami stanowi optymalne położenia przy kolejnych ruchach. Ale jak wygląda? Zauważyłem, że układa się ona w kształt konika szachowego lub też podwójnego konika szachowego. Ruch konikiem to przejęcie tempa - w przypadku pojedynczego ruchu konikiem, lub powiększanie przewagi wraz z kontrolą co może zrobić przeciwnik ruch "long horse", czyli np. 2 ruchy skoczka na szachownicy z punktu A do B jako jeden.
_________________
Always: "Homo ludens"
Never: "Homo faber"
 
 
Barfko 

Dołączył: 30 Kwi 2004
Posty: 556
Skąd: 49°25'N8°45'E
Wysłany: 2007-10-14, 11:44   

Cytat:
1. Skończony układ kamieni - czyli, jak rozumiem, jest ich znana ilość, np. 120?
2. Czy sekwencja czwórek może powstać i kilkadziesiąt ruchów później? (ale wtedy chyba zmierzamy w stronę nieskończoności)
3. Czy vcf to także jedna czwórka? (swoją drogą kiedyś w trakcie naszych dyskusji wypracowałem piękną definicję vcf i wysłalem na priv - masz ją jeszcze? :) )
4. Czy kamienie w tym skończonym układzie mają ustaloną pozycję na planszy, czy też możemy je przekładać?

Układamy na nieskończonej planszy w jakikolwiek sposób skończoną liczbę kamieni i rozpoczynamy robienie czwórek, które są blokowane. Fakt, o którym wspomniałem powiada, że układania kolejnych czwórek nie można kontynuować w nieskończoność. Czy jak kto woli, dla każdego układu na planszy istnieje ograniczenie górne na długość sekwencji czwórek. Czy jak kto woli dla każdej liczby kamieni istnieje ograniczenie górne długości sekwencji czwórek na planszy zależne tylko od liczby kamieni. Ruchy są wykonywane zgodnie z zasadami gomoku, więc nie można przestawiać w trakcie gry.

Angst, za VCF w gomoku zwykło się uważać sekwencję czwórek wykonywanych przez jednego z graczy i blokowanych przez drugiego prowadzącą do zwycięstwa. Zastanawianie się, czy jedną czwórkę (np. powstałą z otwartej trójki) można już uznać za VCF ma niewielkie znaczenie aż do momentu, gdy próbujemy podać definicją VCT. Wtedy warto przyjąć, że jedna czwórka może być VCF-em, bo skróci to istotnie definicję VCT, szczególnie w renju.

Granie w gomoku w ogóle ma niewielkie znaczenie praktyczne. Jest to rozrywka umysłowa. Podobną rozrywką umysłową jest rozwiązywanie problemów inspirowanych gomoku. W świecie rzeczywistym obserwujemy różne wydarzenia starając się znaleźć zbiór możliwie prostych reguł, z na podstawie których da się te zdarzenia wytłumaczyć. Zagadnienie jest nieuchwytne, ale nieustannie popycha ludzi naprzód. Z gomoku jest na odwrót. Reguły już znamy i są proste, można więc pytać, jakie są możliwe zdarzenia odwracając tym samym całą zabawę.
_________________
O-jôzu desu ne!
 
 
Wyświetl posty z ostatnich:   
Odpowiedz do tematu
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Nie możesz załączać plików na tym forum
Możesz ściągać załączniki na tym forum
Dodaj temat do Ulubionych
Wersja do druku

Skocz do:  

Powered by phpBB modified by Przemo © 2003 phpBB Group