Base de senyes de taules de finals

Archiu:Chess tablebase query.png

Un interfaç típic per a solicitar una base de senyes de taules. Per a cada moviment del Blanco, la base de senyes torna el número de moviments necessaris per a guanyar. Rc6 i Dona6+ gana en cinc moviments, per lo que són els moviments òptims.

Una base de senyes de taules de finals és una base de senyes computarizada de totes les posicions d'escacs dins de certs finals. La base de senyes de taules mostra el valor de cada posició segons la teoria del joc (victòria, derrota o taules) i quants moviments tardarà en conseguir eixe resultat en un joc perfecte. Aixina, la base de senyes actua com una màquina oracle, proporcionant sempre els moviments òptims per a les Blanques i les Negres.

Les bases de senyes de taules es generen per mig d'escacs retrospectiu, treballant cap a arrere des d'una posició de jaque mate. Les bases de senyes de taules han resolt l'escacs per a totes les posicions en sis o menys peces (incloent els dos reis). Els resultats de la solució han alvançat profundament en els coneiximents de la teoria de finals per part de la comunitat ajedrecística. Algunes posicions que els humans havien analisat com a taules es va provar que eren ganables, la base de senyes de taules podien vore un mate en 100 moviments o més, molt llunt de l'horisó dels humans i les computadores. Les bases de senyes han aumentat la competitivitat del joc i facilitat la composició d'estudis. Proporcionen una potent ferramenta analítica, permetent als estudiosos de l'escacs descobrir els seus secrets més profunts.

Orige

En principi, és possible resoldre qualsevol joc en la condició de que es conega l'estat complet i no hi haja cap oportunitat aleatòria. Les solucions fortes es coneixen per a alguns jocs simples, com les tres en ralla (taules en un joc perfecte) i el Conecta Quatre (el primer jugador guanya) i en juliol de 2007 per a les dames utilisant el "Chinook" (taules en joc perfecte). Atres jocs com l'escacs (des de la posició inicial) i el Go, no s'han resolt degut a que la seua complexitat és massa gran per a que els ordenadors evaluen totes les possibles posicions. Per a reduir la complexitat del joc, els investigadors han modificat estos jocs complexos reduint el tamany del tauler, el número de peces o abdós.

l'escacs per computadora és un dels terrenys més antics de l'inteligència artificial, havent escomençat en els anys 1940. Claude Shannon va propondre els criteris formals per a evaluar els moviments de l'escacs en 1949. En 1951, Alan Turing va dissenyar un programa primitiu que jugava a l'escacs, que assignava valors per a material i movilitat, el programa "jugava" a l'escacs basant-se en els càlculs manuals de Turing Plantilla:Harv. No obstant, inclús quan es varen escomençar a desenrollar programes d'escacs competents, varen exhibir una debilitat manifesta jugant els finals. Els programadors varen afegir heurístiques específiques per al final, per eixemple, el rei deuria moure's al centre del tauler. No obstant, era necessària una solució comprensible.

En 1965, Richard Bellman va propondre la creació d'una base de senyes per a resoldre finals d'escacs i dames utilisant escacs retrospectiu Plantilla:Harv. En lloc d'analisar cap a davant a partir de la posició actual, la base de senyes analisaria cap a arrere des de posicions a on un jugador dona jaque mate. Aixina, una computadora d'escacs no necessitaria analisar mai més posicions finals durant la partida perque estarien resoltes de bestreta. No tornaria a haver errors perque les bases de senyes de taules sempre jugarien el millor moviment possible.

En 1970, Thomas Ströhlein va publicar una tesis doctoral en anàlisis de les següents classes de finals: RDR, RTR, RPR, RDRT i RTRC. Ken Thompson i uns atres varen ajudar a estendre les bases de senyes per a cobrir tots els finals de quatre i cinc peces, incloent en particular RAARC, RDPRD i RTPRT. Lewis Stiller va publicar una tesis en investigacions sobre algunes bases de senyes de taules de finals en sis peces en 1995 Plantilla:Harv.

Els contribuents més recents són els següents:

• Eugene Nalimov pel que les base de senyes de taules de finals reben el seu nom.
• Eiko Bleicher, que ha adaptat el concepte de base de senyes de taules a un programa cridat "Freezer".
• Guy Haworth, un acadèmic de l'Universitat de Reading, que ha publicat intensivamente en el ICGA Journal.
• Marc Bourzutschky i Yakov Konoval, que han colaborat per a analisar els finals en sèt peces en el tauler.

Les primeres taules de finals per a 4 peces es varen construir al final dels anys huitanta, les de 5 peces en els 90 i l'anàlisis de tots els finals de fins a sis peces (incloent els dos reis) es va completar en 2006. (No obstant, les bases de senyes de taules en cinc peces contra un sol rei no s'han produït perque el resultat és casi sempre obvi.)

L'investigació de bases de senyes de sèt peces s'estimava que seria completada a finals de 2015. pero es varen conseguir en 2013 en Rússia gràcies a un superordenador cridat Lomonósov. Pel seu orige li les coneix com a taules Lomonosov. Ocupen 140 Terabytes pero pot consultar-se en la web sense ser descarregades per complet.

Generació de les bases de senyes

Mètriques: Profunditat de conversió i profunditat de mate

Abans de crear una base de senyes de taules, un programador té que elegir una mètrica de optimalidad, en atres paraules, es té que definir en quin punt un jugador ha guanyat la partida. Cada posició pot definir-se per la seua distància (p.ej. el número de moviments) des del punt final desijat. Generalment s'utilisen dos mètriques:

• Profunditat del mate (DTM, de l'anglés Depth to mat). El mate és l'únic camí considerat cap a la victòria.
• Profunditat de conversió (DTC, de l'anglés Depth to conversion). El costat atacant també pot guanyar capturant material, aixina convertint el final en un més simple. Per eixemple, en el final RDRT, la conversió ocorre quan el Blanco capture la torre Negra.

Haworth ha discutit atres dos mètriques, cridades Profunditat al Moviment Zero(DTZ, de l'anglés Depth to Zeroing-Move) i Profunditat per a la regla (DTR, de l'anglés depth by the rule). Estes mètriques es corrigen per a la regla dels cinquanta moviments i s'han llançat al públic unes quantes bases de senyes en estes mètriques.

La diferència entre DTC i DTM es pot comprendre analisant el diagrama a la dreta. Cóm deuria procedir el Blanco depén de quin mètrica s'utilise.

Mètrica	Jugades	DTC	DTM
DTC	1. Dxd1 Rc8 2. Dd2 Rb8 3. Dd8 mate	1	3
DTM	1. Dc7+ Ra8 2. Dona7 mate	2	2

D'acort en la mètrica DTC, el Blanco deuria capturar la torre perque "gana" immediatament (DTC = 1), pero li durà dos moviments més donar mat (DTM = 3). En contrast d'acort en la mètrica DTM, el blanc dona mat en dos moviments, aixina que DTM = DTC = 2.

Esta diferència és típica de molts finals. Normalment DTC és menor que DTM, pero la mètrica DTM du al mate més ràpit. Les excepcions ocorren quan el bando defensor solament té el rei i en l'estrany final de dos cavalls i rei contra rei i peó, a on DTC = DTM perque no hi ha material que defendre per a capturar o capturar el material no és bo. De fet, capturant el peó defensor en el final dona com resultat unes taules.

Pas 1: Generar totes les possibles posicions

Una volta que s'ha elegit una mètrica, el primer pas és generar totes les posicions en un material donat. Per eixemple, generar una base de senyes de taules DTM per al final de rei i dama contra rei (RDR), la computadora té que descriure les úniques 40.000 posicions llegals d'un array.

Levy i Newborn varen explicar que el número 40.000 derives d'un argument de simetria. El rei negre es pot situar en qualsevol de les dèu caselles: a1, b1, c1, d1, b2, c2, d2, c3, d3 i d4 (vore diagrama). En qualsevol atra casella, la seua posició es pot considerar equivalent per simetria, rotació o reflexió. Aixina, un rei negre en un cantó residirà en a1, a8, h8 o h1. Multiplicant este número 10 per com a molt 64 caselles per a colocar al rei blanc i llavors per com a molt 64 caselles per a la dama blanca. El producte 10×64×64 = 40.960. Varis centenars d'estes posicions són illegals, impossibles o reflexions simètriques d'una atra, per lo que el número real és alguna cosa menor Plantilla:HarvPlantilla:Harv.

Per a cada posició, la base de senyes evalua la situació de forma separada si mou el Blanco o el Negre. Assumint que el blanc té la dama, casi totes les posicions són guanyades pel blanc, en mate forçat en no més de 10 moviments. Algunes posicions són taules pel ofegat o l'inevitable pèrdua de la dama.

Cada peça adicional afegida a un final sense peons multiplica el número de posicions úniques per un factor d'aproximadament xixanta, el número aproximat de caselles no ocupades encara per atres peces.

Els finals en un o més peons incrementen la complexitat perque es reduïx l'argument de simetria. Com els peons es poden moure cap a davant, pero no cap a arrere la rotació i la reflexió vertical del tauler produïx un canvi fonamental en la naturalea de la posició. El millor càlcul de simetria és conseguit llimitant un peó a 24 caselles en el rectàngul a2-a7-d7-d2. El restant de les peces i peons es poden colocar en les atres 64 caselles sobre el peó. Aixina, un final en peons té una complexitat de 24/10 = 2.4 voltes un final sense peons en el mateix número de peces.

Pas 2: Evaluar les posicions utilisant un anàlisis retrospectiu

Tim Krabbé explica el procés de generació d'una base de senyes de taules com seguix:

"L'idea és que una base de senyes està composta de totes les posicions possibles en un material donat. Despuix, una subbase de senyes està composta per totes les posicions a on el negre és mat. Despuix, una a on el blanc pot donar mat. Despuix, una a on el negre no pot parar al Blanco donant mat al següent moviment. Despuix, una a on el Blanco sempre pot alcançar una posició a on el Negre no puga parar un mate al següent moviment. I aixina successivament, sempre un pas més allà del mate fins que es troben totes les posicions possibles. Llavors, totes estes posicions són enllaçades cap a arrere per a donar mat segons el camí més curt a través de la base de senyes. Açò significa que, a banda dels moviments 'equi-òptims', tots els moviments en este camí són perfectes: els moviments del Blanco sempre conduïxen al mate més ràpit, el moviment del Negre sempre conduïxen al mate més llent."

La Figura 1 ilustra l'idea de l'anàlisis retrospectiu. El Blanco dona mat en dos moviments en 1.Rc6, conduint a la posició en la Figura 2. Llavors si 1...Rb8 2.Db7 mate i si 1...Rd8 2.Dd7 mate (Figura 3).

La Figura 3, abans del segon moviment del Blanco, és definida com "mate en un ply". La Figura 2, despuix del primer moviment del Blanco, és "mate en dos ply" moga lo que moga el Negre. Finalment, la posició inicial en la Figura 1 és "mate en tres ply" (i.i., dos moviments) perque conduïx directament a la Figura 2, que ya està definida com "mate en dos ply". Este procés, que enllaça una posició actual a una atra posició que podria haver existit un ply abans, pot continuar indefinidament.

Cada posició s'evalua com una victòria o una derrota en un cert número de moviments. Al final de l'anàlisis retrospectiu, les posicions que no estan designades com a victòria o com a derrota necessàriament són taules.

Pas 3: Verificació

En acabant de que la base de senyes s'ha generat i s'ha evaluat cada posició, el resultar té que ser verificat independentment. El propòsit és comprovar l'auto-consistència dels resultats de la base de senyes.

Per eixemple, en la Figura 1 de dalt, el programa de verificació veu l'evaluació "mate en tres ply (Rc6)". Llavors s'observa la posició en la Figura 2, despuix Rc6 i es veu l'evaluació "mate en dos ply". Estes dos evaluacions són consistents l'una en l'atra. Si l'evaluació de la Figura 2 fora qualsevol atra, seria inconsistente en la Figura 1, en lo que la base de senyes necessitaria ser corregida.

Captures, promocions i moviments especials

Una base de senyes de quatre peces té que dependre de bases de senyes de tres peces que podrien donar com a resultat si es captura una peça. De la mateixa forma, una base de senyes que conté un peó té que ser capaç de dependre d'atres bases de senyes que incloguen un nou conjunt de material despuix d'una promoció d'un peó a una dama o una atra peça. El programa d'anàlisis retrospectiu té que tindre en conte la possibilitat d'una captura o promoció en el moviment anterior Plantilla:Harv.

Les bases de senyes assumixen que l'enroque no és possible per dos raons. Primer, en finals pràctics, esta suposició és casi sempre correcta (encara que, el enroque està permés per convenció en estudis i problemes composts.) Segon, si el rei i la torre estan en les seues caselles originals, el enroque pot estar permés o no. Per esta ambigüitat, seria necessari fer evaluacions separades per a estats en que el enroque és possible o no.

La mateixa ambigüitat existix per a la captura al pas, ya que la possibilitat d'una captura al pas depén del moviment previ de l'oponent. No obstant, les aplicacions pràctiques de la captura al pas ocorren freqüentment en finals en peons, en lo que les bases de senyes prenen en conte la possibilitat de la captura al pas per a posicions a on abdós bandos tenen a lo manco un peó.

Utilisant informació a priori

D'acort en el método descrit anteriorment, la base de senyes té que permetre la possibilitat de que una peça donada puga ocupar qualsevol de les 64 caselles. En algunes posicions, és possible restringir l'espai de busca són afectar el resultat. Açò aforra recursos computacionals i permet busques que d'una atra forma serien impossibles.

Un anàlisis primitiu d'este tipo va ser publicat en 1987, en el final RTP(a2)RAP(a3), a on l'alfil Negre es mou en les caselles negres (vore posició d'eixemple a la dreta). En esta posició, podem realisar les següents suposicions a priori:

1. Si una peça és capturada, podem mirar la posició resultant en la base de senyes corresponent en cinc peces. Per eixemple, si el peó Negre és capturat, es mira la recentment posició creada en RTPRA.

2. El peó Blanco permaneix en a2; els moviments de captura són gestionats per la regla número 1.

3. El peó Negre permaneix en a3; els moviments de captura són gestionats per la primera regla.

El resultat d'esta simplificació és que, en lloc de buscar 48 * 47 = 2.256 permutació per a les ubicacions dels peons, hi ha solament una permutació. Reduint l'espai de busca per un factor de 2.256 facilita un càlcul molt més ràpit.

Bleicher ha dissenyat un programa comercial cridat "Freezer", que permet als usuaris construir noves bases de senyes de taules de Nalimov existents en informació a priori. El programa pot produir una base de senyes per a posicions de sèt peces en peons bloquejats, inclús encara que les bases de senyes de taules no estiguen generalment disponibles.