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