Poker-AI.org

Re: CFRM with exponential smooting?

2014-03-10T21:48:45+00:00

Nasher wrote:

They're adjusted by global count or by how often the node is touched?

For the factor approach I used total Iterations. For the SB's open strategy it seemed to improve convergence, but I did not check other nodes

For the approach of pre-initialisation I would abstain from any adjustments. Just make CFRM believe it already completed 250'000'000 iterations and let the algorithm do its work. I haven't implemented that yet. I am just curious about possible drawbacks this approach might have

Statistics: Posted by Nose — Mon Mar 10, 2014 9:48 pm

Re: CFRM with exponential smooting?

2014-03-10T07:52:30+00:00

They're adjusted by global count or by how often the node is touched?

Statistics: Posted by cantina — Mon Mar 10, 2014 7:52 am

Re: CFRM with exponential smooting?

2014-03-07T21:15:56+00:00

This brings up an idea to adress the issue p2bb brought up initially

Let's say we solved some HUNL with an card and bet sizing abstraction. Now we want to solve a game which (by some means) is similar to the game we solved.

What one could do is:
(1) Initialize the new game with the frequencies we obtained for the first game
(2) Give these frequencies some weight (ie. 250,000,000 Iterations)
(3) Run CFRM on this pre-initialised game tree

The idea is just to skip the phase where CFRM is totally clueless by *providing some (rougly accurate) frequencies.

Thoughts about that?

Statistics: Posted by Nose — Fri Mar 07, 2014 9:15 pm

Re: CFRM with exponential smooting?

2014-03-07T11:04:06+00:00

I changed my approach. I implemented a command that allows me to upscale/downscale cumulative regrets and average strategies to a chosen percentage

(90%, 75%, 50%, 150%, 175%, 200%)

So I guess for the next few hours I will find myself rescaling regrets and average strategies

Statistics: Posted by Nose — Fri Mar 07, 2014 11:04 am

Re: CFRM with exponential smooting?

2014-03-07T13:22:07+00:00

ConvexPolytope wrote:

Quote:

2) Every 1,000,000 iterations
Code:
if( 0 == (Iterations % 1000000) ) f *= f;

It works well in the beginning, but at some point the growth of the factor is too large

The current value of f is squared every 1M hands, so with f(0) = 1.000001, after i-million iterations f will be

f(i) = f(0)^(2^i)

In other words, it's not f that is growing exponentially in the number of iterations, but the exponent of f, so f will get prohibitively large very fast:

f(22) = 66.3
f(23) = 4,387
f(24) = 19,331,000
f(26) = 1.39 * 10^29 > 2^64 (at this point f will overflow)

The problem with exponential growth in general is that for sufficiently many iterations, your value will always become too large.

Maybe something like this is better suited:

f(i) = (1 + 0.001 * i) ^ k

where k is some positive integer.

Isn't it more like f(í)= (f(0)^2)^I = f(0)^(2*I) ?

So the table would look like

Code:

i   2*i   f(i)
0   0   1.000001
1   2   1.000002
2   4   1.000004
3   6   1.000006
4   8   1.000008
5   10   1.00001
6   12   1.000012
7   14   1.000014
8   16   1.000016
9   18   1.000018
10   20   1.00002
11   22   1.000022
12   24   1.000024
13   26   1.000026
14   28   1.000028
15   30   1.00003
16   32   1.000032
17   34   1.000034001
18   36   1.000036001
19   38   1.000038001
20   40   1.000040001
21   42   1.000042001
22   44   1.000044001
23   46   1.000046001
24   48   1.000048001
25   50   1.000050001
26   52   1.000052001
27   54   1.000054001
28   56   1.000056002
29   58   1.000058002
30   60   1.000060002
31   62   1.000062002
32   64   1.000064002
33   66   1.000066002
34   68   1.000068002
35   70   1.000070002
36   72   1.000072003
37   74   1.000074003
38   76   1.000076003
39   78   1.000078003
40   80   1.000080003
41   82   1.000082003
42   84   1.000084003
43   86   1.000086004
44   88   1.000088004
45   90   1.000090004
46   92   1.000092004
47   94   1.000094004
48   96   1.000096005
49   98   1.000098005
50   100   1.000100005
51   102   1.000102005
52   104   1.000104005
53   106   1.000106006
54   108   1.000108006
55   110   1.000110006
56   112   1.000112006
57   114   1.000114006
58   116   1.000116007
59   118   1.000118007
60   120   1.000120007
61   122   1.000122007
62   124   1.000124008
63   126   1.000126008
64   128   1.000128008
65   130   1.000130008
66   132   1.000132009
67   134   1.000134009
68   136   1.000136009
69   138   1.000138009
70   140   1.00014001
71   142   1.00014201
72   144   1.00014401
73   146   1.000146011
74   148   1.000148011
75   150   1.000150011
76   152   1.000152011
77   154   1.000154012
78   156   1.000156012
79   158   1.000158012
80   160   1.000160013
81   162   1.000162013
82   164   1.000164013
83   166   1.000166014
84   168   1.000168014
85   170   1.000170014
86   172   1.000172015
87   174   1.000174015
88   176   1.000176015
89   178   1.000178016
90   180   1.000180016
91   182   1.000182016
92   184   1.000184017
93   186   1.000186017
94   188   1.000188018
95   190   1.000190018
96   192   1.000192018
97   194   1.000194019
98   196   1.000196019
99   198   1.00019802
100   200   1.00020002

I guess the problem is rather that the scale_factor does not grow fast enough

EDIT: Must be something else that grew too fast

Statistics: Posted by Nose — Fri Mar 07, 2014 10:33 am

Re: CFRM with exponential smooting?

2013-12-14T08:48:15+00:00

Quote:

2) Every 1,000,000 iterations
Code:
if( 0 == (Iterations % 1000000) ) f *= f;

It works well in the beginning, but at some point the growth of the factor is too large

Statistics: Posted by ConvexPolytope — Sat Dec 14, 2013 8:48 am

Re: CFRM with exponential smooting?

2013-12-14T04:01:31+00:00

Did anyone put further work into this?

I introduced a factor f := 1.000001 (=initial value) and changed my implementation as follows:

1) Regret-Update

Code:

for (Int32 i = 0; i < totalActions; i++) _cProfile[bucket, i] += f * (regStrat[i] / (qTrain * qOpp));

2) Every 1,000,000 iterations

Code:

if( 0 == (Iterations % 1000000) ) f *= f;

It works well in the beginning, but at some point the growth of the factor is too large

Statistics: Posted by Nose — Sat Dec 14, 2013 4:01 am

Re: CFRM with exponential smooting?

2013-05-27T10:33:34+00:00

Naively I would say

Code:

if(0 == (#Iterations % 10^6))
  foreach(double r in Regrets)
    r *= 0.95;

where initial weights will have been reduced to 0.5% after 100M iterations. after a certain number of iterations one can simply stop smoothening the regrets like

Code:

if(0 == (#Iterations % 10^6))
  if(#Iterations < 10^8)
    foreach(double r in Regrets)
      r *= 0.95;

or alternatively one could use something similar to simulated annealing like

Code:

foreach(double r in Regrets)
  r *= (1-exp(-#Iterations));

the algorithm is still guaranteed to converge in case you stop smoothening at a certain point

[EDIT] Where 10^6 means Math.Pow(10,6) or 1,000,000

Statistics: Posted by Nose — Mon May 27, 2013 10:33 am

Re: CFRM with exponential smooting?

2013-05-11T19:20:49+00:00

I like the idea but I don't think I am versed in it enough to come up with a proper formula that both achieves quicker convergence and also minimizes overfitting/getting stuck in local optima.

Statistics: Posted by Coffee4tw — Sat May 11, 2013 7:20 pm

Re: CFRM with exponential smooting?

2013-05-07T07:18:05+00:00

Slumbot 2012 did this. I mentioned I tried this before with HUL, but didn't conduct a conclusive analysis. I'd imagine it will get you closer to EQ quicker, but may skew things later on. I'd be interested to see a formulaic decay of the weight as the strategy converges. So, initially, more recent regrets have a larger impact, but eventually they reduce to normal -- maybe as an inverse to the node exploration probability used in average sampling?

Statistics: Posted by cantina — Tue May 07, 2013 7:18 am

CFRM with exponential smooting?

2013-05-04T18:44:08+00:00

When learning with a CFRM algorithm, we just add up cumulative regrets and strategies. One problem with this is, that convergence is not a linear process. For instance, at the beginning where every player plays a "random" strategy, open raising a hand like 53s might not be profitable, leasing to negative regrets and the strategy going towards 0 for this bucket. After xM iterations however, we will see that villain folds enough, so the bucket may get profitable. However, the larger x is, the longer it takes to converge as we already added up negative regrets for xM iterations... I wonder if we could increase the convergence rate with exponential smoothing: recent values (regrets/strategies) get a higher weight than very old ones. Did anyone try this in a CFRM context? I know some people use it for opponent modeling to increase the weight of recent observations and reduce the one of very old observations. One possible problem is always running into local minima, but given we have an exploration factor which ensures that every action is sampled with x% even if it has a negative regret, we should overcome this. So in theory I'd guess the only problem might be that if we oscillate between two strategies, we are more inclined to use the recent one. But this should only be a very small concern in terms of EV.

Statistics: Posted by proud2bBot — Sat May 04, 2013 6:44 pm