Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o problema “Ganhando em Las Vegas” utilizando a programação dinâmica?

0 votos
61 visitas
perguntada Jun 10 em Ciência da Computação por Felipe Amaral (16 pontos)  

O problema intitulado “Ganhando em Las Vegas” representa um estudo de caso de programação dinâmica apresentado no livro “Dynamic Programming: A computational tool – Art Lew e Holger
Mauch” (vide seção 2.19 – problema INVESTWLV) e que, originalmente, aparece no livro “Introduction to Operations Research - Frederick Hillier e Gerald Lieberman" (exemplo 7 do capítulo 10).

O enunciado do problema, conforme o livro de Hillier e Lieberman, é o seguinte:

Um jovem estatístico empreendedor acredita que tenha desenvolvido um
sistema para ganhar um popular jogo em Las Vegas. Seus colegas não
acreditam que seu sistema funcione; portanto, eles fizeram uma grande
aposta com ele que se iniciar com três fichas, ele não terá pelo menos
cinco fichas após três rodadas do jogo. Cada rodada do jogo envolve
apostar um número de fichas disponíveis e então ganhar ou perder esse
número de fichas. O estatístico acredita que seu sistema lhe dará uma
probabilidade de 2/3 de ganhar determinada rodada do jogo.

Assim, o objetivo do estatístico é o de determinar uma política de apostas ótima a cada rodada de modo a maximizar a sua chance de vencer o desafio.

Compartilhe

1 Resposta

0 votos
respondida Jun 10 por Felipe Amaral (16 pontos)  

A solução para o problema “Ganhando em Las Vegas” pode ser obtida com o uso da programação dinâmica. Por esta metodologia, o problema original é subdividido em problemas menores, de forma que a política ótima é encontrada por meio da conexão entre as soluções dos subproblemas.

A modelagem proposta para a solução do problema é a seguinte:

Estágio, \(n\) : n-ésima rodada do jogo ( \(n=0,1,2\)).
Estado, \(s_n \): número de fichas em mãos para começar o jogo na rodada \(n \).
Variável de decisão, \(x_n \): número de fichas apostadas na rodada \(n (x_n=0,...,s_n) \).
DPFE (Dynamic Programming Functional Equation): \(f^*(n,s_n) = Max_{x_n=0,...,s_n} (1/3).f^*(n+1,s_n-x_n)+(2/3).f^*(n+1,s_n+x_n) \)
DPFE Base Conditions: \(f^*(3,s_n)=0 \), se \(s_n<5\); \(f^*(3,s_n)=1\), se \(s_n>=5 \).
Função objetivo: \(f^*(0,3) \).

Assim, a DPFE fornece para cada subproblema, isto é, um par de estágio/estado, uma política decisória ótima. Como a DPFE é uma função recursiva, isto é, uma função que chama a si própria, as relações da DPFE Base Conditions fornecem um critério de parada para esta recursão. O problema original é, então, resolvido quando o algoritmo da programação dinâmica encontra o valor ótimo para o estado inicial, isto é, encontra o valor ótimo para \(f^*(0,3) \).

O código abaixo, escrito em Python, fornece a solução para o problema. Para clarificação dos resultados, na implementação computacional adotada as soluções intermediárias para os subproblemas são armazenadas em uma tabela auxiliar, que irá ajudar na reconstrução da política ótima que deve ser seguida a cada estágio/estado.

#=====================================
#Especificação do problema
#=====================================

numerofichasdesejadas=5 #Número desejado de fichas
numerojogadas=2 #Três estágios n=0,n=1,n=2
tabelasubproblemas=list()

def f(n,sn):
    ans=0
    subproblema=" Tabela de subproblemas:"
    if (n>numerojogadas) and (sn<numerofichasdesejadas): #Condição de parada
      ans=0
    if (n>numerojogadas) and (sn>=numerofichasdesejadas): #Condição de parada
      ans=1
    if (n<=numerojogadas):  #Função recursiva     
      decisionSet=possibleDecisions(n,sn)
      xtmp=list()
      for xn in decisionSet:
           tmp=(1/3)*f(n+1,sn-xn)+(2/3)*f(n+1,sn+xn)
           xtmp.append(tmp)
           if tmp>ans:
              ans=tmp
      #Recuperação do xn ótimo do estado sn
      xstarsn=list()
      k=0
      for xn in decisionSet:
          if ans==xtmp[k]:
            xstarsn.append(xn)
          k=k+1
      if sn<=9:
        snstr='0'+str(sn)
      else:
        snstr=str(sn)
      subproblema="f*(" + str(n) + "," + snstr+")= " + str(ans) + " | xn*= " + str(xstarsn)
    tabelasubproblemas.append(subproblema)
    return ans
def possibleDecisions(n,sn):
    ans=list()
    i = 0
    while i <= sn:
      ans.append(i)
      i += 1
    return ans

#=====================================
#Chamada principal
#=====================================

f(0,3) #Objetivo

#Recupera a tabela com os subproblemas
tabelasubproblemas = list(dict.fromkeys(tabelasubproblemas)) #Remove duplicatas
tabelasubproblemas.sort() #Ordena os estágios
tabelasubproblemas

O output da chamada do código é o seguinte:

[' Tabela de subproblemas:',
'f(0,03)= 0.7407407407407407 | xn= 1',
'f(1,00)= 0 | xn= [0]',
'f(1,01)= 0 | xn= [0, 1]',
'f(1,02)= 0.4444444444444444 | xn= [1, 2]',
'f(1,03)= 0.6666666666666666 | xn= [0, 2, 3]',
'f(1,04)= 0.8888888888888888 | xn= 1',
'f(1,05)= 1.0 | xn= [0]',
'f(1,06)= 1.0 | xn= [0, 1]',
'f(2,00)= 0 | xn= [0]',
'f(2,01)= 0 | xn= [0, 1]',
'f(2,02)= 0 | xn= [0, 1, 2]',
'f(2,03)= 0.6666666666666666 | xn= [2, 3]',
'f(2,04)= 0.6666666666666666 | xn= [1, 2, 3, 4]',
'f(2,05)= 1.0 | xn= [0]',
'f(2,06)= 1.0 | xn= [0, 1]',
'f(2,07)= 1.0 | xn= [0, 1, 2]',
'f(2,08)= 1.0 | xn= [0, 1, 2, 3]',
'f(2,09)= 1.0 | xn= [0, 1, 2, 3, 4]',
'f(2,10)= 1.0 | xn= [0, 1, 2, 3, 4, 5]',
'f(2,11)= 1.0 | xn= [0, 1, 2, 3, 4, 5, 6]',
'f(2,12)= 1.0 | xn= [0, 1, 2, 3, 4, 5, 6, 7]']

A política ótima a ser seguida pode ser recuperada ligando a política \(f^*(n,s_n) \) aos seus sucessores, a partir de \(f^*(0,3) \), pela relação \(f^*(n+1,s_n-x_n) \), para o caso de perda na rodada, ou \(f^*(n+1,s_n+x_n) \), para o caso de ganho. Assim, por exemplo, o estatístico deve começar apostando 1 ficha no estágio 0. Caso ele ganhe a aposta no estágio 0, ele deve seguir a política preconizada em \(f^*(1,4) \), ou seja, apostar novamente uma ficha no estágio 1. Caso ele perca a aposta no estágio 0, ele estará igualmente favorecido estatisticamente caso ele venha a apostar 1 ou 2 fichas no estágio 1 (pois a política de \(f^*(1,2) \) é \(x_1^*= [1, 2]\). Seguindo esta linha de raciocínio, a política de apostas ótima para os estágios 0,1,2 é dada pela seguinte tabela:

A imagem será apresentada aqui.

comentou Jul 13 por Daniel Castro (46 pontos)  
Tanto o problema quanto a solução são muito interessantes. Como evolução, sugiro adotar as convenções de codificação de um guia de estilo como o PEP 8 (https://www.python.org/dev/peps/pep-0008/#naming-conventions) para melhorar a manutenibilidade e o entendimento.

Sugiro também utilizar o teste condicional if __name__ == "__main__": para evitar que a chamada principal seja executada caso o código seja utilizado como um módulo, ou seja,  quando apenas as funções f e possibleDecisions forem chamadas por outros scripts.

Por fim, sugiro avaliar a substituição das iterações em listas por "list comprehensions" (https://python-3-patterns-idioms-test.readthedocs.io/en/latest/Comprehensions.html). A leitura do código pode não ficar tão fácil como em um loop for, mas o desempenho em geral é bastante superior.
...