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
Rozpoczęcie wygrywające
Autor Wiadomość
Artur Wydra 

Dołączył: 28 Kwi 2005
Posty: 1
Skąd: Kraków
Wysłany: 2005-04-28, 19:44   Rozpoczęcie wygrywające

Witam!

Zna ktoś algorytm jak można wygrać w Gomoku (zwykłym) rozpoczynając ruch. Podobno coś takiego jest. Nauczycielka od majcy powiedziała, że da mi 5 na koniec jak dam jej ten sposób :D
 
 
 
soul_reaper 
retired


Dołączył: 28 Kwi 2004
Posty: 889
Skąd: Kraków
Wysłany: 2005-04-28, 20:00   

Jak chcesz moge podeslac Ci prace doktorska Victora Allisa w ktore podal on dowod na istnienie pewnego zwyciestwa w standardowym gomoku.
Natomiast algorytmu jako takiego raczej nikt Ci nie poda. Allis przeprowadzil swoj dowod podajac wszystkie mozliwe kombinacje ruchow za pomoca programu Victoria. Program ten korzysta z bazy danych otwarc oraz bardzo mocnego algorytmu zwanego threat-space search analysis. Posiada on ponadto funkcje oceniajaca pozycje w przypadku nie znalezienia sekwencji wygrywajacej pierwsza metoda.
Rowniez z tego co wiem, Istvan Virag napisal program potrafiacy znajdowac sure win, ale nie jestem tego pewny.
 
 
 
kashon 

Dołączył: 30 Kwi 2004
Posty: 282
Skąd: Warszawa/B-stok
Wysłany: 2005-04-28, 20:31   

na stronie gomoku.pl znajdziesz w dziale renlib biblioteki z opracowanymi wygranymi (sure wins) dla 2 otwarc - d4 oraz i11.

kashon
 
 
 
jopq 
retired


Dołączył: 10 Cze 2004
Posty: 737
Skąd: Warszawa
Wysłany: 2005-04-28, 22:55   

Sure Win? Jeszcze go nie znasz? www.gomoku.boo.pl/sure_win

"majcy" czego Ty się w szkole uczysz, hehe
 
 
bad_mojo 
recenzent ludzkości


Dołączył: 10 Lip 2004
Posty: 1569
Skąd: Konstancin-Jez.
Wysłany: 2005-04-28, 22:58   

Śmieszne, ale właśnie zauważyłem, że Piskv nie widzi całego sw :]
_________________
Think for yourself. Question authority. / People tell me what to say, what to think and what to play.
 
 
 
Barfko 

Dołączył: 30 Kwi 2004
Posty: 556
Skąd: 49°25'N8°45'E
Wysłany: 2005-04-28, 23:22   

Wszystko zależy od tego jak twoja pani od majcy sformułowała zagadnienie.

1. Gdyby to było : "Podaj algorytm wygrywający", wówczas zagadnienie jest banalne. Polega na przeszukaniu całego drzewa gry. Algorytmy przeszukujące drzewa są dość proste.

2. Gdyby to było : "Podaj algorytm wygrywający i udowodnij jego poprawność", wówczas nieco gorzej. Algorytm z pktu 1. wciąż działa. Ale trzeba jeszcze wykazać, że czarne mają SW. Takiego dowodu w sensie ścisłym nie ma, ale jest "dowód komputerowy" polegający na wskazaniu bardzo małego poddrzewa drzewa gry, w którym jest zawarta informacja o SW. Dowód ten jest w pracy, o której wspomniał soul.

3. Gdyby chodziło o podanie algorytmu działającego w rozsądnym czasie, na przykład z ograniczeniem liczby operacji bitowych na ruch (powiedzmy < 10000000000 operacji), wówczas kłopot jest poważny, ale z użyciem istniejącego oprogramowania i istniejących bibliotek RenLibowych jest to wykonalne. W bibliotekach, o których wspomniał kashon, jest zawarta informacja o SW z dokładnością do VCT. Żeby mieć algorytm, wystarczy więc napisać funkcję szukającą VCT (nie jest to trudne) i użyć te biblioteki (plus kilka bibliotek z banalnymi SW, gdy białe grają pierwszy ruch dalej). Wszystkie potrzebne biblioteki to jakieś kilka tysięcy ruchów.

4. Gdyby chodziło o podanie algorytmu, o którym mowa w 3. wraz z dowodem jego poprawności, wówczas należy wręczyć pani od majcy pracę doktorską, o której wspomniał soul. Zaletą ostatniego rozwiązania jest mała złożoność czasowa algorytmu (dużo mniejsza od poszukiwania VCT z pkt. 3), za to złożoność pamięciowa byłaby kilkadziesiąt razy większa niż w pkcie 3 - trzeba by było zapamiątać około 300000 ruchów.

Wystarczy więc teraz poprosić panią od majcy, żeby zagadnienie sformułowała na piśmie i mieć nadzieję, że chodzi rozwiązanie z pktu 1., lub z punktu 2. W takim wypadku wystarczy kilka linijek tekstu do wykazania następującego twierdzenia:

Tw1. Jeśli czarne mają SW, to algorytm przeszukujący całe drzewo gry jest dobry.

To twierdzenie wzmocnione wynikiem Allisa

Tw2. Czarne mają SW.

daje twierdzenie

Tw 3. Algorytm przeszukujący całe drzewo gry znajduje SW czarnych.

Oczywiście, gdyby pani od majcy chciała sobie na kurniku rank nabić, to dowód powyższy w tym jej nie pomoże. Hehe.
 
 
ermijo 


Dołączył: 07 Maj 2005
Posty: 1950
Skąd: N49°37`E20°42`
Wysłany: 2005-05-07, 18:11   

Hmm... bardzo dziwna nauczycielka matematyki, a może to była informatyka lub logika ?

Moja teoria na temat SW czarnych w grze gomoku typu standard, jest może trochę "since fiction" , ale uważam, że jeśli chodzi o planszę 15x15, teoretycznie paria zawsze jest remisem. Zawsze można, koncentrując się na grze, nastawić się na remis, co częto stosują tzw. blokersi w grze na 1 min. Zgodziłbym się, że instnieje "pozorne SW" czarnych dla nieskończonego czasu i nieskończonej planszy. Myślę, że z czasem zmierzającym do nieskończoności, czarne zyskują przewagę stopniopwo ( nie wiem wegdług jakiej funkcji, może wykładniczej) , ale nigdy nie wygrają.

Wracajac do gry standard - przeprowadzałem analizy. Symulowałem gry nastepującymi programami: w roli czarnych - CARBON Gomoku, w roli białych FIVER. Programy miały ustawiony najlepszy poziom gry. Okazało się, że rzeczywiście większość partii wygrywały czarne, ale zwykle było to po 40 - 50 ruchach. Można by było przeprowadzić badanie, - sprawdzić zależność ilości ruchów kończących grę od rozmiaru planszy. Wiadomo, że w polu 7x7 ze zrobieniem remisu nie będzie miał problemu nawet człowiek. A przy nieskończonej mocy obliczeniowej ? :twisted: Myślę że nawet pole 10000000x10000000 by nie wystarczyło na wygraną czarnych.

Ponieważ gomoku to gra ograniczona wymiarem planszy i jakimś czasem, gra standard dla graczy idealnych (teoria) prowadziłąby do remisu przy rosnącej przewadz czarnych.
Zatem jak dla mnie to w teorii SW , praktyce zawsze remis a w ludzkich umiejętnościach zawsze wygrana czarnych dla "niemałej planszy".
_________________
Always: "Homo ludens"
Never: "Homo faber"
 
 
angst 
Członek Zarządu
Kapitan IRP

Dołączył: 28 Kwi 2004
Posty: 4998
Skąd: Płock
Wysłany: 2005-05-07, 18:32   

Przy optymalnej grze w wersji standard czarne maja oczywista wygrana nawet przy optymalnej obronie bialych. I plansza 15x15 spokojnie wystarczy. Zostalo to udowodnione jakies 25 lat temu i pewnie juz wspomniano o tym w ktoryms z powyzszych postow.

Pozdrawiam

Angst

P.S. Akurat grac Carbonem czarnymi to nie byl zbyt dobry pomysl, bo spokojnie mozna go ograc bialymi (no moze nie az tak spokojnie dla przecietnego gracza ;) ).
 
 
 
nc 

Dołączył: 05 Maj 2004
Posty: 297
Skąd: Zielona Góra
Wysłany: 2005-05-07, 18:38   

Ermijo, zamiast teorii proponuję praktykę, pograj sobie na kurniku, standard jak dojdziesz (bez nabijania) np. do reda to uznam to za dowód Twojej teorii :roll:

a tak serio to proszę:
ermijo napisał/a:
Jak chcesz moge podeslac Ci prace doktorska Victora Allisa w ktore podal on dowod na istnienie pewnego zwyciestwa w standardowym gomoku.
 
 
 
ermijo 


Dołączył: 07 Maj 2005
Posty: 1950
Skąd: N49°37`E20°42`
Wysłany: 2005-05-07, 18:49   

Bardzo chętnie zapoznam sie z tym dowodem, może Cię złapię na kurniku kiedyś


--- Pozdawiam
_________________
Always: "Homo ludens"
Never: "Homo faber"
 
 
bad_mojo 
recenzent ludzkości


Dołączył: 10 Lip 2004
Posty: 1569
Skąd: Konstancin-Jez.
Wysłany: 2005-05-07, 20:23   

Nie wiem o czym jest tu rozmowa, bo to jest udowodnione, że czarne mają sw w standardzie, i to nawet w renju, gdzie czarnym jest dużo gorzej...
_________________
Think for yourself. Question authority. / People tell me what to say, what to think and what to play.
 
 
 
jopq 
retired


Dołączył: 10 Cze 2004
Posty: 737
Skąd: Warszawa
Wysłany: 2005-05-08, 13:44   

Bez dwóch zdań czarne mają wygraną w wersji standard. Nie wiem tylko co ma do tego czas i czy moc obliczeniowa go skraca? Bo przecież przy nieskończonej mocy obliczeniowej wymaganay czas dąży do 0. Czas sobie leci...
Nie można brać go jako parametru przy stwierdzaniu suchych faktów, które skoro były do udowodnienia wiele lat temu, to dziś przy dużo lepszych możliwościach obliczeniowych naszych komputerów powinny być o oczywiste i łatwe do ponownego przeliczenia (problem pozostaje w dobrze zooptymalizowanym algorytmie).

15x15 spokojnie wystarcza, nawet ostatnio grałem z kilkoma graczami na standard i nie byłem w stanie zablokować jednego z podstawowych wyjść. Warto zobaczyć na otwarcia renju, gdyż te które mają oznaczenia sw, to w gomoku bedza one duzo prostsze do opanowania, a wrecz calkowitego rozpracowania.

PS dowód jest w necie, google...

pozdrawiam, jopq
 
 
Ece 
Wielki Admin ;)


Dołączył: 27 Kwi 2004
Posty: 1680
Skąd: Dublin
Wysłany: 2005-05-08, 17:22   

jopq napisał/a:
Warto zobaczyć na otwarcia renju, gdyż te które mają oznaczenia sw, to w gomoku bedza one duzo prostsze do opanowania, a wrecz calkowitego rozpracowania.

To poprosze o rozpracowanie D13 i I13 dla Gomoku - SW dla bialych w Renju :]
 
 
 
jopq 
retired


Dołączył: 10 Cze 2004
Posty: 737
Skąd: Warszawa
Wysłany: 2005-05-09, 20:11   

Mając na myśli sw w gomoku, udowadniające wygraną dla koloru czarnego, nie można brać pod uwagę D13 i I13, które wykorzystują faule. Myśl przewodnia jest taka, że jeśli czarne wygrywają z białymi w renju, to w gomoku tym bardziej. W przypadku białych sytuacja jest zupełnie inna, bo wsw w renju moze nic nie znaczyć, a nawet okazać sie bsw.

Pozdrawiam
 
 
zukole 

Dołączył: 04 Paź 2004
Posty: 4356
Skąd: Polska
Wysłany: 2014-10-30, 00:13   

soul_reaper napisał/a:
Allis przeprowadzil swoj dowod podajac wszystkie mozliwe kombinacje ruchow za pomoca programu Victoria. Program ten korzysta z bazy danych otwarc oraz bardzo mocnego algorytmu zwanego threat-space search analysis. Posiada on ponadto funkcje oceniajaca pozycje w przypadku nie znalezienia sekwencji wygrywajacej pierwsza metoda.
Trochę więcej - http://www.mimuw.edu.pl/~...iechna/tss.html
Cytat:
Przez zrobienie tego raz i zapamiętanie wyników w bazie danych rozwiązano grę Go-Moku!
Taaa :P
 
 
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