Drzewo gry

Witam.

Chodzi o to jak sie pisze drzewo gry (czyli wszystkie mozliwosci wyboru)...
szukalem w necie i nic nie ma sa tylko grafy itp... sama teoria i 0 przykladow z wykorzystaniem w praktyce.
Ma ktos moze jakis przyklad? np. moga byc szachy

Pewno trzeba użyć jakiegoś przeszukiwania. Pewno z jakimiś strategiami usprawniającymi, żeby jakaś maszyna na świecie była w stanie to przetworzyć w realnym czasie.
Trochę jest tu: http://osilek.mimuw.edu.pl/index.php?title=Sztuczna_inteligencja/SI_Modu%C5%82_8_-_Gry_dwuosobowe
A więcej trzeba szukać po angielsku raczej.

P.S. Szachy to świetny przykład na początek, naprawdę :-D

Drzewo to tez graf, stad pewnie ta 'sama teoria'. Poza tym rozpisanie wszystkich mozliwosci chyba nie jest takie trudne, co? Przeciez to intuicyjne napisac rozrysowac takie drzewo. Czy raczej problem z implementacja drzewa w ogolnosci?

PS. Rzeczywiscie, szachy to idealny, prosty i przejrzysty przyklad :P

no wiem ze szachy do prostych nie naleza... ale ponoc duzo przykladow z tej gry jest :](bo popularna gra)... tylko jakos zadnego nie znalazlem :].

johny_bravo napisał(a)

Poza tym rozpisanie wszystkich mozliwosci chyba nie jest takie trudne, co? Przeciez to intuicyjne napisac rozrysowac takie drzewo. Czy raczej problem z implementacja drzewa w ogolnosci?

hm no raczej jest trudne jesli sie ma to zrobic samodzielnie tzn recznie... bo np wezlow moze byc kilka tysiecy :], dlatego szukam jakis przykladow.
Moze macie jakis pomysly jak to napisac.

somekid - juz to czytalem, ale thx za pomoc

Nie zrozumiales mnie ;)

Ja Ci nie kaze rozrysowywac calego drzewa szachow bo i program mialby z tym problem.

To czego potrzebujesz to:

1. narysuj sobie na kartce 2-3 poziomy decyzyjne
2. Uzyj zwyklej struktury drzewa pasujacej do tego co narysowales
3. Okresl zasady mowiace jak powstaje nowy poziom/galaz

I juz masz program gotowy. I nie bierz sie za szachy, dobrze Ci radze. Wez sobie np. prosta gre w karty albo chocby kolko i krzyzyk (tam tez jest wbrew pozorom sporo mozliwosci).

No i pytanie po co Ci to drzewo - zeby program zagral w ta gre czy zeby Ci zapisal to co policzyl do pliku?

Acha - no i oczywiste jest, ze drzewo sklada sie zarowno z Twoich ruchow jak i ruchow przeciwnika.

johny_bravo napisał(a)

I nie bierz sie za szachy, dobrze Ci radze. Wez sobie np. prosta gre w karty albo chocby kolko i krzyzyk (tam tez jest wbrew pozorom sporo mozliwosci).

No i pytanie po co Ci to drzewo - zeby program zagral w ta gre czy zeby Ci zapisal to co policzyl do pliku?

Acha - no i oczywiste jest, ze drzewo sklada sie zarowno z Twoich ruchow jak i ruchow przeciwnika.

Dokladniej to juz zrobilem gre... tylko chcialbym dodac by nie gral tylko gracz vs gracz tylko gracz vs komputer.
Za szachy sie nie biore bo jeszcze nie jestem na takim etapie :), jakbym byl to pewnie bym nie zadal takiego pytania:]

thx za podpowiedzi... postaram sie tak zrobic jak nie wyjdzie ... to wroce :D.
Tak przy okazji jakby ktos mial jakis pomysl ... albo przyklad to smialo pisac... nie krepowac sie :).

To powiedz jeszcze jaka to gra (i zasady podaj, gdyby byla jakas mniej znana).

Co do tego, ze chcesz, zeby komputer gral. W tym wypadku drzewo jest mniej istotne. Bardziej istotna jest funkcja oceny i to na niej sie skup (chociaz drzewko jest pomocna implementacja). Chodzi o funkcje, ktora na podstawie roznych parametrow oceni 'wartosc' ruchu.

Przykladowo masz drzewko dla kolka-krzyzyka, gdzie startujesz Ty i grasz kolkami:

1. poziom - stawiasz kolko na jednej z 9 pozycji, zatem 1. poziom zawiera 9 elementow.
2. poziom - przeciwnik stawia krzyzyk, zatem 2 poziom do 9x po 8 elementow - czyli krzyzyki w miejscach gdzie przeciwnik moze je postawic.
3. poziom stawiasz kolko, zatem sklada sie z 9x8 po 7 elementow z kolkami w mozliwych miejscach

i tak dalej. I co to daje komputerowi? Nic, poki co. Komputer potrzebuje teraz na podstawie tego drzewka ocenic ktory ruch na 1 poziomie jest najlepszy. Idealna funkcja oceny zawiera cale drzewko decyzyjne - czyli tutaj teoretycznie 9! na ostatnim poziomie i zaznaczone sciezki prowadzace do wygranej. Teoretycznie, bo gra czasem konczy sie wczesniej. Komputer moze przyjac, ze najlepsza jest najkrotsza sciezka, ktora konczy sie wygrana (jak jest ich kilka to losuje z nich). To srednia strategia w tej grze, bo tutaj komputer musialby grac z idiota, przykladowo jak komputer zaznaczy 2 kolka w rzedzie to przeciwnik go nie zastopuje krzyzykiem. Lepiej przyjac na przyklad, ze najlepsza sciezka to ta, ktora ma srednia dlugosc i konczy sie wygrana oczywiscie.

Najlepiej pewnie byloby przyjac ta sciezke, ktora prowadzi do wezla, ktory ma najwiecej dzieci-wygranych. Bo stad gracz jeszcze moze nie wiedziec, ze przegral a statystycznie do tego dazy.

Oczywiscie w grach takich jak szachy nie ma pelnego drzewa, stad funkcja oceny operuje na innych danych, np. ilosc moich figur w srodku pola, ktore ma najwyzsza 'moc' strategiczna, wagi poszczegolnych posiadanych figur - wiadomo, ze pionek jest slabszy niz krolowa, itp. Do tego w szachach na przyklad stosuje sie tablice otwarcia i zamkniecia, czyli obliczone juz i zapisane w pamieci najlepsze rozpoczecia i zamkniecia gry, gdzie te drugie oczywiscie przy pewnym okreslonym stanie gry(np. krol i pionek kontra krol i wieza, itp)

Tak wyglada teoria i troszke praktyki ;)

gra i zasady mniej wiecej wygladaja tak: (nie wiem czy kiedykolwiek taka gra byla... sam ja wymyslilem):
-mamy 4 rzedow kresek (w 1 rzedzie jest ich 8, w drugim 5, trzeciem 3 i ostatnim 1 kreska)

• w 1 ruchu mozna skreslic dowolna ilosc kresek w dowolnym rzedzie, ale tylko w nim.
• kro skresli ostatnia kreske ten przegrywa.

|

johny_bravo napisał(a)

Ja Ci nie kaze rozrysowywac calego drzewa szachow bo i program mialby z tym problem.

Program może nie. Raczej nigdzie nie ma tyle pamięci, żeby to drzewo zmieścić ;)

johny_bravo napisał(a)

To czego potrzebujesz to:

1. narysuj sobie na kartce 2-3 poziomy decyzyjne

Dla szachów to by był chyba tydzień roboty :D Przecież już po pierwszym ruchu jest 400 kombinacji bierek na planszy.

@somekind: dlatego napisalem przyklad na kolku i krzyzyku. A pozniej napisalem dlaczego szachy to troche inna bajka ;)

Acha, to nie pamiec jest problemem w szachach a ilosc obliczen, bo zapisywanie tego drzewa zajeloby chyba wiecznosc ;)

johny_bravo napisał(a)

Acha, to nie pamiec jest problemem w szachach a ilosc obliczen, bo zapisywanie tego drzewa zajeloby chyba wiecznosc ;)

Ilość obliczeń pewno też, ale to drzewo jest "raczej duże", ciężko chyba byłoby wszystkie węzły przechowywać w jakiejś pamięci. Chyba, że ja źle do pojmuję...
Dobra, bo się offtop robi ^^

To jeszcze jedno do offtopu i koncze. Z pamiecia to jest tak, ze duzo latwiej dolozyc 100 dyskow po 0,5 TB niz zmniejszyc zlozonosc algorytmu (a tym samym czas wykonania). Zreszta po szachach bylo to widac, bo DeepBlue wygral z Kasparowem miedzy innymi dzieki wczesniej przygotowanym mini-drzewom. Mial spora baze zapisanych partii, stad czesc obliczen byla juz zbedna. I koniec OT :)

@autor: co do Twojej gry to mozesz postepowac tak jak przedstawilem to z kolkiem i krzyzykiem i powinno byc ok :)