aforismos e afins

02 março 2006

Quiz 9

Existirá no xadrez uma estratégia vencedora* para o jogador que abre o jogo? E uma estratégia de empate? Explique a(s) resposta(s).

*uma estratégia vencedora (estratégia de empate) será um conjunto (exaustivo) de respostas (ou reacções) tal que, qualquer que seja a movimentação escolhida pelo oponente, em qualquer momento do jogo, e qualquer que seja a história do jogo até esse momento, haverá sempre uma resposta (proveniente desse tal conjunto de regras, ou estratégia) que garanta a vitória (o empate) ao jogador que abre o jogo (às "brancas").

posted by Tiago Mendes at 10:14 da manhã

21 Comments:

  • Eu esta conheco, dos livros de teoria dos jogos, pelo que me abstenho de responder.
    LA-C

    By Anonymous Anónimo, at 10:30 da manhã  

  • Naturalmente, nao vale a pena por o ar o meu comentario anterior.

    LA-C

    By Anonymous Anónimo, at 10:49 da manhã  

  • RACC RACC

    By Anonymous Anónimo, at 11:39 da manhã  

  • Isto já me interessa

    Queres perguntar se existe uma estratégia pela qual se obtenha incondicionalmente uma vitória, ou seja, se a melhor resposta para todas as melhores jogadas for insuficiente para evitar a derrota.

    Do xadrês não sei, mas sei que no Go já foi provado que existe num tabuleiro 5x5. Acontece que o jogo é jogado em 19x19...

    By Blogger AA, at 4:17 da tarde  

  • Por "estratégia de empate" entende-se uma estratégia que conduzirá forçosamente a um empate, ou serve uma estratégia que tanto possa conduzir ao empate ou à vitória (conforme a reacção das "pretas")?

    By Blogger Miguel Madeira, at 10:59 da tarde  

  • "Por "estratégia de empate" entende-se uma estratégia que conduzirá forçosamente a um empate, ou serve uma estratégia que tanto possa conduzir ao empate ou à vitória (conforme a reacção das "pretas")? "

    Uma estratégia que conduza - com "habilidade" - à vitória, é uma estratégia vencedora.

    Não nos esqueçamos que o obejctivo do jogador é ganhar, não empatar. [Assumi que isto era dado].

    Logo, uma estratégia de empate é tal que, não conseguindo "impor" uma vitória, consegue ainda assim impor um empate. Isso não depende das pretas no sentido em que isso já está incluido, dado que a estratégia é a melhor resposta a qualquer situação que possa aparecer.

    By Blogger Tiago Mendes, at 11:06 da tarde  

  • Tiago, o teu "e qualquer que seja a história do jogo até esse momento" parece-me que está a mais. Deve assumir-se que até "ao momento" as brancas executaram a "estratégia vencedora"...

    By Blogger AA, at 3:27 da tarde  

  • "Tiago, o teu "e qualquer que seja a história do jogo até esse momento" parece-me que está a mais. Deve assumir-se que até "ao momento" as brancas executaram a "estratégia vencedora"..."

    O argumento e' subtil, mesmo para quem tneha algumas nocoes de teoria dos jogos. A diferenca, basicamente, esta' em nao confundir "equilibirum path" com "strategy". Para especificar a estrategica, e' preciso, se quisermos ser rigorosos, dizer o que eu disse, para podermos fazer backward and forward induction. Uma vez chegados 'a "estrategia", e assumindo que nao ha' "trembling errors", o "equilibrium path" nao e' mais que o resultado da combinacao das estrategias de todos os jogadores.

    Ilustracao: uma vez que falamos de jogos dinamicos (com "observability" das jogadas anteriores), uma estrategia constitui um profile de respostas para TODOS os nos do jogo. Contudo, em equilibrio so' alguns desses nos (ou ramos da arvore) e' que serao escolhidos. Mas para que isso aconteca, e' preciso especificar as respostas para todos os outros nos (a importancia do "off-the-equilibrium path").

    Para quem nao entendeu muito do que escrevi, fica desvendado o misterio de porque e' que nao escrevo mais posts sobre a minha "menina" (TEoria dos Jogos, that is): e' que as coisas interessantes estao muito para alem do debate com leigos (espero que isto nao caia mal: e' um statemente de facto e nao uma opiniao, e muito menos uma critica).

    By Blogger Tiago Mendes, at 3:39 da tarde  

  • Caro Tiago,

    Qure-me parecer que a questão do AA levanta um problema pertinente com a forma como formulaste a questão.

    Uma estratégia (no sentido empregue pela teoria dos jogos moderna) tem de englobar respostas para todos os nós possíveis do jogo mas uma estratégia vencedora não garante a vitória independentemente da "história do jogo até esse momento".

    Creio que uma estratégia vencedora nos termos em que a enunciaste ("uma estratégia vencedora para o jogador que abre o jogo") só garante a vitória se for seguida desde a abertura, situação em que muitas posições podem nunca ser atingidas. Assim sendo, postular que a estratégia vencedora garanta a vitória "qualquer que seja a história do jogo até esse momento" parece-me efectivamente abusivo.

    Uma estratégia vencedora para o jogador que abre o jogo (por ser uma estratégia e não por ser vencedora) terá de gerar respostas para qualquer posição possível do jogo mas não terá de garantir a vitória para todas essas situações, ao contrário do o Tiago afirma no seu asterisco.

    Não sei se era isto que o AA tinha em mente mas a verdade é que me parece haver mesmo um problema com a formulação do Tiago.

    By Blogger André Azevedo Alves, at 6:39 da manhã  

  • "Para quem nao entendeu muito do que escrevi, fica desvendado o misterio de porque e' que nao escrevo mais posts sobre a minha "menina" (TEoria dos Jogos, that is): e' que as coisas interessantes estao muito para alem do debate com leigos (espero que isto nao caia mal: e' um statemente de facto e nao uma opiniao, e muito menos uma critica)."

    Discordo em dois aspectos:

    1- Quanto à natureza da afirmação, já que é, efectivamente, uma opinião (sobre os requisitos para debater as "coisas interessantes" da teoria dos jogos).

    2- Quanto ao conteúdo dessa opinião, porque me parece que qualquer conceito ou problema de teoria dos jogos é perfeitamente explicável e debatível com leigos que tenham um mínimo de fundamentos matemáticos e boas bases de lógica (o que reduz muito o universo de leigos mas não o elimina). Tenho para mim, aliás, que mesmo ramos menos "imediatos" e "triviais" da matemática aplicada (ou mesmo teórica) sou perfeitamente compreensíveis para leigos (nesses ramos específicos) desde que tenham boas bases de lógica e um bocadinho de paciência (qualidades raras mas apesar de tudo não impossíveis de encontrar).

    Por outras palavras, qualquer bom filósofo (e entenda-se que não me refiro a 99,9% das macacadas que passam por "filosofia" nos dias que correm) não deverá ter problemas de maior em compreender matemática e, mais ainda, aplicações como a teoria dos jogos.

    O reverso é que já não é verdade.

    By Blogger André Azevedo Alves, at 6:55 da manhã  

  • E, para concluir, deixo uma provocação: é curioso que a "menina" do Tiago seja em larga medida uma excrescência (ainda que uma excrescência "simpática", se tal é possível...) de ovelhas tresmalhadas do rebanho da Escola Austríaca.

    É uma boa indicação da mediocridade dos tempos que correm (nos quais, obviamente, também me incluo) e da degradação a que chegou a ciência económica que tantos economistas hoje se concentrem em aprofundar algumas notas de rodapé do passado ao mesmo tempo que ignoram por completo os fundamentos da sua Ciência.

    A Viena do fim do Séc. XIX e início do Séc. XX era de facto um local fascinante...

    By Blogger André Azevedo Alves, at 7:07 da manhã  

  • Caro André,

    A note de rodapé - talvez essa seja a nota incompreendida, e assumo que podia ter sido mais claro - refere-se a uma estratégia vencedora EM QUALQUER MOMENTO DO JOGO, ou seja, vista do ponto de vista de qualquer momento t.

    Por isso é que digo:

    "uma estratégia vencedora será um conjunto (exaustivo) de respostas (ou reacções) tal que, qualquer que seja a movimentação escolhida pelo oponente, em qualquer momento do jogo (O MOMENTO NO QUAL SE AVALIA ESSA ESTRATEGIA), e qualquer que seja a história do jogo até esse momento, haverá sempre uma resposta (proveniente desse tal conjunto de regras, ou estratégia) que garanta a vitória".

    Ou seja, o ponto de análise é um qualquer momento do tempo. DEPOIS - só depois - de pensarmos genericamente em qualquer momento do tempo é que podemos focarmos no período inicial, isto é, na abertura do jogo. O argumento tem de ser apresentado desta forma "genérica", que é natural que suscite alguma confusão a leigos.

    Admito que poderia ter sito mais claro. Por outro lado, isso até acaba por reforçar o meu ponto, no sentido em que aquilo que referes (AAA) como crítica tem de ser "óbvio" para um não leigo, isto é, que se há uma estratégia vencedora GLOBAL ela é para ser levada a cabo a partir do momento inicial, e, consequentemente, a partir daí qualquer história de jogo que se desenhe, por definição, permitirá que as brancas tenham uma vitória. Isto assume - claro! - que o jogador que tem a estratégia vencedora a vai seguir sem fazer erros.

    "Uma estratégia (no sentido empregue pela teoria dos jogos moderna) tem de englobar respostas para todos os nós possíveis do jogo mas uma estratégia vencedora não garante a vitória independentemente da "história do jogo até esse momento"."

    Se existe uma estratégia vencedora na abertura do jogo, e ela é seguida pelas brancas, então, em qualquer período t posterior, será verdade que ela é ainda uma estratégia vencedora QUALQUER QUE TENHA SIDO A HISTORIA ANTERIOR, uma vez que estamos a assumir (claro) que as brancas seguem essa estratégia, sem erros, como disse anteriormente.

    "Uma estratégia vencedora para o jogador que abre o jogo (por ser uma estratégia e não por ser vencedora) terá de gerar respostas para qualquer posição possível do jogo mas não terá de garantir a vitória para todas essas situações, ao contrário do o Tiago afirma no seu asterisco."

    André, julgo que o que dizes não faz muito sentido. Uma estratégia tem de especificar resposta a todos os nós do jogo. Se é vencedora quer dizer que qualquer que sejam as respostas do oponente, em qualquer momento de jogo, haverá sempre uma forma de garantir a vitória.

    "Quanto ao conteúdo dessa opinião, porque me parece que qualquer conceito ou problema de teoria dos jogos é perfeitamente explicável e debatível com leigos que tenham um mínimo de fundamentos matemáticos e boas bases de lógica (o que reduz muito o universo de leigos mas não o elimina). Tenho para mim, aliás, que mesmo ramos menos "imediatos" e "triviais" da matemática aplicada (ou mesmo teórica) sou perfeitamente compreensíveis para leigos (nesses ramos específicos) desde que tenham boas bases de lógica e um bocadinho de paciência (qualidades raras mas apesar de tudo não impossíveis de encontrar)."

    Não vale a pena ir por aí. Percebo o teu ponto, mas claro que o problema aqui depende das noções de "leigo", "minimo fundamentos de matemática" e "boas bases de logica". Bem sei que gostas (eu também, ainda que menos) de "subjectivismo", mas há limites para tudo :)

    "Por outras palavras, qualquer bom filósofo (e entenda-se que não me refiro a 99,9% das macacadas que passam por "filosofia" nos dias que correm) não deverá ter problemas de maior em compreender matemática e, mais ainda, aplicações como a teoria dos jogos.

    O reverso é que já não é verdade."

    Concordo. Embora haja aqui alguma tautologia, no sentido de tu estares a IMPOR como componente para a DEFINICAO de um BOM FILOSOFO o ser capaz de raciocinios matemáticos de algum calibre.

    "E, para concluir, deixo uma provocação: é curioso que a "menina" do Tiago seja em larga medida uma excrescência (ainda que uma excrescência "simpática", se tal é possível...) de ovelhas tresmalhadas do rebanho da Escola Austríaca."

    É uma óptima provocação :)

    A TJ é por natureza subjectivista e já muitos problemas com isso. (E muito mais).

    "É uma boa indicação da mediocridade dos tempos que correm (nos quais, obviamente, também me incluo) e da degradação a que chegou a ciência económica que tantos economistas hoje se concentrem em aprofundar algumas notas de rodapé do passado ao mesmo tempo que ignoram por completo os fundamentos da sua Ciência."

    Eu sou um grande crítico de muitos fundamentos da economia enquanto ciência, como (acho que) sabes, portanto diria que concordo em geral com o teu ponto, embora tivessemos de ir mais ao detalhe para saber exactamaente o que criticamos.

    Espero ter clarificado... tell me if not.

    By Blogger Tiago Mendes, at 1:56 da tarde  

  • "A Viena do fim do Séc. XIX e início do Séc. XX era de facto um local fascinante..."

    Seriam virtudes do "multiculturalismo"?

    By Blogger Miguel Madeira, at 12:08 da manhã  

  • "A note de rodapé - talvez essa seja a nota incompreendida, e assumo que podia ter sido mais claro - refere-se a uma estratégia vencedora EM QUALQUER MOMENTO DO JOGO, ou seja, vista do ponto de vista de qualquer momento t."

    Ok. Esclarecido. Julgo que a possível falta de clareza resulta da conjunção da nota com a referência inicial à abertura do jogo.

    By Blogger André Azevedo Alves, at 2:02 da manhã  

  • "André, julgo que o que dizes não faz muito sentido. Uma estratégia tem de especificar resposta a todos os nós do jogo. Se é vencedora quer dizer que qualquer que sejam as respostas do oponente, em qualquer momento de jogo, haverá sempre uma forma de garantir a vitória."

    Como escrevi, a estratégia vencedora nos termos em que a enunciaste ("uma estratégia vencedora para o jogador que abre o jogo") só garante a vitória se for seguida desde a abertura, situação em que muitas posições podem nunca ser atingidas. Assim sendo, postular que a estratégia vencedora garanta a vitória "qualquer que seja a história do jogo até esse momento" parece-me efectivamente abusivo.

    Como já esclareceste que a nota é geral e nãpo se refere às condições específicas em que o problema é colocado, a questão está esclarecida.

    By Blogger André Azevedo Alves, at 2:05 da manhã  

  • "Percebo o teu ponto, mas claro que o problema aqui depende das noções de "leigo", "minimo fundamentos de matemática" e "boas bases de logica". Bem sei que gostas (eu também, ainda que menos) de "subjectivismo", mas há limites para tudo :)"

    Fair enough. Mas pensa no seguinte: quantos leigos entendem a noção de vantagens comparativas? A mim parece-me mais fácil reunir os requisitos para a TJ do que para outros aspectos que até parecem mais simples...

    By Blogger André Azevedo Alves, at 2:07 da manhã  

  • "Assim sendo, postular que a estratégia vencedora garanta a vitória "qualquer que seja a história do jogo até esse momento" parece-me efectivamente abusivo."

    Mas não é abusivdo exactamente porque temos ela é seguida desde a primeira jogada. Logo, a vitória - por definição - está garantida, qualquer que seja a história do jogo desde o início.

    "Fair enough. Mas pensa no seguinte: quantos leigos entendem a noção de vantagens comparativas? A mim parece-me mais fácil reunir os requisitos para a TJ do que para outros aspectos que até parecem mais simples..."

    Quanto à vantagem comparativa, não posso estar mais de acordo... julgo até que grande parte dos estudantes de economia serão incapazes de explicar isso. Quanto aos requisitos para a TJ, depende, claro, de que requisitos falamos. Por exemplo, o argumento de "backwards induction" é relativamente simples. Mas podes por perguntas altamente "filosóficas" (até podia ter tirado as aspas) sobre esse conceito e a sua razoabilidade.

    Conheces o "Centipede Game"? Se sim, saberás certamente do que falo... Depois há os problemas epistemológicos da racionalidade e do "common knowledge of rationality", para não falar no problema de usarmos estratégias mistas, quando o Independent Axiom pode não ser razoável (o que não permite, consequentemente, utilizar a "utilidade esperada"). E, outro exemplo, o argumento de "forward induction" também tem as suas complicações. Tal como o "Cho-Kreps refinement".

    Enfim, como em tudo, depende do que estivermos a falar. Se for sobre estratégias dominantes e dilemas de prisioneiros, tudo bem, é acessível. Mas há muita coisa também interessante que, infelizmente, requer algum estudo e, sobretudo, alguma reflexão aprofundada. Não digo que fosse esse o caso aqui, mas a noção e a improtância do "off-the-equilibrium-path" é crucial e nada fácil de adquirir.

    By Blogger Tiago Mendes, at 6:17 da tarde  

  • "Mas pensa no seguinte: quantos leigos entendem a noção de vantagens comparativas? A mim parece-me mais fácil reunir os requisitos para a TJ do que para outros aspectos que até parecem mais simples.."

    "Quanto à vantagem comparativa, não posso estar mais de acordo... julgo até que grande parte dos estudantes de economia serão incapazes de explicar isso"

    Sem querer desviar a conversa para um tema off-the-topic, não se pode censurar os leigos por não perceberam a "vantagem comparativa", já que os defensores da TVC também não percebem os argumentos dos "leigos".

    Normalmente, os protecionistas argumentam que, com comércio livre:

    a) a indústria dos paises ricos vai ser destruida pela concorrencia dos baixos salários dos paises pobres;

    ou

    b) a indústria dos paises pobres vai ser destruida pela concorrência da alta produtividade dos paises ricos;

    Quando ouvem estes argumentos, os economistas sacam logo da "teoria da vantagem comparativa". Mas um dos pressupostas da TVC é uma dotação fixa de recursos por pais (i.e., um "fronteira de possibilidades de produção" fixa). Ora, como os argumentos protecionistas, normalmente, têm a ver o perigo de "a industria ser destruida" (ou nem chegar a se desenvolver), quer dizer que eles estão a raciocinar no pressuposta que a dotação de factores produtivos variar com o tempo.

    Assim, acho que quando alguém evoca a TVC para criticar o protecionismo, demonstra que nem chegou a compreender os argumentos protecionistas (ou então, que decorou a TVC sem perceber os seus próprios pressupostas).

    (note-se que eu não estou a dizer que o protecionismo seja bom, apenas que a TVC não serve para o refutar)

    By Blogger Miguel Madeira, at 10:29 da tarde  

  • http://www.wto.org/english/res_e/reser_e/cadv_e.htm

    Nobel laureate Paul Samuelson (1969) was once challenged by the mathematician Stanislaw Ulam to "name me one proposition in all of the social sciences which is both true and non-trivial." It was several years later than he thought of the correct response: comparative advantage. "That it is logically true need not be argued before a mathematician; that is is not trivial is attested by the thousands of important and intelligent men who have never been able to grasp the doctrine for themselves or to believe it after it was explained to them." 1/

    By Anonymous Anónimo, at 6:48 da tarde  

  • Excelente contributo, LA-C, tx.

    By Blogger Tiago Mendes, at 6:57 da tarde  

  • Está mal. Fuga sem resposta.

    By Anonymous Anónimo, at 4:54 da tarde  

Enviar um comentário

<< Home