Programa de xadrez de Dietrich Prinz

Programa de xadrez de Dietrich Prinz
Desenvolvedor Dietrich Prinz ( d )
Diretor Dietrich Prinz
Início do projeto 1949
Data de lançamento Novembro de 1951
Gentil Programa de xadrez
Plataforma Ferranti Mark I

As falhas do programa Dietrich Prinz (às vezes chamado de Robot Chess ou mate-in-two ) funciona pela primeira vez emNovembro de 1951no Ferranti Mark I da Universidade de Manchester , o primeiro computador para uso comercial. Um pioneiro da inteligência artificial , é o primeiro programa de computador para xadrez a ser executado em um computador, apenas precedido pela teoria do programa de xadrez de Alan Turing , intitulada Turochamp .

Como parte de uma colaboração entre Ferranti e da Universidade de Manchester, o computador britânico Dietrich Prinz parte pioneira na criação do Ferranti Mark I e os seus protótipos, o TAU eo Manchester Mark I . Prinz desenvolve seu programa na Ferranti Mark I de 1949, programa que está operacional emNovembro de 1951. As capacidades limitadas do dispositivo tornam impossível jogar um jogo clássico de xadrez contra o computador e forçam Prinz a implementar apenas um estudo da final, especialmente esteiras de dois movimentos . Além disso, as regras são consideravelmente simplificadas, obscurecendo o roque , os movimentos de duas etapas do peão , o recebimento e a promoção ou a não distinção entre companheiro e pá . Prinz opta por uma busca exaustiva , que requer a avaliação de milhares de movimentos possíveis durante cada partida disputada. O programa, que é significativamente mais lento do que um humano, requer quase quinze minutos para cada curso. As transferências entre a memória magnética e a memória eletrônica, assim como os testes são as principais causas dessa lentidão.

Os observadores notam o aspecto rudimentar da programação, a lentidão do programa, mas notam o valor histórico da realização de Prinz. Este último nunca mais desenvolveu um programa de xadrez , em particular por causa do aumento de sua carga de trabalho na Ferranti.

Gênese

Dietrich Prinz é um pioneiro da ciência da computação de origem alemã , formado na Universidade Humboldt de Berlim, onde estudou com Max Planck e Albert Einstein . Sua condição de judeu o levou a fugir do Terceiro Reich em 1938, então ele se estabeleceu na Inglaterra . Ele adotou a nacionalidade britânica em 1947. Comumente conhecido por suas iniciais DP na Universidade de Manchester, Prinz era uma espécie de geek antes mesmo de o termo ser inventado, e um “discípulo” de Turing.

Avanços na pesquisa de radar e no hardware usado para criptologia durante a Segunda Guerra Mundial abriram o mundo da informática e facilitaram o desenvolvimento de computadores no final da década de 1940. Após a guerra, os negócios da empresa Ferranti começam a declinar, devido à falta de encomendas do Ministério da Defesa do Reino Unido . Eric Grundy, um gerente, forma uma equipe para estudar os usos potenciais dos computadores. Em 1947, ele nomeou Dietrich Prinz como responsável pela equipe de desenvolvimento de TI. Prinz trabalha em colaboração com a Universidade de Manchester no desenvolvimento de computadores. Ferranti já trabalhava com a universidade na década de 1930 para fabricar tubos de elétrons . Após dois meses de testes, a Máquina Experimental de Pequena Escala (SSEM, apelidada de bebê ) finalmente está funcionando. Assim que demonstrou a viabilidade de seu design, foi lançado um projeto para torná-lo um computador mais amigável: o Manchester Mark I , que rapidamente se tornou o protótipo do Ferranti Mark I , o primeiro computador generalista do mercado. É entregue emAgosto 1950na Universidade. Alan Turing e sua colega Cicely Popplewell trabalharam cerca de seis meses na interface do usuário, então o computador foi oficialmente finalizado emFevereiro de 1951.

Prinz aprende programação no Mark I por meio de seminários conduzidos por Turing e Popplewell. Ele vê a programação do xadrez "como uma pista para métodos que poderiam ser usados ​​para lidar com problemas estruturais ou logísticos que ocorrem em outras áreas, por meio de computadores eletrônicos" . Seu interesse em programas de xadrez de computador é provavelmente influenciado por Alan Turing. Prinz então executa seu programa de xadrez no Mark I, que vem desenvolvendo desde 1949. Rapidamente, Turing e Prinz concluem que nenhum programa no Mark I pode jogar uma partida completa de xadrez. Eles então decidem concentrar seus esforços na final dos jogos, em particular nos tatames de duas tacadas . Prinz provavelmente se inspirou, como Christopher Strachey e Donald Michie, por um artigo intitulado "  A Theory of Chess and Noughts and Crosses  " publicado no periódico Penguin Science News escrito em 1950 pelo cientista do National Physical Laboratory (NPL) Donald Davies. . Ele também teria sabido da existência de El Ajedrecista , que permite que o xadrez seja jogado no rei final e se volte contra o rei sozinho , e teria se inspirado por ele para realizar seu programa.

Dentro Novembro de 1951, seu programa no Mark I consegue resolver os mastros em dois movimentos .

Operação

As capacidades técnicas limitadas da Ferranti Mark Não exijo apenas que Prinz reduza os tapetes a dois movimentos . Para permitir que as tarefas sejam realizadas no menor tempo possível, algumas restrições são colocadas na forma como as regras são explicadas à máquina. Em particular, nenhuma distinção é feita entre mate e pat , o roque não é permitido, nem os movimentos de dois passos do peão , nem a recepção no passe , nem a promoção .

Cada jogo executado pelo programa requer a avaliação de vários milhares de movimentos, que é uma pesquisa de força bruta , ao contrário do Turochamp que realiza menos pesquisas porque é baseado em uma pesquisa de tipo heurístico . Prinz escolheu essa opção porque um jogo tão simplificado não precisa de pesquisa heurística.

O programa e a posição inicial das peças são fornecidos à máquina por meio de uma fita perfurada e transferidos para sua memória magnética. Uma rotina inicial transfere os dados para a memória eletrônica e, em seguida, o computador inicia os cálculos. O programa examina primeiro todas as casas conectadas à do rei pelo movimento de um cavaleiro, a fim de saber se esta última aparece no tabuleiro, quais casas são ocupadas, qual é a próxima peça e finalmente se é realmente um cavalo. Esta série de verificações é repetida para cada parte. O programa integra uma rotina de cálculo do próximo movimento possível, uma rotina responsável por verificar a legalidade do movimento e várias sequências cuja função é registrar o movimento e a posição obtida. Todas essas rotinas são comandadas por uma rotina mestre, que sintetiza a estrutura do problema como um todo e garante que as sub-rotinas se encaixem na seqüência correta. As técnicas de programação são rudimentares; a velocidade de execução do programa requer refinamentos e melhorias. O programa leva mais tempo para escolher um lance do que um jogador humano. Por exemplo, um único toque leva o computador quinze minutos para imprimir a solução.

Muito do tempo usado pelo programa é alocado para testes de autoverificação . A outra tarefa demorada é a transferência magnética de dados entre armazenamento magnético e eletrônico, como o de sub-rotinas e dados relativos a posições e movimentos. Nove dessas transferências de dados são feitas em cada foto. Em comparação, o tempo necessário para realizar os cálculos de deslocamento é de menor importância, mesmo que todos os movimentos possíveis e impossíveis sejam avaliados. Posições incorretas ou movimentos proibidos são rapidamente descartados pelo programa e representam apenas uma pequena parte do tempo de cálculo. Durante o primeiro problema de xadrez da história proposto ao programa, um simples movimento força o programa a verificar 450 movimentos possíveis, 100 dos quais são ilegais. O programa leva cerca de dois segundos para decidir cada um de seus movimentos.

O programa continua a ser revisado até que uma solução seja encontrada. Ele imprime cada lance branco testado e anuncia "  mate  " assim que um lance vencedor é encontrado. Não possui interface gráfica , sendo o resultado impresso em papel.

Primeiro problema de xadrez da história resolvido pelo programa

O programa deve encontrar um movimento para as brancas darem xeque-mate no próximo movimento, independentemente da escolha das pretas. As caixas são numeradas de forma anormal, da esquerda para a direita e de 11 a 18 para a linha inferior, a seguir de 21 a 28 para a segunda e assim por diante, até a linha mais alta (de 81 a 88). A caixa 68 está, portanto, na linha 6 e na coluna 8 (h6). O programa imprime todas as posições testadas e anuncia “  mate  ” quando encontra a solução. No diagrama à direita, é Rook em 68 ( "Tour em 68" ), ou seja, Th6. O programa já tentou as etapas P78 (gxh7), T17 (Tg1), T16 (Tf1), T15 (Te1), T14 (Td1), T13 (Tc1), T12 (Tb1), T11 (Ta1) na ordem, T28 (Th2), T38 (Th3), T48 (Th4), T58 (Th5). Esse problema é comumente atribuído, sem qualquer prova, ao prodígio americano Paul Morphy (1837-1884), bem antes da criação do programa.

Posteridade

O programa de xadrez de Dietrich Prinz é unanimemente referido como o primeiro programa de jogos a ser executado em um computador multifuncional, especialmente no primeiro computador comercial, o Ferranti Mark I , e é notável na história dos jogos . Como tal, também aparece na gênese dos videogames onde é citado em livros que tratam da história desse meio, como o primeiro jogo funcional em um computador. Ele também é um dos pioneiros no desenvolvimento da inteligência artificial . Jack Copeland , que escreveu extensivamente sobre a vida e a obra de Alan Turing , chama o programa de "um grande momento, o Big Bang do xadrez de computador" . Se o programa de Prinz resolver esteiras em dois movimentos deNovembro de 1951, não foi antes de 1958 e do programa proposto pelo americano Alex Bernstein no IBM 704 , ser capaz de jogar uma partida completa de xadrez contra um computador. De acordo com Copeland, apesar da simplicidade do programa e da escolha da pesquisa de força bruta, "a magnitude do que Prinz realizou é comparável ao primeiro vôo curto dos irmãos Wright .  "

Prinz publicado em 1952 todos os detalhes de seu programa no artigo "  Robot Chess  " revista Research ( n o  5, pp.  261-266 ). O artigo foi republicado em 1988 no livro Computer Chess Compendium ( pp.  213-219 ).

BV Bowden descreve o programa em seu livro de 1953, Faster Than Thought: Symposium on Digital Computing Machines . Para ele, isso só pode servir como um exemplo grosseiro da velocidade que um programa pode atingir e demonstra a necessidade de melhorar o hardware e a programação, para conseguir uma máquina capaz de jogar xadrez contra um humano. Considera que o programa pode ser melhorado em vários aspectos, nomeadamente ao nível da utilização da memória electrónica. Melhores técnicas de programação podem reduzir o tempo de computação, reduzindo a troca de dados entre os espaços de armazenamento. Ele critica severamente o programa, acrescentando que se este método de programação rudimentar é o único disponível, a competição em condições razoáveis ​​entre a máquina e o ser humano é irreal. Ele qualifica sua posição, porém, ao lembrar que o programa conseguiu resolver um problema em apenas algumas semanas de aprendizado, o que é um progresso bastante razoável para um jogador iniciante. Em 1972, Alex Bell também mencionou o programa em seu livro sobre a história dos programas de xadrez de computador, intitulado Games Playing with Computers . Como Bowden, ele acha o programa muito rudimentar para competir com humanos em condições razoáveis. Segundo Copeland, Turing provavelmente poderia ter aprimorado o código-fonte do programa, mas não o faz: ele sabe que a busca por força bruta, usada sozinha, não tem futuro e tem pouco interesse nela.

Prinz relata que o programa, uma vez operacional, nunca mais é usado. Ele acrescenta que como a quantidade de trabalho aumentou devido ao aumento do número de computadores, ele não tem conseguido lidar com tarefas menores, como programar jogos de xadrez. Além disso, um problema de xadrez um pouco mais complicado, disse ele, provavelmente exigiria horas de cálculos em um computador. Posteriormente, Prinz escreveu um manual para o Ferranti Mark I , um modelo de clareza, em contraste com os escritos por Turing, enquanto continuava a trabalhar na música de computador.

Referências

  1. (de) Detlef Borchers, "  Vor 50 Jahren fing alles an: das erste" Elektronenhirn "in Deutschland  " , no Heise Online ,6 de outubro de 2001.
  2. B. Jack Copeland, Jonathan Bowen e Mark Sprevak Robin Wilson , The Prinz Chess Program , Brute-force Chess , p.  339-342.
  3. S. Barry Cooper J. van Leeuwen , o trabalho de Turing em "máquinas pensantes": The Fourth faceta de um gênio , p.  875.
  4. (en) "  Ferranti Mark 1 Computador  " , no Museu de Ciência e Indústria .
  5. (in) EBITDA Napper, "  Introdução à Marca 1  " , na Universidade de Manchester .
  6. B. Jack Copeland Alan Mathison Turing , Capítulo 16: O primeiro programa prático de xadrez , p.  564-565.
  7. (em) "  Computer History Museum - movimentos de abertura: Origens do Xadrez computador - primeiros testes  " no Computer History Museum .
  8. (in) Thomas Dreher, "  IASLonline NETART: Theory  " em IASLonline .
  9. "  Computer Pioneers - Christopher Strachey  " , em IEEE Computer History (acessado em 3 de setembro de 2016 ) .
  10. Julian Alvarez e Damien Djaouti , "  Arcade: Os Pioneiros do jogo de vídeo  " ( Mook ), Pix'n Amor , Éditions Pix'n Amor , n o  11,2010, p.  32-43 ( ISBN  9782918272106 ).
  11. Bowden , p.  286-287.
  12. Alex G. Bell , Capítulo 5: Alguns programas de xadrez .
  13. (in) Jack Copeland , "  O que é Inteligência Artificial?  » , Em Alanturing.net ,Maio de 2000.
  14. (em) Rachel Kowert e Thorsten Quandt, The Video Game Debate: Unraveling the Physical, Social, and Psychological Effects of Video Games , Routledge ,2015, 204  p. ( ISBN  978-1-317-56717-2 e 131756717X , leia online ) , p.  3.
  15. Monografia Chessbase em CD-ROM Paul Morphy, Genius and Myth - Chessbase .
  16. (in) David Levy, Computer chess compendium , New York, Springer New York,1988, 440  p. ( ISBN  978-1-4757-1968-0 , leitura online ) , p.  213-219.

Bibliografia