Enseñando a jugar a mi PC

Português: Ensinando meu PC a Jogar (traducido por Clube Torre21)

Mi PC me conoce bien. Durante años, me ha visto jugar muchas partidas por Internet, suficientes para saber que soy verdaderamente malo. Por eso cuando me decidí a darle algunos consejos para jugar al ajedrez, se le pusieron los voltios de corbata. Nunca lo ha confesado, pero fue una experiencia interesante.

Unos años atrás, escribí un programa para que él pudiese jugar al ajedrez y yo aprender como se hacia. Para hacerlo, seguí con devoción las enseñanza de David Levy contenidas en su libro “Manual de Ajedrez por computadora”. Siempre que tengo ocasión lo recomiendo, no es para programadores.

Lo más importante que aprendí es que "la espina dorsal" de todos los programas, es el árbol de variantes. Este surge cuando, a partir de una posición dada, se analizan todos los movimientos que el jugador al que le toca mover puede realizar, a continuación las distintas respuestas de su rival a cada uno de esos movimientos y así sucesivamente.

Lo primero que uno piensa, es que será necesario explorar exhaustivamente todas las posibilidades de movimiento-respuesta para poder emitir un veredicto matemáticamente irrefutable, pero no es cierto, afortunadamente (?) no es cierto.

La idea que refuta ese primer pensamiento es muy sencilla. Cuando usted analice sus posibles jugadas, durante una partida, sólo debe preocuparse por las respuestas de su rival que más daño pueden hacerle y muy poco por las que serían un error de aquel, porque no las hará. Por ejemplo, me toca mover, empiezo a analizar una de las jugadas que puedo realizar y veo que, haga lo que haga mi adversario, ganó un peón limpio. A continuación, empiezo el análisis de otra de mis posibles jugadas y me doy cuenta de que si la realizo, mi rival dispone de una respuesta que conduce a que sea yo quien pierda un peón, sería una perdida de tiempo seguir analizando otras respuestas de mi rival a esta segunda jugada mía, por mucho que puedan favorecerme, mi rival hará esa en la que yo pierdo un peón y tampoco me importa si con otras puedo llegar a perder aún más material, ya se lo suficiente para no realizar esta jugada cuando tengo a mi disposición la primera que analicé. Esto es en realidad lo que hacemos todos cuando jugamos, o lo que deberíamos hacer, y que como es natural es lo primero que le hemos enseñado a los PC.

Para que nos hagamos una idea de la utilidad de este principio, se ha comprobado que, por termino medio, al aplicar esta estrategia es posible descartar el 95% de todas las jugadas mecánicamente posibles.

Decimos término medio porque hay veces que no se consigue descartar ni una sola posibilidad y otras en las que se hace con el 99%, o más de las mismas.

¿De que depende?

Fundamentalmente depende de lo temprano, o tarde, que aparezca la mejor jugada posible, o al menos una buena. Si tenemos la suerte de que la primera jugada analizada es la mejor posible, al analizar cualquier otra jugada, es muy probable que rápidamente encontremos respuestas del rival que nos dejan en peor situación que con la jugada buena y que por lo tanto, no tengamos que profundizar inútilmente en el análisis de las mismas. Nuevamente, esto es lo que todos los jugadores tratan de hacer de una forma intuitiva y que a veces se denomina selección de "jugadas candidatas".

Pues bien, después de tan largo rodeo hemos llegado al punto donde yo estaba dispuesto a mejorar el juego de mi PC, dándole algún consejo sobre por donde empezar a analizar para encontrar rápidamente una buena jugada. El éxito en esta tarea es la diferencia entre un buen y un mal programa.

El Libro de D. Levy contiene poderosos métodos para decidir por donde empezar a buscar y naturalmente mi PC ya los conocía, de lo que ahora se trataba era de ir un poco más allá, al menos más allá de lo que habíamos encontrado navegando por Internet, con lo que nos metíamos en un terreno armados sólo de mis conocimientos de Ajedrez, en otras palabras, estábamos perdidos.

Pero nos quedaba el más humano de todos los métodos científicos, el de prueba y error. Así que allí estábamos, dispuestos a probar hasta donde hiciese falta.

Aunque no obtuvimos frutos a la primera, tengo que reconocer que hubo suerte, porque ideas no había muchas y sonó la flauta sin tener que errar en demasía.

La idea del éxito nace de una reflexión, que sin duda Pero Grullo habría incorporado a su repertorio: "Sólo se gana material mediante capturas", así que la consigna a seguir fue "analizar primero los movimientos que realizan capturas y el primero el que más capture".

La forma de valorar los méritos de las distintas estrategias es muy sencilla. Dado que se trata de encontrar la mejor jugada analizando el mínimo de posiciones (descartando cuanto antes las malas jugadas) la mejor estrategia es la que alcanza la solución considerando menos posiciones.

Conviene aclarar que todas las estrategias deben conducir a la misma solución[1], las variantes no se descartan porque a la "estrategia" le parezcan más o menos buenas, se hace porque se sabe que matemáticamente no pueden conducir a una jugada mejor, que otra que se ha encontrado previamente. Por lo tanto no cabe decir "vale, esa estrategia es muy rápida pero conduce a una jugada peor que esa otra”, en nuestro caso la más rápida es la mejor sin paliativos.

Aclarado esto, ya podemos mostrar que es lo que pasa cuando el PC incorpora la consigna antes mencionada. En la tabla siguiente se muestran los resultados obtenidos en tres posiciones diferentes:

La posición inicial

Una posición de la apertura Rui López

Posición del medio juego de la partida “Shirov, A. - Kurajica, B” disputada en el Bosnia GM Sarajevo BIH del 2004.

El PC analizó las posiciones, sin usar libro de aperturas, con una profundidad mínima de 6 movimientos y de hasta 20 según las necesidades tácticas. En el caso de la primera posición (la posición inicial), se utilizó una profundidad entre 8 y 22 movimientos porque entre  6 y 20 tarda demasiado poco para poder comparar (menos de 1 segundo).

Los resultados son realmente sorprendentes, máxime si tenemos en cuenta que los cálculos "sin la nueva estrategia" ya incluyen un algoritmo de reducción de variantes muy eficiente que se conoce como la estrategia del movimiento ganador[2], sin la presencia de este algoritmo la diferencia de tiempos, sin y con la nueva estrategia, es muchísimo mayor. En la posición de la partida de Shirov, al usar la nueva estrategia el tiempo se reduce a la centésima parte.

Sin La estrategia de Movimiento ganador

Cuanto más compleja es la posición, en el sentido de que el número de movimientos posibles es mayor, más importante es la ganancia. En la partida de Shirov, las blancas disponen de 52 movimientos en su primera jugada y el tiempo (al incorporar la nueva estrategia) se divide por 20, si la aplicación tiene incorporada la estrategia de movimiento ganador, o por 100 si no la tiene. Además cuando se aumenta la profundidad del análisis, el ahorro de posiciones y por lo tanto de tiempo, no se mantiene en terminos proporcionales si no que cada vez es mayor.

¿Cómo puede una estrategia tan burda y quizás incorrecta, ser tan eficiente?. Mi PC y yo no lo sabemos. Es posible que la inmensa mayoría de las jugadas mecánicamente posibles sean malas, como ir poniendo la Dama a tiro de todas las piezas rivales. Si lo malo es lo más abundante (pasa a menudo) y esta consigna es experta en descartar malas jugadas podríamos tener la explicación.

Al margen de la “curiosidad técnica” contenida en estas notas, me gustaría que ellas aportasen algo en desagravio de las aplicaciones informáticas que juegan al ajedrez y a las que a menudo se califica como "de pura fuerza bruta". Es cierto que su potencia de juego se basa en la capacidad de procesar enormes cantidades de posiciones en poquísimo tiempo, pero no es menos cierto que lo hacen siguiendo patrones traídos de la experiencia humana, e incluso aplicados al "modo humano". Hace tiempo leí un artículo del GM P. San Segundo, que más o menos decía, que al igual que los aviones tenían una forma de volar muy distinta a la de los pájaros, los programas de ajedrez tienen una forma de jugar distinta a la de los hombres. No seré yo quien le contradiga, pero encuentro que los hombres hemos enseñado el ajedrez a las máquinas, más a nuestra imagen y semejanza, que los aviones lo son a los pájaros. Lo cual no sería de extrañar ya que nosotros no sabemos volar.

Ensinando meu PC a Jogar

Meu PC me conhece bem. Durante anos, viu-me jogar muitas partidas pela Internet, suficientes para saber que sou verdadeiramente ruim. Por isso, quando me decidi a dar-lhe alguns conselhos para jogar xadrez, os chips colocaram gravata. Nunca confessou, mas foi uma experiência interessante.

Há alguns anos atrás, escrevi um programa para que ele pudesse jogar xadrez e eu aprender como se faz. Para fazê-lo, segui com devoção as ensino de David Levy contidas em seu livro "Manual de Ajedrez por computadora". Recomendo-o, sempre que tenho oportunidade, não é para programadores.

O mais importante que aprendi é que "a espinha dorsal" de todos os programas é a árvore de variantes. Esta surge quando, a partir de uma posição dada, analisa-se todos os movimentos que o jogador a quem cabe mover pode realizar, a seguir as diferentes respostas de seu rival a cada um desses movimentos e assim sucessivamente.

O primeiro pensamento é que será necessário explorar exaustivamente todas as possibilidades de movimento-resposta para poder emitir um veredicto matematicamente irrefutável, mas isso não é verdadeiro, felizmente (?) não é verdadeiro.

A idéia que refuta esse primeiro pensamento é muito simples. Quando você analisa suas possíveis jogadas, durante uma partida, só deve preocupar-se pelas respostas de seu rival que mais dano podem fazer-lhe e muito pouco pelas que seriam um erro daquele, porque não as fará. Por exemplo: é minha vez de jogar. Começo a analisar uma das jogadas que posso realizar e vejo que, faça o que faça meu adversário, ganho um peão limpo. A seguir, começo a análise de outra de minhas possíveis jogadas e me dou conta de que, se a realizo, meu adversário dispõe de uma resposta que leva a que seja eu quem perca um peão. Seria uma perda de tempo continuar analisando outras respostas de meu adversário a esta segunda jogada minha, por muito que possam favorecer-me, meu rival fará essa na qual eu perco um peão e também não me importa se com outras posso chegar a perder ainda mais material. Já sei o suficiente para não realizar esta jogada, quando tenho a minha disposição a primeira que analisei. Isso é, em realidade, o que fazemos todos quando jogamos, ou o que deveríamos fazer, e que, como é natural, é a primeira coisa que ensinamos aos PC.

Para que tenhamos uma idéia da utilidade desse princípio, comprovou-se que, em média, ao aplicar esta estratégia, é possível descartar 95% de todas as jogadas mecanicamente possíveis.

Dizemos em média porque há vezes em que não se consegue descartar nem uma só possibilidade e outras em que se faz com o 99%, ou mais das mesmas.

De que depende?

Fundamentalmente depende do cedo ou tarde que apareça a melhor jogada possível, ou ao menos uma boa. Se tivermos a sorte de que a primeira jogada analisada é a melhor possível, ao analisar qualquer outra, é muito provável que rapidamente encontremos respostas do rival que nos deixam em pior situação do que com a jogada boa e que, portanto, não tenhamos que aprofundar inutilmente a análise das mesmas. Novamente isto é o que todos os jogadores tratam de fazer de uma forma intuitiva e que às vezes se denomina seleção de "jogadas candidatas".

Pois bem, depois de tantos rodeios, chegamos ao ponto em que eu estava disposto a melhorar o jogo de meu PC, dando-lhe algum conselho sobre por onde começar a analisar para encontrar rapidamente uma boa jogada. O sucesso nesta tarefa é a diferença entre um bom e um mau programa.

O Livro de D. Levy contém poderosos métodos para decidir por onde começar a procurar e naturalmente meu PC já os conhecia. Agora, tratava-se de ir um pouco além, ao menos além do que tínhamos encontrado navegando pela Internet, com o que nos metíamos num terreno armados só de meus conhecimentos de Xadrez, em outras palavras, estávamos perdidos.

Mas nos restava o mais humano de todos os métodos científicos, o de tentativa e erro. Assim, ali estávamos, dispostos a tentar até onde fosse necessário.

Ainda que não obtivemos frutos na primeira, tenho que reconhecer que tive sorte, porque idéias não tinha muitas e soou a flauta sem ter que errar em demasia.

A idéia do sucesso nasce de uma reflexão que sem dúvida Pero Grullo teria incorporado a seu repertório: "Só se ganha material mediante capturas", assim que o método a seguir foi "analisar primeiro os movimentos em que se realizam capturas, e primeiro o que mais capture".

A forma de valorizar os méritos das diferentes estratégias é muito simples. Dado que se trata de encontrar a melhor jogada analisando o mínimo de posições (descartando, o quanto antes, as más jogadas) a melhor estratégia é a que atinge a solução considerando menos posições.

Convém esclarecer que todas as estratégias devem conduzir à mesma solução [1], as variantes não são descartadas porque à "estratégia" lhe pareçam mais ou menos boas. Faz-se porque se sabe que matematicamente não podem conduzir a uma jogada melhor do que outra que se encontrou previamente. Portanto, não cabe dizer "tudo bem, essa estratégia é muito rápida, mas conduz a uma jogada pior do que essa outra", em nosso caso a mais rápida é a melhor sem paliativos.

Esclarecido isso, já podemos mostrar o que acontece quando o PC incorpora o método antes mencionado. Na tabela seguinte, mostram-se os resultados obtidos em três posições diferentes:

A posição inicial

Uma posição da abertura Rui López

Posição do meio-jogo da partida "Shirov, A. - Kurajica, B" disputada na Bósnia GM Sarajevo BIH de 2004

O PC analisou as posições, sem usar livro de aberturas, com uma profundidade mínima de 6 movimentos e de até 20 segundo as necessidades táticas. No caso da primeira posição (a posição inicial), utilizou-se uma profundidade entre 8 e 22 movimentos porque entre 6 e 20 demora muito pouco para poder comparar (menos de 1 segundo).

Os resultados são realmente surpreendentes, mais ainda se levamos em conta que os cálculos "sem a nova estratégia" já incluem um algoritmo de redução de variantes muito eficiente, que é conhecido como a estratégia do movimento ganhador [2]. Sem a presença deste algoritmo, a diferença de tempos, sem e com a nova estratégia, é muitíssimo maior. Na posição da partida de Shirov, ao usar a nova estratégia, o tempo é reduzido à centésima parte.

Sem A estratégia de Movimento ganhador

Quanto mais complexa é a posição, no sentido de que o número de movimentos possíveis é maior, mais importante é o ganho. Na partida de Shirov, as brancas dispõem de 52 movimentos em sua primeira jogada e o tempo (ao incorporar a nova estratégia) divide-se por 20, se a aplicação tem incorporada a estratégia de movimento ganhador, ou por 100 se não a tem. Ademais, quando se aumenta a profundidade da análise, a economia de posições, e portanto de tempo, não se mantém em termos proporcionais, mas é cada vez maior.

Como pode uma estratégia tão tola e talvez incorreta ser tão eficiente? Meu PC e eu não sabemos. É possível que a imensa maioria das jogadas mecanicamente possíveis sejam más, como ir pondo a Dama "na linha de fogo" de todas as peças rivais. Se o ruim é o mais abundante (acontece com freqüência), e este método é "expert" em descartar más jogadas, poderíamos ter a explicação.

À margem da "curiosidade técnica" contida nestas notas, gostaria que elas contribuíssem um pouco em desagravo das aplicações informáticas que jogam xadrez e às que com freqüência são qualificadas como "de pura força bruta". É verdade que sua potência de jogo se baseia na capacidade de processar enormes quantidades de posições em pouquíssimo tempo, mas não é menos verdade que o fazem seguindo padrões trazidos da experiência humana, e inclusive aplicados ao "modo humano". Há tempo, li um artigo do GM P. San Segundo, que dizia que assim como os aviões tinham uma forma de voar muito diferente da dos pássaros, os programas de xadrez têm uma forma de jogar diferente da dos homens. Não serei eu quem vai contradizer-lhe, mas pondero que os homens ensinamos o xadrez às máquinas mais a nossa imagem e semelhança do que os aviões o são aos pássaros. O que não seria de estranhar, já que nós não sabemos voar.

[1] Pode ocorrer que haja diferentes variantes que forçadamente conduzam à mesma posição, ou a posições diferentes, mas com valorações idênticas, pelo que uma estratégia pode conduzir a uma delas e outra a uma diferente, em função de qual se encontre primeiro. Mas isto não é obstáculo para afirmar que todas conduzem à melhor solução, o que acontece é que esta melhor solução não é única.

[2] O algoritmo do movimento ganhador consiste em recordar o movimento que refuta uma determinada jogada para prová-lo em primeiro lugar quando se analisa a seguinte possibilidade de mover, uma vez mais, algo que passa pela cabeça dos jogadores durante suas partidas.