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/