- Teoria de Jogos Combinat rios: Uma Breve Introdu ocelc.ciencias.ulisboa.pt/seminar/slides_2013/slid130527.pdf · Emanuel Lasker (1931) (sobre o nim de lasker): (...) Podemos provar

Teoria de Jogos Combinatorios: Uma Breve Introducao

Carlos Pereira dos Santos

ISEC

27 de Maio de 2013

Carlos Pereira dos Santos (ISEC) 27 de Maio de 2013 1 / 70

Teorias de Jogos

Teorias de Jogos

Pascal-Fermat (sec. XVII)Cardano, Liber de ludo Aleae (sec. XVI)


Teorias de Jogos

Teorias de Jogos

Pascal-Fermat (sec. XVII) Theory of Games and Economic Behaviour, 1944Cardano, Liber de ludo Aleae (sec. XVI) (von Neumann, Morgenstern)

Equilıbrio de Nash, 1950


Teorias de Jogos

Teorias de Jogos

Pascal-Fermat (sec. XVII) Theory of Games and Economic Behaviour, 1944 Conferencia de Dartmouth, 1956Cardano, Liber de ludo Aleae (sec. XVI) (von Neumann, Morgenstern) Stephen Cook, PxNP, 1971

Equilıbrio de Nash, 1950 Montecarlo, 1946(von Neumann, Ulam)


Teorias de Jogos

Teorias de Jogos

Pascal-Fermat (sec. XVII) Theory of Games and Economic Behaviour, 1944 Conferencia de Dartmouth, 1956Cardano, Liber de ludo Aleae (sec. XVI) (von Neumann, Morgenstern) Stephen Cook, PxNP, 1971

Equilıbrio de Nash, 1950 Montecarlo, 1946(von Neumann, Ulam)


Teorias de Jogos

Jogo Combinatorio: Definicao Informal

Definicao

Um jogo combinatorio satisfaz as seguintes condicoes:

1 Dois jogadores (Esquerda, Direito) jogam alternadamente;

2 Nao ha dispositivos aleatorios como dados, cartas ou peoes; em todosos momentos, cada jogador e conhecedor de toda a informacaorelativa a uma posicao de jogo;

3 As regras de um jogo combinatorio asseguram que, mesmo ignorandoa regra da alternancia, nao ha sequencias infinitas de jogadas legais;

4 A condicao de vitoria e baseada no ultimo movimento efectuado.


Teorias de Jogos


Na Versao Normal o ultimo a jogar ganha.


Teorias de Jogos


Na Versao Normal o ultimo a jogar ganha.

Na Versao Misere o ultimo a jogar perde.


Teorias de Jogos

Historia

Alda Carvalho, Carlos Pereira dos Santos, Joao Neto, Jorge Nuno Silva,“History of Combinatorial Games”, Of Boards and Men: Board GamesInvestigated, Actas do XIIIth Board Game Studies Colloquium, Paris, 14-17April 2010, organizado e editado por Thierry Depaulis, pp. 241-276, 2012.


Jogo do nim

nim

Ha um certo numero de pilhas. Ha dois jogadores alternando movimentos.Cada jogador escolhe uma pilha e retira-lhe o numero de feijoes que quiser.


Jogo do nim

nim

Ha um certo numero de pilhas. Ha dois jogadores alternando movimentos.Cada jogador escolhe uma pilha e retira-lhe o numero de feijoes que quiser.

C. L. Bouton. “Nim, a game with a complete mathematical theory”, Ann.Math. 3 (2), 1902, 35–39.


Jogo do nim

Bouton

101

011

100


Jogo do nim

Bouton

101

011

100⊕

010


Jogo do nim

Bouton

101

001

100⊕

000


Ideia Intuitiva de Igualdade e Soma Disjunctiva

dominorio imparcial



dominorio imparcial



dominorio imparcial



dominorio imparcial



Soma Disjunctiva (Intuicao)



Igualdade de Jogos (Intuicao)

= ?




Outras Componentes




Outras Componentes


Definicoes Iniciais

Definicao Recursiva de Jogo Combinatorio

Definicao

Define-se recursivamente jogo combinatorio J = {J E | J D} em que J E eo conjunto das opcoes da Esquerda e J D e o conjunto das opcoes doDireito. J E e J D sao conjuntos de jogos combinatorios (as opcoes saojogos) e, usualmente, utiliza-se JE e JD para designar elementos genericosde J E e J D. J e um jogo curto se puder ser escrito na forma {J E | J D}com J E e J D conjuntos finitos de jogos curtos. Caso contrario, o jogodiz-se jogo longo.


Definicoes Iniciais

Dia 0

Dia 0

{ | } = 0


Definicoes Iniciais

Dia 1

Dia 1

{0 | } = 1 { | 0} = −1 {0 | 0} = ∗


Definicoes Iniciais

Outros Dias Menos Claros...

No dia 2, 22 jogos nascidos.


Definicoes Iniciais



No dia 3, 1474 jogos.


Definicoes Iniciais



No dia 3, 1474 jogos.

No dia 4, algures entre 3 trilioes e 10434 jogos...


Definicoes Iniciais

Nımeros

{0 | 0} = ∗ {0, ∗ | 0, ∗} = ∗2 {0, ∗, ∗2 | 0, ∗, ∗2} = ∗3

∗n = {0, ∗, . . . , ∗(n − 1) | 0, ∗, . . . , ∗(n − 1)}


Definicoes Iniciais

Desfechos

Teorema

(Teorema Fundamental da Teoria dos Jogos Combinatorios)Seja J um jogo combinatorio. Ou o primeiro a jogar pode forcar a vitoriaou o segundo a jogar pode forcar a vitoria; nunca ambos.


Definicoes Iniciais

Desfechos

Teorema


Ha 4 desfechos compatıveis com o teorema fundamental:


Definicoes Iniciais

Desfechos

Teorema


Ha 4 desfechos compatıveis com o teorema fundamental:

Desfecho Nome DefinicaoN confuso O jogador SeguiN te pode forcar a vitoriaP zero (na versao normal) O jogador Previo pode forcar a vitoria.

(para evitar o problema da inexistenciade jogador previo, P significa realmenteque o seguiN te nao pode forcar a vitoria)

E positivo (na versao normal) Esquerda pode forcar a vitoria independentementede quem joga primeiro

D negativo (na versao normal) Direito pode forcar a vitoria independentementede quem joga primeiro


Definicoes Iniciais

Definicao Recursiva de Soma Disjunctiva

Definicao

(Soma Disjunctiva)J + H = {J E + H, J + HE | J D + H, J + HD}


Definicoes Iniciais

Igualdade

Definicao

(Igualdade)J = H se d(J + X ) = d(H + X ) para todos os jogos X .


Teoria Sprague-Grundy

Primeiras Intuicoes

Emanuel Lasker (1931) (sobre o nim de lasker): (. . . ) Podemos provarque dois grupos sao iguais se, em qualquer posicao de jogo, pudermostrocar um pelo outro sem alterar o vencedor (. . . ).




R. P. Sprague. “Uber mathematische Kampfspiele”. Tohoku MathematicalJournal, 1935.

P. M. Grundy. “Mathematics and Games”. Eureka, 1939.



Jogos Imparciais e Teoria Sprague-Grundy

Definicao

(Imparcial)Um jogo J e imparcial se as opcoes da Esquerda e as opcoes do Direitoforem as mesmas em J e em todos os seus seguidores.



Jogos Imparciais e Teoria Sprague-Grundy

Definicao

(Imparcial)Um jogo J e imparcial se as opcoes da Esquerda e as opcoes do Direitoforem as mesmas em J e em todos os seus seguidores.

Teorema

(Teoria Sprague-Grundy)

1 Se um jogo J e imparcial, J e igual a um nımero (J = ∗n para algumn). E usual chamar-se a n o valor Grundy de J: G(J) = n;

2 Considerando dois jogos imparciais J e H, G(J + H) = G(J) ⊕ G(H).



Reversibilidade, Funcao Mınimo Excluıdo

{0, ∗, ∗4 | 0, ∗} (Reversibilidade, Mex)



Reversibilidade, Funcao Mınimo Excluıdo

{0, ∗, ∗4 | 0, ∗} (Reversibilidade, Mex)

Forma Canonica



Como Aplicar?

Distincao entre Conjunto de Regras e Jogo.



Como Aplicar?


Optaremos pela notacao de A. Siegel, G para designar os jogos curtos deConway e PG para designar os jogos de Conway em geral.



Como Aplicar?


Optaremos pela notacao de A. Siegel, G para designar os jogos curtos deConway e PG para designar os jogos de Conway em geral.

Consideremos um conjunto de regras tal como o lim. Consideremos P aclasse de todas as posicoes possıveis do lim. O jogo fica resolvido comuma “boa compreensao” da injeccao,

P → PG

p ∈ P → ∗n relativo a TSG



Richard Guy

Richard Guy (n. 1916 f de 2005)



Uma Aplicacao

Alex Fink, Aviezri Fraenkel, Carlos Santos, “Lim is not Slim”, InternationalJournal of Game Theory (impact factor 2012-0.3), DOI:10.1007/s00182-013-0380-z, 2013.http://link.springer.com/article/10.1007



Dimensao nim

Carlos Pereira dos Santos, “Embedding Processes in Combinatorial GameTheory”, Discrete Applied Mathematics, 159, pp. 675-682 (impact factor, 2012 -

0.795), 2011. http://dx.doi.org/10.1016/j.dam.2010.11.019

Carlos Pereira dos Santos, Jorge Nuno Silva, “Konane has InfiniteNim-Dimension”, Integers, Electronic Journal of Combinatorial NumberTheory, 2008. http://www.integers-ejcnt.org/vol8.html

Carlos Pereira dos Santos, Jorge Nuno Silva, “Nimbers in Partizan Games”,Games of no Chance 4, Cambridge University Press, 2009 (aceite).


Teoria Geral

John H. Conway

John Conway (n. 1937)

Estudou em Cambridge. Conheceu o filho de Richard Guy em 1960. ElwinBerlekamp conheceu Richard Guy numa conferencia em 1966. Em 1970,Conway deu uma serie de talks em Cambridge sobre a sua ideia sobre osjogos combinatorios.


Teoria Geral

Primeiras Publicacoes

D. Knuth. 1974. Surreal Numbers. Addison-Wesley, Reading,Massachusetts.


Teoria Geral



J. Conway. 1976. On Numbers and Games, Academic Press.


Teoria Geral



J. Conway. 1976. On Numbers and Games, Academic Press.

E. R. Berlekamp, J. Conway, R. Guy. Winning Ways. 1982. AcademicPress, London.


Teoria Geral

Winning Ways


Teoria Geral

Inversos e Ordem

Definicao

(Inversos Aditivos)−G = {−GR | − GL}


Teoria Geral

Inversos e Ordem

Definicao

(Inversos Aditivos)−G = {−GR | − GL}

Definicao

(Ordem) J > H se ∀X,se a Esquerda ganha jogando primeiro em H + X entao a Esquerda ganhajogando primeiro em J + Xe

se a Esquerda ganha jogando segundo em H + X entao a Esquerda ganhajogando segundo em J + X.


Teoria Geral

Estrutura

Os jogos de Conway tem estrutura de grupo abeliano parcialmenteordenado.


Teoria Geral

Formas Construtivas

Ha formas construtivas para se realizar comparacoes.

Teorema

(Teorema Fundamental da Versao Normal) J = 0 ⇔ J e uma posicao-P.


Teoria Geral

Formas Construtivas

Ha formas construtivas para se realizar comparacoes.

Teorema

(Teorema Fundamental da Versao Normal) J = 0 ⇔ J e uma posicao-P.

Teorema

(Igualdade Jogavel)

J = H ⇔ J − H = 0.


Teoria Geral

Formas Construtivas

J > 0 quando a Esquerda ganha J J > H quando a Esquerda J − HJ = 0 quando o jogador previo J J = H quando o jogador previo ganha J − HJ < 0 quando o Direito ganha J J < H quando o Direito ganha J − HJ‖0 quando o jogador seguinte ganha J J‖H quando o jogador seguinte ganha J − H


Teoria Geral

Arbusto

{0 | } = 1 d(J) = E

b

b


Teoria Geral

Arbusto

{0 | 1} d(J) = E

bb

b

b


Teoria Geral

Arbusto

J − H > 0

b

b

bb

b

b


Teoria Geral

Quantificacao?

0

b

b

bb

b

b

b

bb

b


Teoria Geral

Numeros

Definicao

(Numeros)Um jogo combinatorio J na forma canonica e um numero, se todas asopcoes de J forem numeros e todos os elementos de J L forem menores doque qualquer elemento de J R .


Teoria Geral

Diadicos

Definicao

(Inteiros)n = {n − 1 | }


Teoria Geral

Diadicos

Definicao

(Inteiros)n = {n − 1 | }

Definicao

(Diadicos)Para j > 0 e m ımpar, define-se

m

2j=

{

m − 1

2j|m + 1

2j

}


Teoria Geral

Ajuste Mais Simples

bbb


Teoria Geral

Ajuste Mais Simples

1 2 3 4 5

{1 | 5}

b b bbb


Teoria Geral

Ajuste Mais Simples

1 2 3 4 5

{1 | 5} = 2

b b bbb

Teorema do Ajuste mais Simples


Teoria Geral

Dicoticos

Outro conjunto de regras interessante: clobber, um jogo dicotico(totalmente pequeno).


Teoria Geral

Dicoticos


Teoria Geral

Dicoticos

Definicao

(Jogo Dicotico) Um jogo combinatorio J diz-se dicotico se para J eseguidores, quando um dos jogadores tem opcoes o outro jogador tambemtem.


Teoria Geral

Infinitesimais

b

b


Teoria Geral

Infinitesimais

Definicao

(Infinitesimal) Um jogo combinatorio J e infinitesimal se −r < J < r paraqualquer numero r > 0.


Teoria Geral

Peso Atomico

Peso Atomico (Regra dos Dois de Avanco)


Teoria Geral

Teorema do Valor Medio; Teoria da Temperatura

Jogos Quentes


Teoria Geral


Jogos Quentes

{1 | − 1} = ±1


Teoria Geral


Jogos Quentes

{1 | − 1} = ±1

±1 + ±1 + ±1 + . . .


Teoria Geral


Jogos Quentes

{1 | − 1} = ±1

±1 + ±1 + ±1 + . . .

{4 | 2} = 3 ± 1


Teoria Geral


Jogos Quentes

{1 | − 1} = ±1

±1 + ±1 + ±1 + . . .

{4 | 2} = 3 ± 1

{4 | 2} + {4 | 2} + {4 | 2} + . . . = 3 ± 1 + 3 ± 1 + 3 ± 1 + . . . = n.3+ △


Teoria Geral


Jogos Quentes

{1 | − 1} = ±1

±1 + ±1 + ±1 + . . .

{4 | 2} = 3 ± 1

{4 | 2} + {4 | 2} + {4 | 2} + . . . = 3 ± 1 + 3 ± 1 + 3 ± 1 + . . . = n.3+ △

{{100 | 4} | 2}


Teoria Geral


Jogos Quentes

{1 | − 1} = ±1

±1 + ±1 + ±1 + . . .

{4 | 2} = 3 ± 1

{4 | 2} + {4 | 2} + {4 | 2} + . . . = 3 ± 1 + 3 ± 1 + 3 ± 1 + . . . = n.3+ △

{{100 | 4} | 2}

{{100 | 4} | 2} + {{100 | 4} | 2} + {{100 | 4} | 2} + . . .


Teoria Geral

Quadro Geral (Versao Normal)

IC de Medida Nao Nula

Jogos Quentes

Teorema do Valor Medio

Numeros

Teorema do Ajuste Mais Simples

Infinitesimais

Jogos Dicoticos

Peso Atomico

Jogos Imparciais

Teoria Sprague − Grundy

IC de Medida Nula

J tal que J=r+inf

Princ ıpio da Translacao

G (versao normal)

Zero

Teoria da TemperaturaRegra dos Dois de Avanco

Teorema da Escusa dos Numeros

b


Teoria Geral

Alguns Resultados

Alda Carvalho, Carlos Pereira dos Santos, “A Non-trivial Surjective Maponto the Short Conway’s Group”, Games of no Chance 4, CambridgeUniversity Press, 2011 (aceite).

A. Carvalho, Carlos P. Santos, C. Dias, F. Coelho, J. Neto e S. Vinagre,“A Recursive Process Related to a Partizan Variation of Wythoff”,Integers, Electronic Journal of Combinatorial Number Theory (12), 2012.http://www.integers-ejcnt.org/vol12.html


Estrutura

Dia 0 e Dia 1

0

Dia 0

0 ∗

1

−1

Dia 1

b b

b

b b


Estrutura

Dia 2 (Guy)


Estrutura

Dia 2

{1 | 0, ∗}

{1 | ∗}

−12

−1∗

0

{∗ | −1}

1

↓

12

↑ ∗

{0, ∗ | −1}

↑

∗2 ±1

1∗

−2

∗

−1

↓ ∗

{0 | −1}

{1 | 0}

2

Construcao de Conway

Dia 2


Estrutura

Distributividade

D. Calistrate, M. Paulus, D. Wolfe. “On the Lattice Structure of FiniteGames”. In Richard Nowakowski, editor More Games of No Chance, pages25-30. Cambridge University Press, Mathematical Sciences ResearchInstitute Publications 42, 2002.

M. Albert, R. Nowakowski. “Lattices of Games”. Order, pages 75-84.Springer Netherlands, 29(1), 2012.


Estrutura

Alguns Resultados

A. Carvalho, Carlos Santos, C. Dias, F. Coelho, J. Neto, R. Nowakowski eS. Vinagre, “On Lattices from Combinatorial Game Theory: Infinite Case”,Order (impact factor, 2012 - 0.412), Springer, 2012 (aceite).

A. Carvalho, Carlos Santos, C. Dias, F. Coelho, J. Neto, R. Nowakowski eS. Vinagre, “On Lattices from Combinatorial Game Theory Modularity anda Representation Theorem: Finite Case”, Theoretical Computer Science(impact factor, 2012 - 0.665), 2012 (submetido).


Estrutura

A Outra Versao...

Normal Misere

Imparcial

Partizano

Sprague − Grundy

Temperatura

Peso Atomico

(. . .)

Quociente Misere

!?


Menos Restricoes

Quando Se Pode Passar...

Jogos Cıclicos: J pode ser um elemento de J E (ou de J R , ou de ambos)


Menos Restricoes

Quando Se Ganha de Outra Forma...

Jogos de Pontuacao


Menos Restricoes

Em Curso

Carlos Pereira dos Santos, Richard Nowakowski, Urban Larsson. “ScoringCombinatorial Game Theory: A Useful Universe” (em curso).


Documents

- Teoria de Jogos Combinat rios: Uma Breve Introdu ocelc.ciencias.ulisboa.pt/seminar/slides_2013/slid130527.pdf · Emanuel Lasker (1931) (sobre o nim de lasker): (...) Podemos provar