1
boardgamestheory
4 min de leitura ·

Processos Decisórios de Markov e Justiça Criptográfica em Gamão: O Algoritmo Expectiminimax e Provably Fair Dice

Gamão como um Processo Decisório de Markov (MDP)

Diferente do xadrez e das damas, que são jogos puramente determinísticos de informação perfeita, o gamão (backgammon) é classificado na teoria dos jogos como um jogo estocástico de informação perfeita e soma zero. A introdução de variáveis aleatórias exógenas (os dados de seis faces) transforma a dinâmica da árvore de decisão em um Processo Decisório de Markov (Markov Decision Process — MDP) com horizonte finito e espaço de estados estocástico.

Em qualquer turno de jogo, a transição entre estados não depende apenas da ação deliberada do jogador ativo, mas da convolução da ação escolhida com a distribuição de probabilidade condicional dos dados.

O Algoritmo Expectiminimax e a Distribuição dos Dados

Em jogos estocásticos, a árvore tradicional de busca Minimax é expandida com nós probabilísticos intermédios, dando origem ao algoritmo Expectiminimax.

A cada rodada, os dois dados produzem 36 combinações elementares equiprováveis, que se agrupam em 21 resultados macroscópicos distintos:

  • 15 pares não-duplos (ex.: 3-1, 6-5), cada um ocorrendo com probabilidade 2/36 = 1/18 ≈ 5,56%;
  • 6 lances duplos (ex.: 1-1, 4-4, 6-6), cada um com probabilidade 1/36 ≈ 2,78%, mas que conferem quatro movimentos idênticos em vez de dois, gerando um impacto tático desproporcional.

A função de avaliação de um nó de chance (V(s)) é formalmente calculada como o valor esperado sobre todas as 21 configurações possíveis de dados:

V(s) = ∑ [ P(d) * max_{a ∈ Actions(s, d)} V(Result(s, a)) ]

onde (P(d)) representa a probabilidade do par de dados (d), e (Actions(s, d)) representa o conjunto de permutações legais de movimentação para aquele resultado específico.

O Cubo de Dobra e a Teoria das Opções Econômicas

O gamão moderno foi profundamente transformado na década de 1920 pela invenção do Cubo de Dobra (Doubling Cube). Matematicamente, o cubo introduz um mecanismo contínuo de precificação de equidade e transferência de risco:

A Derivação do Ponto de Tomada (Take Point de 25%)

Se um jogador recebe uma proposta de dobra (double) para apostar 2 pontos em vez de 1:

  • Se ele recusar (drop), ele perde imediatamente 1 ponto (Equidade = -1.0);
  • Se ele aceitar (take), ele joga valendo 2 pontos. Denotando (p) como sua probabilidade de vitória, sua equidade esperada é: 
    E(take) = p * (+2) + (1 - p) * (-2) = 4p - 2

Para que aceitar a dobra seja matematicamente vantajoso em relação a recusar:

4p - 2 ≥ -1  =>  4p ≥ 1  =>  p ≥ 0,25 (25%)

Assim, se o jogador defensor tiver pelo menos 25% de probabilidade de vitória (desconsiderando gammon/backgammon), a decisão ótima no equilíbrio de Nash é aceitar a dobra. Além disso, a posse exclusiva do cubo funciona como uma opção financeira americana: somente quem aceitou a dobra possui o direito de redobrar posteriormente (beaver ou redouble).

O Dilema da Confiança em Plataformas Online e o Risco de PRNGs Opacos

Em implementações digitais de gamão competitivo, a integridade da distribuição de probabilidades é crítica. Quando um servidor gera dados utilizando geradores convencionais pseudo-aleatórios (PRNGs) em um backend opaco, os jogadores não possuem garantias matemáticas de que o sistema não está manipulando resultados para favorecer determinados usuários ou reter jogadores.

Para eliminar qualquer necessidade de confiança cega na infraestrutura centralizada, as plataformas de ponta adotam protocolos criptográficos de equidade comprovável (Provably Fair).

Arquitetura Criptográfica Commit-Reveal com HMAC-SHA256

O protocolo Commit-Reveal baseado em funções de dispersão unidirecionais (HMAC-SHA256) garante matematicamente que nem o servidor nem o cliente podem prever ou manipular o resultado dos dados antes do lance ser efetuado:

  1. Compromisso do Servidor (Commitment):
    Antes do início da partida, o servidor gera uma semente secreta de alta entropia (server_seed) e calcula seu hash público usando SHA-256:
    commitment = SHA256(server_seed)
    Esse hash público é enviado ao cliente antes que qualquer ação ocorra. O servidor está agora matematicamente comprometido com aquela semente, sem poder alterá-la posteriormente sem invalidar o hash.

  2. Entropia do Cliente (Client Seed):
    O cliente (navegador ou app do jogador) gera localmente sua própria semente aleatória (client_seed) ou utiliza a entropia do usuário, enviando-a ao servidor.

  3. Geração Determinística e Imparcial dos Dados:
    A cada rodada (i) (nonce), o par de dados é derivado computando o HMAC criptográfico das duas fontes de entropia:
    hash_bytes = HMAC_SHA256(server_seed, client_seed + ":" + nonce)
    Os primeiros bytes do hash resultante são convertidos em números inteiros no intervalo [1, 6] através de operações de módulo balanceado sem viés (rejection sampling).

  4. Revelação e Auditoria Pós-Jogo (Reveal):
    Ao término da partida, o servidor revela a chave secreta original (server_seed). O cliente verifica automaticamente que:

    • SHA256(server_seed) == commitment (o servidor não trocou a semente);
    • A reexecução determinística da sequência de dados produz exatamente os lances que ocorreram na partida.

Um exemplo notável de implementação rigorosa dessa arquitetura pode ser analisado e verificado publicamente no Boardgammon Fair Dice – sistema de dados provably fair e verificação criptográfica de lances, onde a suíte completa de verificação matemática é disponibilizada com transparência total de código para os participantes.

Palavras-chave: #gamao #criptografia #provablyfair #algoritmos #teoriadosjogos #programacao

Carregando publicação patrocinada...