A game of pawns

Estratégia vencedora

Estratégia vencedora, exemplo:

O jogo é "finito" e existe estratégia vencedora

Se o jogador um falou n, diga n+1

• Existe estratégia vencedora?

Como as jogadas são finitas, então o jogador 1 tem

J1, J2, J3, ..., Jn jogadas

e dependendo de cada jogada do jogador 1 o jogador 2 tem

K1, K2, K3, ..., Km jogadas

Supor que o jogador 2 não tem estratégia vencedora

Supondo que o jogador 1 começa, então existem Jn jogadas possíveis

O jogador 1 tem outras t jogadas

onde destas jogadas, existe uma em que o jogador 2 não terá a jogada ou uma sequêcia de jogadas que é vencedora

O jogador 1 faz então a jogada

Jp

O jogador 2 então faz uma jogada Km

em que ele não ganhará

Fazendo essa interação várias vezes...

Como o jogador 2 não fez a jogada vencedora

em nenhuma das suas jogadas...

O jogador 1 vai ganhar!!!

A3

A4

Exemplo

Jogo da velha

Dois Jogadores

Estratégia Jogador 1: A do apresentador

Estratégia Jogador 2: Sigma

• Jogo do número mais alto:

É aquela estratégia que um jogador possui, tal que não importa como o outros jogadores joguem, estes outros vão sempre perder

Um jogo de peões

A Game of Pawns

O que é Jogo?

especificando um pouco mais...

Estratégias

Mais especificamente...

De uma forma mais específica...

Sequência de passos que lhe dirão como jogar em função das jogadas dos seus oponentes

"...the determination of the basic long-term goals and objectives of an enterprise, and the adoption of courses of action and the allocation of resources necessary for carrying out these goals"

Vamos trabalhar com jogos "finitos",

i.e., jogos em que o número de jogadas é finito e com um número finito de jogadores

"Um jogo é um sistema no qual os jogadores envolvem-se em um conflito artificial, definida por regras, que determina um resultado quantificável". (Katie Salen e Eric Zimmerman)

"Um jogo é uma forma de arte na qual os participantes, denominado jogadores, tomar decisões, a fim de gerir os recursos através de elementos de jogo na busca de um objetivo." (Greg Costikyan)

"Um jogo é uma atividade entre dois ou mais tomadores de decisão independentes que procuram atingir os seus objetivos em um contexto de limitação." (Clark C. Abt)

"Em seu nível mais elementar, então podemos definir jogo como um exercício de sistemas de controle voluntário em que há uma oposição entre forças, confinados por um procedimento e as regras a fim de produzir um resultado de desequilíbrio". (Elliot Avedon e Brian Sutton-Smith)

Em Inteligência Artificial, um jogo é um modelo teórico de conflitos de interesse (decisões possíveis, resultados possíveis) entre dois ou mais agentes que tem motivações conflitantes.

Jogo vai ser partida para qual existe uma condição de vitória entre os jogadores e

cada um deve fazer sua jogada a partir das jogadas dos outros jogadores

Exemplos: Tic-Tac-Toe, Go, Hex

Exemplo: Sigma:Jogue sempre na primeira coluna, de cima para baixo, e, se não for possível, jogue randômico

"A rule that tells the player which action to choose at each instant of the game."

Exemplos: Jogo da velha, xadrez, damas, etc...

GANHOU!!

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Corrida de peões

GANHOU!!

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

• É um jogo com dois jogadores
• É um jogo finito
• O "tabuleiro" é uma árvore
• Ganha o jogador que chegar primeiro em um folha

Ganhou!!

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Jogador 2

Até agora...

Vimos como funciona o jogo e a hipótese de que

nesse jogo deve existir um jogador com a estratégia

vencedora

O que vou fazer agora...

Vou supor por absurdo que todos os jogadores 2

tem estratégia vencedora, e assim chegar em uma

contradição

Jogador 2

Jogador 1

Jogador 2

Jogador 1

Em um jogo finito que não empata, um dos jogadores sempre tem estratégia vencedora

Árvore 1

Árvore 2

Árvore 1

Árvore 2

Árvore 1

Árvore 2

A1

A0

A2

A3

J1, J2, J3, J4, ..., Jn

. . .

Por simplicidade vamos supor também que tem apenas dois jogadores

P

J3

J2

J1

O jogador 1 vai ter uma estratégia vencedora, basta:

=

"Jogar pra não perder"

Jogar na defensiva

A1

A0

A2

A3

. . .

P

J3

J2

J1

A1

A0

A2

A3

Ai

A1

A0

A2

A3

A1

A0

A2

A3

. . .

P

J3

J2

J1

P

Ji

J3

J2

J1

P

J3

J2

J1

O jogador 2 não tem estratégia vencedora

Necessariamente o jogador 1 tem a estratégia vencedora

Ai

A1

A0

A2

A3

A1

A0

A2

A3

A1

A0

A2

A3

. . .

P

Ji

J3

J2

J1

J3

J2

J1

P

J3

J2

J1

A1

A0

A2

A3

Jogada do jogador J2

. . .

P

J2

J1

J3

A1

A0

A2

A3

. . .

Ai+1

Ai

A1

A2

A3

A0

P

J3

J2

J1

A1

A0

A2

A3

Referências

Galvin's "Racing Pawns" Game and a Well Ordering of Trees (Memoirs of the American Mathematical Society)

Wikipedia

. . .

Ji+1

Ji

J3

J2

J1

P

J3

J2

J1

A1

A0

A2

A3

. . .

P

J2

J1

J3

A1

A0

A2

A3

. . .

P

J3

J2

J1

Ai

Ai+2

Ai+1

Ki

Ki+1

Ki+2