Cadeias de Markov e Jogos Gacha : A Verdadeira Matemática do Azar (Parte 2)

No artigo anterior, nós vencemos o “jogo bonzinho”. Usando equações de recorrência, calculamos o custo para refinar um item quando as regras eram simples e as probabilidades, constantes. Mas nós sabemos que a realidade dos jogos online é bem mais cruel.

Agora, o desafio sobe de nível. E se as regras do jogo mudarem a cada passo?

E se as chances de sucesso diminuírem a cada refino?
E se o custo de cada tentativa aumentar a cada nível?

Nossas equações simples ainda dão conta do recado, porem tudo ficara muito mais complicado e trabalhoso. Para navegar por um sistema que muda em cada passo, precisamos de uma ferramenta mais poderosa. É aqui que entra uma das ideias mais elegantes da probabilidade: a Cadeia de Markov.

Ok, mas o que é uma Cadeia de Markov?

Pense em um jogo de tabuleiro(como cobras e escadas) onde sua próxima casa depende apenas da casa onde você está agora e um lançamento aleatório de um dado, e não de todo o caminho que você fez para chegar até ali. O processo tem “memória curta”. Essa é a essência de uma Cadeia de Markov.

Essa ideia de um processo com “memória curta” é uma espécie de canivete suíço da matemática, capaz de modelar uma variedade impressionante de fenômenos. Com ela, podemos analisar desde a transmissão de erros de bit em teoria da informação e a mobilidade entre classes sociais ao longo de gerações, até a evolução de populações na biologia e, claro, os cálculos de risco em cassinos e apostas.

No fundo, para quase qualquer sistema que evolui no tempo de forma sequencial, a Cadeia de Markov oferece um mapa para entender seu comportamento. E o primeiro rascunho desse mapa é, quase sempre, um grafo — uma representação visual dos estados e dos caminhos possíveis entre eles.

fig 1. transicao de estados

MathJax Markov Matrix

$$M = \begin{pmatrix} α_{11} & α_{12} & α_{13} \\ α_{21} & α_{22} & α_{23} \\ α_{31} & α_{32} & α_{33} \end{pmatrix}$$

Matriz de transição de estados M.

Se o grafo é o nosso “mapa” visual, a matemática por trás dele é a Matriz de Transição, que geralmente chamamos de M.

Pense nela como uma tabela. A regra é simples:

As linhas (i) sempre representam o estado DE ONDE você está partindo.
As colunas (j) representam o estado PARA ONDE você pode ir.

O valor que encontramos no cruzamento da linha i com a coluna j é o nosso elemento αij (lê-se “alfa i jota”). Ele nada mais é do que a probabilidade exata de fazer essa jogada: sair do estado i e chegar no estado j.

Então, quando você vir a notação matemática formal M=[αij], não se assuste. É apenas o jeito elegante de dizer: “M é uma matriz onde cada elemento nos dá a probabilidade de ir de um estado i para um estado j“.

E, se tivermos uma lista de probabilidades dos estados (representada como pj) e quisermos saber o próximo estado, podemos escrever a seguinte equação matricial:

$$P_{n+1}=P_{n} \cdot M = \begin{pmatrix} p_{1} & p_{2} & p_{3} \end{pmatrix} \begin{pmatrix} α_{11} & α_{12} & α_{13} \\ α_{21} & α_{22} & α_{23} \\ α_{31} & α_{32} & α_{33} \end{pmatrix} $$

Agora, vamos aplicar nossas ferramentas a um desafio real, inspirado em um RPG online: a jornada para refinar um equipamento do nível +1 até o sonhado +10. Aqui, o jogo deixa de ser “bonzinho” e revela suas verdadeiras e cruéis regras:

As chances de sucesso mudam a cada novo nível.
Os custos de cada tentativa também são variáveis.
E, claro, a regra do downgrade: uma falha significa que o item volta um estado.

Com este cenário em mãos, nosso objetivo é claro: estimar o custo médio real para se conseguir cada nível de equipamento(iremos assumir que 1 moeda ou fragmento custa 1 centavo). Para começar, vamos usar as probabilidades de sucesso de cada etapa, baseadas em um jogo de verdade e apresentadas na tabela abaixo.

Tabela de Transições

Transição	Chance	Custos (moedas)
1->2	70%	20
2->3	50%	40
3->4	35%	50
4->5	25%	70
5->6	18%	100
6->7	13%	150
7->8	9%	250
8->9	6%	500
9->10	4%	1000

Gráfo da cadeia de Markov

Gráfo de transição de estados de markov!

Isso quer dizer que nossa Matriz ficaria:

$$M = \begin{pmatrix} 0.3 & 0.7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0.5 & 0.0 & 0.5 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0.65 & 0 & 0.35 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0.75 & 0 & 0.25 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0.72 & 0. & 0.18 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0.87 & 0 & 0.13 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0.91 & 0 & 0.09 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0.94 & 0 & 0.06 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.96 & 0 & 0.04\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix}$$

Ta? Mas porque diabos isso ajuda a resolver nosso problema de calcular quantas moedas nos gastariamos para ir do refino 1 ate o 10?

Não é simples, mas isso pode nos ajudar muito. Por exemplo suponha que começamos no estado 1 e que queremos saber quais as probabilidades de conseguir de estar em cada estado depois de 4 transições? Se sabemos que a chance inicial é de 100% de estar no estado 1 então para saber após 4 transições aplicar a matriz nesse vetor 4 vezes! De forma simplificada:

$$P_{4}=P_{0} \cdot M^{4} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \cdot M^{4} $$

Parece complicado, mas aqui podemos usar ferramentas de programação e softwares para nos ajudar.

Essa linha nos revela que após 4 transições teremos 33% de chance de ter voltado ao primeiro estado 23% de estar no segundo 36% de estar no 3.6% de estar no 4 e 3% de estar no 5

Tá isso me fala as chances depois de 4 transições, mas como isso me ajuda a calcular o número médio de transições do 1 pro 10? E pior como isso vai me ajudar nos custos visto que cada transição tem um peso diferente?

Vamos com calma e apresentar uns conceitos que chegamos lá:

Estado transiente é todo aquele que depois de um número grande de passos não teremos chance mais de voltarmos para eles. Esses estados são muito faceis de achar olhando o gráfo.

Vemos que não existe nenhuma seta que sai de um estado recorrente para um estado transiente, isso quer dizer que uma vez que chegamos em um estado recorrente jamais voltamos para um estado transiente. Podemos dizer também que depois de um número que se aproxima do infinito de transições estaremos obrigatoriamente em um estado recorrente. Matematicamente:

$$ \lim_{N \to \infty} P \cdot M^{N} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \ \end{pmatrix} $$ $$ \forall P $$

Tá sabemos agora que para um N suficientemente elevado temos garantia que chegaremos no refino 10.
Isso já é um passo para chegar onde queremos.

Agora vamos pensar somente no transiente, vamos reescrever a matriz de transição tirando o espaço de recorrência e vejamos o que obtemos. $T=[t_{ij}]$

$$T = \begin{pmatrix} 0.3 & 0.7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0.5 & 0.0 & 0.5 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.65 & 0 & 0.35 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0.75 & 0 & 0.25 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.72 & 0. & 0.18 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.87 & 0 & 0.13 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.91 & 0 & 0.09 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.94 & 0 & 0.06 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.96 & 0 \end{pmatrix}$$

O Pulo do Gato: A Matriz de Tempos Médios

Agora preste muita atenção, porque aqui vem a parte mais elegante da nossa análise. A pergunta que queremos responder é:

“Começando de um nível i, quantas vezes, em média, vamos visitar um nível j antes de finalmente chegar ao +10?”

A resposta está em uma matriz especial, que vamos chamar de S. E para construí-la, vamos usar a “falta de memória” da Cadeia de Markov para montar uma velha conhecida nossa: uma equação de recorrência.

Vamos construir a lógica passo a passo. O número total de vezes que visitamos o estado j, partindo de i ( $s_{ij}$ ), pode ser dividido em duas partes:

A Visita Inicial: Se começarmos no próprio estado j (ou seja, se i=j), já contamos 1 visita logo de cara. Se começarmos em qualquer outro lugar (i≠j), a contagem inicial é 0.
- Nota nerd: Matemáticos têm um nome para isso: o Delta de Kronecker (δij), que vale 1 se i=j e 0 caso contrário. É só uma forma elegante de representar a visita inicial.
As Visitas Futuras: Partindo de k, podemos pousar no estado transiente j com uma probabilidade p dado pelas somas das probabilidaes $\sum_{k=1}^{m} t_{ik}s_{kj}$

Juntando as duas partes (a visita inicial + as visitas futuras), chegamos à equação:

$s_{ij}= δ_{i,j} +\sum_{k=1}^{m} t_{ik}s_{kj}$

Rescrevendo tudo chegaremos na equação matricial.

$S=I+TS$

por consequência:

$S=(I-T)^{-1}$

Para uma prova mais robusta segue o link.

O livro do Sheldon Ross introduction to probability models tem uma seção dedicada a tempos médios em cada estado a partir de uma matriz de transição de estados. Ele nos diz que basicamente que definindo um estado final os tempos médios em cada estado vai ser dado pelo inverso da matriz. Uma procurada no google e vc consegue achar ele.

Colocando a matriz T nessa equação chegaremos:

A forma de interpretar essa matriz é que partindo da linha(nivel i para chegar ao estado final 10) vamos passar uma média de $t_{ij}$ vezes naquele estado e como sabemos que o custo para transicionar é função do estado, o custo para subir um nível do estado 1 para o estado 10 seria:
Custo=963k*20+1349k*40+1037*50+484k*70+147k*100+30k*150+4k*250+416*500+25*1000=179,706,247 Ou 179.7 Milhões de moedas ou 1.79 milhões de Reais e aproximadamente 4 milhões de tentativas. Fazendo uma simulação do processo todo para 200 tentativas(cada tentativa gastava 20segundos) ficamos com uma média de 153 milhões de moedas( nesse caso chamado fragmentos) se pudessemos comprar cada moeda por 0.01 centavos( o que frequentemente acontece em jogos) ainda gastariamos 1.5Milhões de reais por uma única arma.

Onde a média para esses processos sem memórias quase sempre vai ta na taxa de sucesso (1-1/e)=63% acompanhando uma distribuição chamada exponencial que é outra distribuição famosa por ser sem memória.

Podemos ir um pouco além nessa análise. E se quisermos saber pro 5 sem nunca avançar, como iriamos determinar isso já que somente o estado 10 é o estado recorrente?
Muito simples basta criar uma matriz artificial quando chegamos no estado por exemplo para 5 se nunca mais mudarmos a probabilidade de transição ficaria sendo p55=1 e pi5=0 para to i diferente de 5.

Como ficariamos então:

$$M = \begin{pmatrix} 0.3 & 0.7 & 0 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 & 0\\ 0 & 0.65 & 0 & 0.35 & 0\\ 0 & 0 & 0.75 & 0 & 0.25\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$ $$T = \begin{pmatrix} 0.3 & 0.7 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.65 & 0 & 0.35 \\ 0 & 0 & 0.75 & 0 \\ \end{pmatrix}$$

Invertendo obteriamos para a matriz de tempos médios:

Que nos daria um custo em moeda:
Custo=13.46*20+16.85*40+11.428*50+4*70=1,795 Moedas para ir do 1 pro 5
Simulando

Mediana de 1300 média de 1805 (n= 50mil simulações). Se afastou um pouco da média calculada, mas flutuações nessa ordem são esperadas.

E podemos fazer isso para todos os outros valores intermediários, para não me alongar vou postar a matriz de resultados com o tempo estimado em 7 segundos por tentativa de transação.

Nível do Refino	Mediana	Média de Moedas	Transições	Tempo médio de refino
2	20	29	1	7s
3	120	137	5	24s
4	360	482	14	1m 10s
5	1,300	1,795	45	4m
6	5,880	8,334	195	16m
7	39,960	53,250	1,206	1h 40m
8	359,640	510,176	11,434	15h
9	aprox 5,400,000	7,677,019	171,697	10d
10	aprox 121,000,000	179,706,247	aprox 4,000,000	233d

Finalmente podemos concluir que se um jogador não tiver autocontrole e quiser gastar muito em um processo do jogo podera fácimente gastar mais de 1 milhão de Reais (se 1 moeda for 1 centavo) em um simples jogo e essa é somente uma das ínumeras mecânicas que existem dentro do jogo. Se ficarmos um pouco mais atento e observar o gráfico tbm iremos ver um certo infortunio que podem acontecer com alguns jogadores mais azarados. A maioria dos jogadores vai gastar menos que a média para conseguir o resultado desejado e aproximademente 63%(1-1/e) vão gastar menos da média para conseguir, mas existe um grupo de jogadores que se derem azar podem facilmente gastar 2 a 3 vezes a média se tiverem no grupo dos 10% mais azarados enquanto vai ver seus amigos quase todo gastando por vezes 10x menos que ele conseguindo ir mais longe. Esse é certamente um mecanismo psicológico torturante enquanto ele ainda tenta conseguir o que deseja.

Com isso encerramos por agora o nosso estudo sobre modelos probabilísticos e jogos online com monetizações, tenha em mente que existem milhares de outras formas e modelos de monetizar e a maioria podem ser modelados pro uma simples cadeia de markov. Com isso vemos a inspiração de muitos modelso probabilisticos foram desenvolvidas no passado(saber quanto iremos gastar em casinos, jogos apostas, apostas de ações, cenários futuros), para quase tudo na sua vida em questão de incerteza podera ter ali uma cadeia de markov escondida.

Finalmente, a conclusão é chocante: um jogador sem autocontrole poderia facilmente gastar o equivalente a mais de um milhão de reais em uma única mecânica de um jogo online. E esta é apenas uma das inúmeras que existem. Se observarmos o gráfico com mais atenção, também veremos o infortúnio que pode acontecer com alguns jogadores mais azarados. A maioria, aproximadamente 63% (1-1/e), gastará menos que a média para conseguir o resultado desejado. No entanto, um jogador no grupo dos 10% mais azarados pode facilmente gastar de duas a três vezes esse valor. Isso cria um cenário frustrante, no qual ele vê seus amigos avançarem gastando, por vezes, dez vezes menos. É certamente um mecanismo psicológico torturante para quem ainda tenta alcançar o objetivo.

Vimos também outro poder da ferramenta das cadeias de markov. Em vez de rodar uma simulação computacional milhares de vezes para estimar esse custo — um processo que poderia ser lento e computacionalmente difícil —, as Cadeias de Markov nos entregam o resultado analítico e exato. Elas nos dão a resposta precisa que a pura força bruta da simulação teria dificuldade em alcançar e são extremamente flexíveis.

Com isso, encerramos por agora nosso estudo sobre jogos e modelos probabilísticos. Tenha em mente que esta é apenas uma das milhares de formas de monetização, e a maioria delas pode ser mapeada por uma simples Cadeia de Markov. Vemos que muitos desses modelos nasceram de necessidades antigas: calcular riscos em cassinos, em apostas de ações, em cenários futuros. Olhe com atenção e, para quase toda incerteza em sua vida, você talvez encontre uma Cadeia de Markov escondida.