Hej

Mamy daną jakąś grę z niepełną informacją, np. grę
karcianą w tysiąca. Dysponujemy komputerem z dowolnie
dużą mocą obliczeniową. Trzeba napisać algorytm którego
na dłużą metę (w dużej ilości gier) nie pokona żaden
inny algorytm, a co najwyżej z nim zremisuje. Jaki to
powinien być algorytm?

Niby znam odpowiedź na to pytanie. Niby wystarczy dla wielu
losowych rozdań przeszukać drzewo gry. Ale jakoś nie potrafię
uwzględnić w tym wszystkim informacji z poprzednich ruchów i
blefowania.

Zwykle zakładamy że nasi przeciwnicy zagrają optymalnie. Załóżmy
że jeden z przeciwników w pierwszym ruchu kładzie np. asa kier.
Co powinien w takiej sytuacji zrobić optymalny algorytm? Chyba
powinien przeanalizować wszystkie możliwe rozdania i następnie
wziąć tylko te w których położenie asa kier jest dla naszego
przeciwnika ruchem optymalnym. W ten sposób algorytm zawęzi
zbiór możliwych kart jakie może posiadać nasz przeciwnik. Wszystko
byłoby pięknie, gdyby nasz przeciwnik nie wiedział o tym, że
właśnie dokonamy takiej analizy. Więc nasz przeciwnik czasami
wykona ruch nieoptymalny właśnie po to, aby taka analiza przynosiła
nam możliwie mało korzyści.

No i właśnie tutaj się gubię. Jaki algorytm zagra optymalnie w
tysiąca? Jaki algorytm będzie optymalnie blefował i uwzględniał
optymalne blefowanie u przeciwników?

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

On Tuesday, May 8, 2012 10:18:07 PM UTC+1, M.M. wrote:
> Hej
>
> Mamy dan� jak�� gr� z niepe�n� informacj�, np. gr�
> karcian� w tysi�ca. Dysponujemy komputerem z dowolnie
> du�� moc� obliczeniow�. Trzeba napisa� algorytm kt�rego
> na d�u�� met� (w du�ej ilo�ci gier) nie pokona �aden
> inny algorytm, a co najwy�ej z nim zremisuje. Jaki to
> powinien byďż˝ algorytm?
>
> Niby znam odpowiedďż˝ na to pytanie. Niby wystarczy dla wielu
> losowych rozdaďż˝ przeszukaďż˝ drzewo gry. Ale jakoďż˝ nie potrafiďż˝
> uwzgl�dni� w tym wszystkim informacji z poprzednich ruch�w i
> blefowania.
>
> Zwykle zak�adamy �e nasi przeciwnicy zagraj� optymalnie. Za��my
> �e jeden z przeciwnik�w w pierwszym ruchu k�adzie np. asa kier.
> Co powinien w takiej sytuacji zrobiďż˝ optymalny algorytm? Chyba
> powinien przeanalizowa� wszystkie mo�liwe rozdania i nast�pnie
> wzi�� tylko te w kt�rych po�o�enie asa kier jest dla naszego
> przeciwnika ruchem optymalnym. W ten spos�b algorytm zaw�zi
> zbi�r mo�liwych kart jakie mo�e posiada� nasz przeciwnik. Wszystko
> by�oby pi�knie, gdyby nasz przeciwnik nie wiedzia� o tym, �e
> w�a�nie dokonamy takiej analizy. Wi�c nasz przeciwnik czasami
> wykona ruch nieoptymalny w�a�nie po to, aby taka analiza przynosi�a
> nam mo�liwie ma�o korzy�ci.
>
> No i w�a�nie tutaj si� gubi�. Jaki algorytm zagra optymalnie w
> tysi�ca? Jaki algorytm b�dzie optymalnie blefowa� i uwzgl�dnia�
> optymalne blefowanie u przeciwnik�w?

Podobne problemy czesto rozwiazuje sie w matematyce finansowej. Jezeli zalozysz, ze
gra trwa maksymalnie N ruchow (to chyba jest prawda dla tysiaca?), to drzewko gry
mozesz po prostu przejsc od konca. To powinno uwzglednic blefy.
Poczytaj o metodach wyceny opcji amerykanskich na drzewach i metoda "least squares
Monte Carlo".

RW

do góry

Roman W <b...@g...pl> napisał(a):

> Podobne problemy czesto rozwiazuje sie w matematyce finansowej. Jezeli
> zalozysz, ze gra trwa maksymalnie N ruchow (to chyba jest prawda dla
> tysiaca?), to drzewko gry mozesz po prostu przejsc od konca. To powinno
> uwzglednic blefy.
> Poczytaj o metodach wyceny opcji amerykanskich na drzewach i metoda "least
> squares Monte Carlo".

Może gra w tysiąca do wyrobienia sobie wstępnego poglądu jest nadal zbyt
rozbudowana. Może powinienem posłużyć się jakąś prostszą grą. Z kolei
nie wiem czy prostszej grze stosowanie blefów będzie miał jakikolwiek
sens...

Może taka gra:
1) Jest dwóch graczy, jeden gracz nazywa się A, drugi B.
2) Grają małą talią od dziewiątek do asów, czyli używaj 24 kart.
3) Karty rozdaje na przemian gracz A i B.
4) W trakcie rozdawania każdy gracz otrzymuje tylko 3 losowe karty z talii.
5) Pierwszy wykłada kartę na stół gracz rozdający, potem ten który wziął
poprzednią lewę.
6) Jest obowiązek dokładania do koloru, jeśli gracz nie kładzie karty w
tym samym kolorze, to przegrywa. Jeśli dokłada do koloru to wygrywa
ten który położył starszą kartę.
7) Ten gracz który weźmie więcej lew zdobywa 1 punkt. Drugi gracz
zdobywa zero punktów. Po czym na nowo są rozdawane 3 karty.
8) Cała rozgrywka składa się z bardzo dużej ilości rozdań, z tylu aby
można było wyeliminować wygrane dzięki szczęściu. Wygrywa ten który
gra lepiej.

Drzewko takiej gry jest małe. Na początku, zaraz po rozdaniu kart, pierwszy
gracz ma do dyspozycji 3 ruch. Drugi gracz na początku też ma trzy ruchy.
Potem obaj mają do dyspozycji po 2 ruch, a gdy zostaje im już jedna karta to
nie mają możliwości wyboru, obaj muszą położyć ostatnią kartę jaka im została.

Tak więc drzewo ma 3*3*2*2=9*4=36 węzłów. Każdy domowy komputer takie drzewo
może przeszukać miliony razy i do woli może robić symulacje MC.

Jak powinien wyglądać algorytm który nigdy nie przegra w taką grę?
Interesuje mnie taki algorytm wraz z dowodem matematycznym że jest
algorytmem optymalnym.

Pozdrawiam



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Dnia Wed, 09 May 2012 09:58:21 +0000, M.M. napisal:

> Roman W <b...@g...pl> napisał(a):
>
>> Podobne problemy czesto rozwiazuje sie w matematyce finansowej. Jezeli
>> zalozysz, ze gra trwa maksymalnie N ruchow (to chyba jest prawda dla
>> tysiaca?), to drzewko gry mozesz po prostu przejsc od konca. To powinno
>> uwzglednic blefy.
>> Poczytaj o metodach wyceny opcji amerykanskich na drzewach i metoda "least
>> squares Monte Carlo".
>
> Może gra w tysiąca do wyrobienia sobie wstępnego poglądu jest nadal zbyt
> rozbudowana. Może powinienem posłużyć się jakąś prostszą grą. Z kolei
> nie wiem czy prostszej grze stosowanie blefów będzie miał jakikolwiek
> sens...
>
> Może taka gra:
[...]
>
> Jak powinien wyglądać algorytm który nigdy nie przegra w taką grę?
> Interesuje mnie taki algorytm wraz z dowodem matematycznym że jest
> algorytmem optymalnym.

Tit-for-tat przeradza się w tit-for-tat-if-cannot-abuse-opponent.
W psychologii trudno o dowody formalne.

Edek

do góry

On Wednesday, May 9, 2012 10:58:21 AM UTC+1, M.M. wrote:

> Jak powinien wyglądać algorytm który nigdy nie przegra w taką grę?
> Interesuje mnie taki algorytm wraz z dowodem matematycznym że jest
> algorytmem optymalnym.

Poniewaz gra zawiera element losowy, dowolny algorytm moze przegrac, jesli dostanie
bardzo slabe karty w rozdaniu. Dopiero w granicy nieskonczonej liczby rozgrywek
mozesz miec gwarantowana wygrana.

Google for "Snell envelope".

RW

do góry

Edek Pienkowski <e...@g...com> napisał(a):

> Dnia Wed, 09 May 2012 09:58:21 +0000, M.M. napisal:
>
> > Roman W <b...@g...pl> napisał(a):
> >
> >> Podobne problemy czesto rozwiazuje sie w matematyce finansowej. Jezeli
> >> zalozysz, ze gra trwa maksymalnie N ruchow (to chyba jest prawda dla
> >> tysiaca?), to drzewko gry mozesz po prostu przejsc od konca. To powinno
> >> uwzglednic blefy.
> >> Poczytaj o metodach wyceny opcji amerykanskich na drzewach i metoda "least
> >> squares Monte Carlo".
> >
> > Może gra w tysiąca do wyrobienia sobie wstępnego poglądu jest nadal zbyt
> > rozbudowana. Może powinienem posłużyć się jakąś prostszą grą. Z kole
> i
> > nie wiem czy prostszej grze stosowanie blefów będzie miał jakikolwiek
> > sens...
> >
> > MoĹźe taka gra:
> [...]
> >
> > Jak powinien wyglądać algorytm który nigdy nie przegra w taką grę?
> > Interesuje mnie taki algorytm wraz z dowodem matematycznym Ĺźe jest
> > algorytmem optymalnym.
>
> Tit-for-tat przeradza się w tit-for-tat-if-cannot-abuse-opponent.
> W psychologii trudno o dowody formalne.

Zróbmy coś, aby wyeliminować psychologię :)

Można to rozpatrywać w postaci dwuwymiarowej tabeli. W poziomie i
w pionie mamy kolejne programy, a w komórce na skrzyżowaniu
wiersza x z kolumną y mamy wynik jaki uzyskuje program x grając
przeciwko programowi y. Jeśli w komórce jest 100% to znaczy
że x wygra wszystkie gry bez względu na to jak zostały rozdane
karty.

Moje pierwsze pytanie chyba można sprowadzić do tego, czy dla danej
gry istnieje program który ma minimalną wartość 50% ( minimalną, czyli
obojętnie z jakim programem zagra, to uzyskuje 50% lub więcej.).

W różnych grach czynnik blefu może mieć różne skutki. Nie wiem w
tej chwili czy są gry z niepełną informacją w których czynnik blefu
nigdy nie poprawi wyniku. Jeśli takie gry są, to w nich należy grać
optymalnie i należy zakładać że przeciwnik zagra/zagrał optymalnie.
Myślę że dla takich gier istnieją programy które minimalną wartość w
powyższej tabeli będą miały właśnie 50%.

Natomiast dla gier w których blefowanie może pomóc taki algorytm
raczej nie istnieje. Chyba dla każdej strategii blefowania
można napisać taką strategię która osiągnie ponad 50%.

Dobrze myślę czy źle?

Ponadto rodzą się kolejne problemy.

Po pierwsze jak ocenić czy w danej grze czynnik blefu ma duże znaczenie czy
małe? A jeśli już ocenimy jakie ma znaczenie, to jak wpleść w
algorytm choćby jakieś najprostsze szacowanie sposobu blefowania przeciwnika?

W grach karcianych gdy jest już po rozgrywce to dowiadujemy się jakie
karty otrzymał przeciwnik. Pamiętamy także jak dokładał karty. Może należy
zawsze grać optymalnie, a blef oceniać tylko u przeciwnika? Można obliczyć
jak odległa była strategia obrana przez przeciwnika od strategii
optymalnej i zakładać jakąś średnią ważoną z N ostatnich rozdań?

Wydaje się sensowne jeśli program całkowicie zaniecha blefowania a będzie
grał zawsze optymalnie. Jeśli program zdoła oszacować poziom blefowania
przeciwnika (a tym samym poziom umiejętności gry przeciwnika) to zagra
optymalnie do oszacowanego poziomu.


Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

On Wednesday, May 9, 2012 2:14:58 PM UTC+1, M.M. wrote:
> Edek Pienkowski <e...@g...com> napisał(a):
>
> > Dnia Wed, 09 May 2012 09:58:21 +0000, M.M. napisal:
> >
> > > Roman W <b...@g...pl> napisał(a):
> > >
> > >> Podobne problemy czesto rozwiazuje sie w matematyce finansowej. Jezeli
> > >> zalozysz, ze gra trwa maksymalnie N ruchow (to chyba jest prawda dla
> > >> tysiaca?), to drzewko gry mozesz po prostu przejsc od konca. To powinno
> > >> uwzglednic blefy.
> > >> Poczytaj o metodach wyceny opcji amerykanskich na drzewach i metoda "least
> > >> squares Monte Carlo".
> > >
> > > Może gra w tysiąca do wyrobienia sobie wstępnego poglądu jest nadal zbyt
> > > rozbudowana. Może powinienem posłużyć się jakąś prostszą grą. Z kole
> > i
> > > nie wiem czy prostszej grze stosowanie blefów będzie miał jakikolwiek
> > > sens...
> > >
> > > MoĹźe taka gra:
> > [...]
> > >
> > > Jak powinien wyglądać algorytm który nigdy nie przegra w taką grę?
> > > Interesuje mnie taki algorytm wraz z dowodem matematycznym Ĺźe jest
> > > algorytmem optymalnym.
> >
> > Tit-for-tat przeradza się w tit-for-tat-if-cannot-abuse-opponent.
> > W psychologii trudno o dowody formalne.
>
> Zróbmy coś, aby wyeliminować psychologię :)

Zaloz funkcje uzytecznosci wygranej/przegranej dla kazdego gracza, a potem zakladaj,
ze gracze maksymalizuja oczekiwana uzytecznosc.

RW

do góry

Dnia Wed, 09 May 2012 13:14:58 +0000, M.M. napisal:

> Edek Pienkowski <e...@g...com> napisał(a):
>
>> Dnia Wed, 09 May 2012 09:58:21 +0000, M.M. napisal:
>>
>> > Roman W <b...@g...pl> napisał(a):
>> >
>> >> Podobne problemy czesto rozwiazuje sie w matematyce finansowej. Jezeli
>> >> zalozysz, ze gra trwa maksymalnie N ruchow (to chyba jest prawda dla
>> >> tysiaca?), to drzewko gry mozesz po prostu przejsc od konca. To powinno
>> >> uwzglednic blefy.
>> >> Poczytaj o metodach wyceny opcji amerykanskich na drzewach i metoda "least
>> >> squares Monte Carlo".
>> >
>> > Może gra w tysiąca do wyrobienia sobie wstępnego poglądu jest nadal zbyt
>> > rozbudowana. Może powinienem posłużyć się jakąś prostszą grą. Z kole
>> i
>> > nie wiem czy prostszej grze stosowanie blefów będzie miał jakikolwiek
>> > sens...
>> >
>> > MoĹźe taka gra:
>> [...]
>> >
>> > Jak powinien wyglądać algorytm który nigdy nie przegra w taką grę?
>> > Interesuje mnie taki algorytm wraz z dowodem matematycznym Ĺźe jest
>> > algorytmem optymalnym.
>>
>> Tit-for-tat przeradza się w tit-for-tat-if-cannot-abuse-opponent.
>> W psychologii trudno o dowody formalne.
>
> Zróbmy coś, aby wyeliminować psychologię :)

Tu nie tylko o psychologię chodzi; na poziomie gry służy do "wykorzystania"
algorytmu przeciwnika. Nawet optymalnego.

>
> Można to rozpatrywać w postaci dwuwymiarowej tabeli. W poziomie i
> w pionie mamy kolejne programy, a w komórce na skrzyżowaniu
> wiersza x z kolumną y mamy wynik jaki uzyskuje program x grając
> przeciwko programowi y. Jeśli w komórce jest 100% to znaczy
> że x wygra wszystkie gry bez względu na to jak zostały rozdane
> karty.

Są takie gry, gdzie istnieje tego rodzaju strategia optymalna,
ale nie zawsze się stosuje bezpośrednio do gier z czynnikiem losowym.
Z blefem jest jeszcze gorzej - polega na sytuacji, gdy nie zna się
kart blefującego a oceniać można cokolwiek po jego zachowaniu.

>
> Moje pierwsze pytanie chyba można sprowadzić do tego, czy dla danej
> gry istnieje program który ma minimalną wartość 50% ( minimalną, czyli
> obojętnie z jakim programem zagra, to uzyskuje 50% lub więcej.).
>
> W różnych grach czynnik blefu może mieć różne skutki. Nie wiem w
> tej chwili czy są gry z niepełną informacją w których czynnik blefu
> nigdy nie poprawi wyniku. Jeśli takie gry są, to w nich należy grać
> optymalnie i należy zakładać że przeciwnik zagra/zagrał optymalnie.
> Myślę że dla takich gier istnieją programy które minimalną wartość w
> powyższej tabeli będą miały właśnie 50%.

Są gry, gdzie blef jest czasem stricte opłacalny, ale częściej to
zależy od przeciwnika. Blef to w końcu blef. Można robić dwa rodzaje
założeń: takie, że przeciwnik zawsze zachowa się racjonalnie,
to znaczy zgodnie z najlepszą strategią - tą optymalną - albo
takie, że nie każdy przeciwnik zachowa się racjonalnie, w tym sensie,
że jego strategia nie jest optymalna. I dochodzimy do tit-for-tat.
Socjologia nie przewiduje, że każdy będzie się przewidywał racjonalnie
i stosuje się to przez model gry (chociaż nie zawsze trzeba wygrać,
to są pożądane skutki i niepożądane, to czasem tłumaczy dlaczego
ludzie stoją w kolejce czy w korku, chociaż mogliby wybrać inny moment,
a jednak wszyscy tę kolejkę tworzą). Nieracjonalność nie bierze
się koniecznie z robienia sobie na złość, może wynikać z braku
informacji lub nieuwzględnienia strategii optymalnej. W tit-for-tat
racjonalne jest pomaganie przeciwnikowi o ile on pomaga tobie. Ale,
optymalniejsze jest wrabianie przeciwnika w pomaganie tobie, chyba
że się nie da, bo przeciwnik jest - no właśnie - bardziej racjonalny
i uwzględnia to, że można się wrabiać.

>
> Natomiast dla gier w których blefowanie może pomóc taki algorytm
> raczej nie istnieje. Chyba dla każdej strategii blefowania
> można napisać taką strategię która osiągnie ponad 50%.
>
> Dobrze myślę czy źle?

Dobrze. Zakładając że wszyscy zachowują się racjonalnie, a to
w przypadku gier dla których nie jest znana jedna optymalna strategia
jest założeniem błędnym. Ok, czasami jakkolwiek zachowa się przeciwnik
blef może się >50% opłacać (wyobrażając sobie sytuację, w której
blef nie "odkrywa kart" których można użyć później), ale z przeciwnikiem
nieracjonalnym może istnieć lepsza strategia. Co prawda tworzy się
mistrzowskie algorytmy do pokonania innego mistrza, ale
- dla niektórych gier - lepszy efekt w przypadku słabszych przeciwników
można uzyskać stosując inną strategię. Na punkty w lidze może się opłacać.

>
> Ponadto rodzą się kolejne problemy.
>
> Po pierwsze jak ocenić czy w danej grze czynnik blefu ma duże znaczenie czy
> małe? A jeśli już ocenimy jakie ma znaczenie, to jak wpleść w
> algorytm choćby jakieś najprostsze szacowanie sposobu blefowania przeciwnika?

1. nie blef - możliwe zachowania przeciwnika 2. blef - możliwe zachowania
przeciwnika. Oprócz analizy wszystkich możliwości odpowiedzi po równo,
dochodzi element przewidywania zachowania przeciwnika czyli
jego racjonalność. Psychologia czy dostosowanie się do sposobu działania
przeciwnika, wszystko jedno, można przy optymalnej strategii przeciwnika
założyć, że za duże w danej sytuacji będzie dla niego ryzyko sprawdzania
blefu i być może tylko dlatego opłaca się blefować. Ale jednocześnie zyskowna
dla przeciwnika może być możliwość sprawdzenia blefu - tyle że nie zna
on naszych kart i może zachować się właśnie, co my wiemy, niekorzystnie
dla siebie. Czysty zysk.

>
> W grach karcianych gdy jest już po rozgrywce to dowiadujemy się jakie
> karty otrzymał przeciwnik. Pamiętamy także jak dokładał karty. Może należy
> zawsze grać optymalnie, a blef oceniać tylko u przeciwnika? Można obliczyć
> jak odległa była strategia obrana przez przeciwnika od strategii
> optymalnej i zakładać jakąś średnią ważoną z N ostatnich rozdań?
>
> Wydaje się sensowne jeśli program całkowicie zaniecha blefowania a będzie
> grał zawsze optymalnie. Jeśli program zdoła oszacować poziom blefowania
> przeciwnika (a tym samym poziom umiejętności gry przeciwnika) to zagra
> optymalnie do oszacowanego poziomu.

Blef może być czasami optymalny sam w sobie, ale jak nie jest to
widzę te same problemy.

Edek

do góry

Dnia Wed, 09 May 2012 13:14:58 +0000, M.M. napisal:

> Edek Pienkowski <e...@g...com> napisał(a):
>
>> Dnia Wed, 09 May 2012 09:58:21 +0000, M.M. napisal:
>>
>> > Roman W <b...@g...pl> napisał(a):
>> >
>> >> Podobne problemy czesto rozwiazuje sie w matematyce finansowej. Jezeli
>> >> zalozysz, ze gra trwa maksymalnie N ruchow (to chyba jest prawda dla
>> >> tysiaca?), to drzewko gry mozesz po prostu przejsc od konca. To powinno
>> >> uwzglednic blefy.
>> >> Poczytaj o metodach wyceny opcji amerykanskich na drzewach i metoda "least
>> >> squares Monte Carlo".
>> >
>> > Może gra w tysiąca do wyrobienia sobie wstępnego poglądu jest nadal zbyt
>> > rozbudowana. Może powinienem posłużyć się jakąś prostszą grą. Z kole
>> i
>> > nie wiem czy prostszej grze stosowanie blefów będzie miał jakikolwiek
>> > sens...
>> >
>> > MoĹźe taka gra:
>> [...]
>> >
>> > Jak powinien wyglądać algorytm który nigdy nie przegra w taką grę?
>> > Interesuje mnie taki algorytm wraz z dowodem matematycznym Ĺźe jest
>> > algorytmem optymalnym.
>>
>> Tit-for-tat przeradza się w tit-for-tat-if-cannot-abuse-opponent.
>> W psychologii trudno o dowody formalne.
>
> Zróbmy coś, aby wyeliminować psychologię :)
>

Tak przy okazji, to akurat jest psychologia, ale dotyczy jak najbardziej
strategii optymalnej i zachowań pozostałych.

Wchodzę na dworzec, pociąg za 5 minut, było to ze dwa miesiące temu. Kolejka do
3 czy 4ech kas na 15 minut. No cóż, stoję. Ale jakoś byłem rozkojarzony, bo
bałem się że się spóźnię na pociąg, no i się rozglądam i zastanawiam, czy może
nie kupić biletu drożej w pociągu. Tak też można. I nagle w rogu, na widoku
z kolejki, widzę kasę. Otwartą. Nikogo przy niej nie ma. Co prawda ma napis
Informacja, ale ma też napis sprzedaż biletów, wygląda jakoś inaczej, ale chyba kasa.
No to ryzyk fizyk, poszedłem i kupiłem bilet. Co prawda irracjonalny umysł mówi mi,
że z tą kasą coś jest nie tak, wszyscy stoją na środku, miliony much itd.
No ale nie wiem, bilet ok, reszta ok, babka nie pluła mówiąc a i tak była szyba ;)

Wracałem obok kolejki, jakieś dwie z tapetą pytają czy tamta kasa czynna i w bieg,
ale same by dupy nie ruszyły, w końcu wszyscy tu stoją. Ok, pomyślałem, pewnie
tamtą kasę właśnie otworzyli czy właśnie mieli zamknąć i stąd taka anomalia.

Ale wczoraj było deja vu - nikt do tej kasy nie podejdzie, bo wszyscy stoją do tej
głównej grupy kas na środku i nikt się nie ruszy. Nawet chyba widzą tą kasę,
ale stoją karnie. Albo z tą kasą faktycznie jest coś nie tak, albo coś,
tak twierdzi mój irracjonalny umysł, ale racjonalnie podchodzę i kupuję bilet
bez kolejki. Stanie w kolejkach to dzisiaj jakiś fetysz? ;)

Edek

do góry

Edek Pienkowski <e...@g...com> napisał(a):

> Tu nie tylko o psychologię chodzi; na poziomie gry służy do "wykorzystania"
> algorytmu przeciwnika. Nawet optymalnego.
Tak, nie tylko o psychologię. Jeśli wiemy że przeciwnik wybrał optymalny
algorytm w jakimś określonym znaczeniu optymalności, to możemy wybrać algorytm
który będzie grał optymalnie przeciwko algorytmom należącym do takiego zbioru
z jakiego prawdopodobnie wybierał nasz przeciwnik. Poza tym, jak poniżej
piszesz, możemy po prostu przyjąć że przeciwnik nie zachowa się optymlanie.


>> Można to rozpatrywać w postaci dwuwymiarowej tabeli. W poziomie i
>> w pionie mamy kolejne programy, a w komórce na skrzyżowaniu
>> wiersza x z kolumną y mamy wynik jaki uzyskuje program x grając
>> przeciwko programowi y. Jeśli w komórce jest 100% to znaczy
>> że x wygra wszystkie gry bez względu na to jak zostały rozdane
>> karty.

>Są takie gry, gdzie istnieje tego rodzaju strategia optymalna,
>ale nie zawsze się stosuje bezpośrednio do gier z czynnikiem losowym.
>Z blefem jest jeszcze gorzej - polega na sytuacji, gdy nie zna się
>kart blefującego a oceniać można cokolwiek po jego zachowaniu.

Może niepotrzebnie utrudniam sobie analizę z tym blefem. Są tylko
zachowania graczy i strategie które do takich zachowań prowadzą.
Strategie mogą być:
1) Deterministyczne
a) na postawie danych z jednej (obecnej) partii
b) na podstawie danych z obecnej partii i N poprzednich
2) Zrandomizowane.

Ad 1a ) Algorytm na wejściu otrzymuje dane o stanie gry. Na podstawie
tych danych algorytm podaje jak należy się zachować. Dla skończonych
gier istnieje skończona ilość strategii, a więc koleje algorytmy
realizują po prostu kolejne strategie.

Ad 1b ) Jest tak samo jak w punkcie 1a, ale algorytm otrzymuje dodatkową
informację o tym jak przeciwnik zachowywał się w przeszłości. W ogólnym
przypadku przyszłość nie jest przeszłością, więc poza trywialnym przypadkami,
gdy np. przeciwnik bardzo słabo gra, taka informacja chyba niewiele da.
Mylę się?

Ad 2 ) Tutaj mamy jakiś rozkład prawdopodobieństwa, że do wybrania ruchu
numer n zostanie wybrana strategia x. Jeśli potrafimy ten rozkład
oszacować, to możemy dobierać strategię optymalną przeciwko stragegii
jaką prawdopodobnie wybrał przeciwnik. Ale raczej takie oszacowania
będą bardzo trudne.

Przypadek 1a wydaje się ciekawy. Mamy zbiór strategii, oznaczmy go X.
Dla każdej pary (x1,x2), gdzie x1 należy do X i x2 należy do X; mamy
określone ile procent zwycięstw (pomińmy remisy) odnosi strategia x1,
a strategia x2 otrzymuje 100% - to co otrzymuje x1.

A więc optymalny algorytm w przypadku 1a powinien wyglądać tak jak na
początku napisał Roman. Drzewko przeszukujemy "od tyłu" i wykorzystujemy
programowanie dynamiczne do zbudowania par (stan_gry, zachowanie)

Nie wiem czy dla popularnych gier karcianych (brydż, tysiąc, poker, pan), przy
założeniu 1a, istnieją strategie gwarantujące 50% wygranych bez względu
na to jaką strategię przyjął przeciwnik. Czy można to wywnioskować bez
konieczności budowania tabeli wypłat? Może warto jeszcze dokonać kilku
uściśleń:
1) grają dwie osoby
2) rozgrywają po jednej partii dla każdego możliwego rozdania kart,
czyli w jednej grze jest tyle partii ile jest możliwych różnych
rozdań
3) za wygraną partię jest 1 punkt, za przegraną 0 punktów.
4) w każdej partii używają tej samej stragegii
5) punkty ze wszystkich partii się sumują, wynik gry stanowi ilość
punktów dzielona przez ilość partii.
Pierwszy gracz wybiera stragegie x_i, a drugi gracz po kolei
wszyskie możliwe stragie od x_1 do x_n. Czy pierwszy gracz może wybrać
taką stragegię x_i, że dla dowolnej stragegii od x_1 do x_n uzyska minimum
50% punktów? Czy to są raczej takie gry jak kamień, nożyce, papier i
stragegia x_1 wygrywa z x_2, x_2 wygrywa z x_3, a x_3 wygrywa z x_1?


>> Natomiast dla gier w których blefowanie może pomóc taki algorytm
>> raczej nie istnieje. Chyba dla każdej strategii blefowania
>> można napisać taką strategię która osiągnie ponad 50%.
>>
>> Dobrze myślę czy źle?

> Dobrze. Zakładając że wszyscy zachowują się racjonalnie, a to
> w przypadku gier dla których nie jest znana jedna optymalna strategia
> jest założeniem błędnym. Ok, czasami jakkolwiek zachowa się przeciwnik
> blef może się >50% opłacać (wyobrażając sobie sytuację, w której
> blef nie "odkrywa kart" których można użyć później), ale z przeciwnikiem
> nieracjonalnym może istnieć lepsza strategia. Co prawda tworzy się
> mistrzowskie algorytmy do pokonania innego mistrza, ale
> dla niektórych gier - lepszy efekt w przypadku słabszych przeciwników
> można uzyskać stosując inną strategię. Na punkty w lidze może się opłacać.
Czyli problem blefu sprowadza się do tego, czy umiem stworzyć dobry model
gry przeciwnika. W ogólnym przypadku przeciwnik może zmieniać strategię
blefowania jak chce, czyli się nie da. Gdy gramy z ludźmi, to możemy
wiedzieć że kolega z klubu wczoraj się nie wyspał i zagra słabiej.

> 1. nie blef - możliwe zachowania przeciwnika 2. blef - możliwe
> zachowania przeciwnika.
> [...]
> Blef może być czasami optymalny sam w sobie, ale jak nie jest to
> widzę te same problemy.
Właśnie to mój błąd że rozgraniczam zachowania na ruchy optymalne i blef.

Pozdrawiam




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry