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