Escacs per ordinador

Els escacs per ordinador és una modalitat de joc que intenta programar ordinadors capaços de competir amb humans en el joc dels escacs, un camp que ha tingut molta influència en els debats sobre la intel·ligència artificial.

Al segle xviii es va començar a difondre la idea de crear un ordinador capaç de jugar als escacs. L'any 1769, un jugador d'escacs autòmat anomenat El Turc es va fer famós abans que es descobrís que era un engany. L'espanyol Leonardo Torres Quevedo va construir, el 1912, un autòmat capaç de jugar als escacs, anomenat El Ajedrecista. Després d'aquells fets, el tema dels escacs mecànics no es va tornar a esmentar i va caure en l'oblit, fins a l'aparició de l'ordinador en la dècada dels anys 50. Des de llavors, els fanàtics dels escacs i de l'enginyeria informàtica han construït màquines i programes que juguen als escacs.

GNU Chess 5.07 a interface WinBoard 4.2.7

Actualment, els ordinadors d'escacs estan disponibles per un preu insignificant, i hi ha nombrosos programes (molts de programari lliure, com GNU Chess, Amy, o Crafty) que poden jugar als escacs a qualsevol ordinador personal i derrotar jugadors professionals sota condicions de torneig, mentre que alguns d'entre els millors programes comercials d'escacs, com Shredder, Fritz, Rybka o Fruit, han vençut molts jugadors de qualitat i diversos campions del món en temps de control molt curts i partides llampec.

Origen

Hi ha diverses causes que van motivar l'existència dels escacs computacionals, com l'entreteniment propi (permetent que els jugadors practiquin i es diverteixin quan no hi ha cap oponent disponible), també com a eina o suport d'anàlisi, per a competicions entre ordinadors d'escacs, i com a investigació o proveïment del coneixement humà. Els dos primers objectius han estat assolits satisfactòriament, sent tot un èxit, sobretot si es torna la vista enrere, quan els primers intents de programar un ordinador capaç de desafiar als grans jugadors d'escacs daten de fa només menys de cinquanta anys. Podríem dir que els escacs no són un gran problema per a la computació contemporània.

No obstant això, i malgrat la sorpresa de molts, els escacs ens han ensenyat molt poc pel que fa a la construcció de màquines que proporcionen intel·ligència humana, o fer qualsevol altra cosa que no sigui jugar prodigiosament als escacs. Per aquesta raó, els escacs computats, així com molts altres jocs, com el Scrabble, no tenen un gran interès acadèmic per als experts de la intel·ligència artificial, sent aquest reemplaçat per jocs més intuïtius, com el Go. El funcionament dels programes d'escacs consisteix, essencialment, a explorar un nombre molt elevat de possibles futurs moviments i aplicar una funció d'avaluació al resultat, mentre que els ordinadors de Go desafien els programadors a idear nous enfocaments i estratègies de joc.

Les tàctiques basades en la força bruta són pràcticament inútils per a la majoria de problemes que han afrontat els investigadors de la IA. L'estil de joc d'un programa d'escacs es diferencia en gran manera de l'estil de joc humà, ja que l'elecció del moviment a jugar és totalment diferent. En alguns jocs d'estratègia, els ordinadors solen vèncer fàcilment la gran majoria de partides, mentre que en d'altres, els principiants vencen les màquines sense major esforç. En els escacs, el resultat de la fusió de les habilitats dels experts, amb els programes d'escacs, és major que el de qualsevol dels dos a soles.

Estratègia contra força bruta

El primer article sobre el tema va ser escrit per Claude Shannon, i publicat el 1950, abans de l'existència d'un ordinador que jugués als escacs, i va predir encertadament les dues possibles principals formes de recerca de qualsevol programa, a les quals va nomenar de 'Tipus A', i de 'Tipus B'.

Els programes 'Tipus A', més rudimentaris, utilitzarien una recerca basada en la "força bruta", els quals examinarien totes possibles posicions de cada branca de l'arbre de moviments utilitzant l'algorisme minimax. Shannon va creure que això seria molt poc pràctic per dues raons:

• Primer, amb aproximadament 30 moviments possibles en una posició típica de mig joc, Shannon va predir que trobar les 30⁶ (més de 700.000.000) posicions contingudes en els primers tres moviments (d'ambdós bàndols, és a dir, 6 pliés), trigaria aproximadament 16 minuts, fins i tot en el cas "molt optimista" que el programa avalués un milió de posicions per segon. Després d'aquesta conjectura, es va trigar al voltant de 40 anys per aconseguir aquesta velocitat.
• Segon, s'ignorava el problema de la latència, ja que el programa tracta d'avaluar la posició resultant després de tot l'intercanvi de peces passat durant tots aquests moviments al final de cada branca de l'arbre. Els programes de 'Tipus A' funcionen així, però l'inconvenient és que s'incrementa enormement el nombre de posicions necessàries per a l'anàlisi, i d'aquesta manera el programa es alentia encara més.

En comptes d'aquest gastar la potència de procés examinant moviments dolents o trivials, Shannon va suggerir que els programes tipus B farien servir una mena de "intel·ligència artificial estratègica" per solucionar aquests problemes en els quals s'analitzarien només les millors jugades de cada posició, una cosa semblant al que fan els jugadors humans. Això permetria el programa d'analitzar les línies significants de manera més profunda en un temps raonable.

Adriaan de Groot va entrevistar diversos jugadors d'escacs de diversos nivells i la seva conclusió va ser que tant els Grans Mestres com a novells calculen aproximadament quaranta o cinquanta posicions abans de decidir quina jugada fer. El que realment diferencia jugadors experts de jugadors mediocres és l'habilitat del reconeixement de patrons, que es va adquirint amb l'experiència. Això permet analitzar més profundament les millors línies i no perdre el temps amb altres de pitjors. Una prova d'això és que els jugadors d'escacs recorden moltes de les posicions jugades en anteriors partides i aprenen de l'experiència, però les computadores no ho tenen tan fàcil.

El problema dels programes 'Tipus B' és que es confia massa en que el programa pot decidir quins moviments són prou bons per ser dignes de consideració en qualsevol posició, sent un problema molt més greu que en programes 'Tipus A' amb un maquinari de gran velocitat.

Un dels grans defensors de les computadores d'escacs entre els Grans Mestres va ser el Campió del món d'escacs Mikhaïl Botvínnik, que va escriure diversos treballs en la matèria. També tenia un doctorat en Enginyeria Elèctrica. El treballar amb maquinari relativament primitiu a l'URSS a principis dels anys 1960, Botvínnik no va tenir l'oportunitat d'investigar les tècniques de programari de selecció de moviments, en aquest moment els ordinadors més potents podien aconseguir tres pliés per recerca i Botvínnik no tenia aquestes màquines. El 1965 Botvínnik va ser conseller a l'equip ITEP en el matx d'ordinadors EUA-URSS.

El 1973, la Universitat de Northwestern, encarregada de la creació de programes de tipus B, va deixar de programar, passant al bàndol dels programes de Tipus A. Va ser la creadora d'una diversos programes d'escacs que van guanyar els primers tres torneigs ACM Computer Chess Championships (1970-1972). El programa de Tipus A resultant va ser "Chess 4.0", guanyador del torneig ACM durant 5 anys seguits, a més d'inaugurar un dels campionats més importants, el World Computer Chess Championship (WCCC).

Una de les raons per les quals van realitzar el canvi va ser perquè trobaven als programes de tipus B poc estimulants durant els torneigs, ja que és molt difícil predir el que van a moure, i molt menys el perquè. Una altra raó va ser que en els programes de Tipus A era molt més fàcil detectar els error del programa i depurat, i van aconseguir fer-ne un programa prou ràpid: en el temps que solien prendre per decidir els moviments que eren dignes de ser buscats, era possible únicament cercar tots ells.

De fet, Chess 4.0 establir un paradigma que era i continua utilitzant-se en tots els programes d'escacs actuals. Els programes tipus Chess 4.0 guanyaven per la simple raó que els seus programes simplement jugaven millor a escacs. Aquests programes no intentaven imitar els processos de pensament humans, però confiaven completament en recerques alfa-beta i negascout. Molts d'aquests programes (incloent-hi tots els programes actuals) també inclouen una part selectiva bastant limitada de la cerca basada en cerques latents i normalment extensions i podat (particularment podat de moviments nuls des dels anys 1990) que eren llançades basades en certes condicions en un intent d'eliminar o reduir els moviments dolents obvis (històrics de moviments) o investigar nodes interessants (per exemple, comprovació d'extensions, peons passats en la setena fila, etc.). No obstant això, els llançament d'extensió i poda s'han d'utilitzar amb molta cura. Si se sobrextiende el programa gasten massa temps analitzant posicions sense interès. Si es poda massa, hi ha riscos de tallar nodes interessants. Els programes d'escacs difereixen en termes de com i quins tipus de regles de poda i extensió s'utilitzen així com de la funció d'avaluació. Es creu que alguns programes són més selectius que altres (per exemple Deep Blue se sap que és menys selectiu que molts programes comercials perquè podia permetre fer més cerques completes), però tots tenen una base de recerques com a fonament i tots tenen component selectius (recerca-Q, poda/extensions).

Encara que tals addicions vol dir que el programa realment no examinaría cada node dins de la profunditat de cerca (de tal manera que no seria realment força bruta en aquest sentit), els estranys errors deguts a aquestes recerques selectives es troba que consumeixen en temps extra que és estalviat pel fet que es podria augmentar la profunditat. D'aquesta manera els programes d'escacs poden obtenir el millor d'ambdós mons.

A més, el desenvolupament i els avenços tecnològics van fer que el sistema de força bruta continués en alça i s'intensifiqués molt més en els anys 90. El resultat ha estat la creació de programes molt més sòlids, amb una IA tàctica realment sorprenent, programes molt més exactes gairebé sense errors, i conduïts cap al límit de la seva profunditat de cerca. Això ha produït resultats extraordinaris, almenys pel que fa als escacs, deixant que els ordinadors facin allò que millor saben fer, calcular, en lloc d'intentar emular la intel·ligència i coneixement humans. El 1997, Deep Blue, un ordinador de Tipus A, va derrotar el Campió del Món Garri Kaspàrov; fou el primer cop que un ordinador derrotà el campió del món en una partida amb control de temps estàndard de torneig.

No obstant això, a finals dels anys 1990, els programadors van començar a preferir els programes de tipus B, i van començar a substituir els de Tipus A. El 1998 es publica Rebel 10, un programa comercial de tipus B, que va derrotar Viswanathan Anand per 5-3, i es va proclamar el segon motor d'escacs més fort del món aquell any. Val a dir que de les quatre partides d'escacs ràpid (temps de control: 5 min+5 s per jugada) que es van jugar, Rebel va guanyar-ne 3, en les dues partides semiràpides, van quedar 1½-0½ a favor de Rebel, i en la partida amb temps de control més llarg (40/2:00, 1 hora), va ser Anand qui va vèncer. D'això es pot deduir que els ordinadors juguen millor que els humans en temps de control més ràpids, però que la força dels jugadors es mesura amb temps de control més llargs, on Anand va demostrar que els humans segueixen essent millors.

A principis del Segle XXI van sorgir nous programes d'escacs comercials, com ara Deep Junior, o Fritz, que van aconseguir entaular als campions del món Garri Kaspàrov i Vladímir Kràmnik. El 2005, Hydra, un ordinador d'escacs del Tipus B, va derrotar el millor jugador britànic i setè millor classificat del món, Michael Adams, en un matx a sis partides amb un contundent resultat: 5½ - ½ a favor d'Hydra.

Ordinadors contra humans

El 1968, el Mestre Internacional David Levy va fer una famosa aposta, en la qual afirmava que cap ordinador d'escacs seria capaç de derrotar en deu anys, sota condicions de torneig. Va guanyar l'aposta el 1978, vencent per 3,5-1,5 en un matx de cinc partides a l'ordinador més fort en aquell temps, Chess 4.7, i guanyà 1.250 lliures, tot i reconèixer que al cap de poc temps el superarien. El 1989, Levy no va poder superar Deep Thought, que el derrotà en una partida d'exhibició. No obstant això, durant un llarg període en els anys 1970 i els anys 1980 restà la pregunta oberta de si un programa d'escacs podria derrotar el més expert dels humans.

No obstant això, Deep Thought no estava encara a l'altura dels millors escaquistes del món, i el 1989 així ho va demostrar Garri Kaspàrov en dues ocasions, fins que per fi, el 1996, l'ordinador Deep Blue d'IBM va aconseguir que Kaspàrov perdés la seva primera partida contra un ordinador en temps de control de torneig. És més, era la primera vegada que un ordinador derrotava a un campió del món amb ritme de joc lent. No obstant això, després Kaspàrov va aconseguir vèncer tres i empatar-ne dues de les cinc últimes partides, i així aconseguí la victòria sobre l'ordinador per 4-2.

El maig de 1997, una versió millorada de Deep Blue va derrotar Kaspàrov en un matx a 6 partides per 3,5-2,5, i s'originà un gran debat sobre si el jugador més fort en aquella època era una màquina.

Posteriorment es deia que IBM havia fet trampes utilitzant un jugador humà durant el matx per incrementar la força estratègica de l'ordinador. El 2003 es va realitzar un documental centrat en la confrontació, titulat Game Over: Kasparov and the Machine. IBM continua tenint una pàgina web de l'esdeveniment Arxivat 1999-04-29 a Wayback Machine.. Encara que no va ser un campionat del món oficial, el resultat del matx sovint es considera que el jugador més fort del món és un ordinador. Aquesta reivindicació és un gran debat obert, ja que és difícil d'organitzar un veritable matx net home-màquina. Es veu com injust que els jugadors humans hagin de guanyar el seu títol en torneigs que els s'enfronten a un variat conjunt d'estil d'oponent, mentre que les computadores són ocasionalment optimitzades per a l'oponent actual. També, al contrari que el contrincant humà, que els ordinadors tenen accés a grans bases de dades d'obertures) i finals.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Posició Final de la partida 1, Deep Blue vs. Kaspàrov, 1996

IBM va desmantellar Deep Blue després del matx i no ha tornat a jugar des d'aleshores. No obstant això, s'han seguit jugant partides entre humans i ordinadors. Amb l'increment de la potència de processament, els programes d'escacs que s'executen en ordinadors normals comencen a ser rivals per als jugadors més forts del món. El 1998, Rebel 10 derrotà Viswanathan Anand, que en aquell moment estava classificat en el segon lloc del món, amb un marcador de 5-3. No obstant això, algunes d'aquestes partides no es van jugar amb controls de temps habituals. De les vuit partides, quatre van ser partides ràpides (cinc minuts més cinc segons de retard Fischer per a cada moviment) que va guanyar Rebel per 3-1. Hi va haver dues partides semi-ràpides (quinze minuts per cada bàndol) que Rebel va guanyar també (1.5-0.5). Finalment es van disputar dues partides lentes (quaranta jugades per dues hores i una hora més a finish) que va guanyar Anand per 0.5-1.5. Almenys a les partides ràpides, sembla que els ordinadors juguen millor que els humans però en controls de temps clàssics, en els quals es determina la classificació d'un jugador, l'avantatge no està tan clar.

A principis dels anys 2000, els programes comercialment disponibles com Júnior i Fritz eren capaços d'entaular partides contra el campió del món Garri Kaspàrov i el campió del món d'escacs clàssic Vladimir Kràmnik:

• L'octubre de 2002, Vladimir Kràmnik es va enfrontar a Deep Fritz, en una trobada de vuit partides en Bahrain, que va finalitzar amb empat. Kràmnik va guanyar les partides 2 i 3 amb tàctiques anti-ordinador convencionals (jugant conservador per tenir un avantatge a llarg termini que l'ordinador no és capaç de veure en la seva base de dades). Fritz, però, va fer el mateix a la 5 després d'un greu error de Kràmnik. La sisena partida va ser qualificada pels comentaristes del torneig com a espectacular. Kràmnik, que tenia avantatge en iniciar-se el mig joc, va sacrificar una peça per aconseguir una bona posició tàctica. Aquest tipus de sacrificis són molt arriscats contra ordinadors que són molt forts defensant-se contra aquests tipus d'atacs. En efecte, Fritz va trobar una sòlida defensa l'atac de Kràmnik, deixant-lo en una mala posició. Kràmnik es va rendir, creient que la partida estava perduda. No obstant això, l'anàlisi post-mortem demostrar que Fritz tenia poques possibilitats de forçar una victòria i que Kràmnik efectivament va desaprofitar una posició de taules. Les dues últimes partides van acabar en taules. Donades les circumstàncies, molts comentaristes segueixen donant a Kràmnik com el jugador més fort del matx.
• El gener de 2003, Garri Kaspàrov va jugar contra Júnior, un altre programa d'escacs, a Nova York. El matx va acabar 3-3. El novembre de 2003, Garri Kaspàrov va jugar contra X3D Fritz. El matx va acabar 2-2.

El 2005, Hydra, un ordinador d'escacs dedicat amb maquinari personalitzat i seixanta-quatre processadors, que és capaç de calcular 40 milions de posicions per segon, guanyador del 14è IPCCC a 2005, va guanyar a Michael Adams (setè en les llistes mundials) amb un contundent 5½ x ½. Encara que la preparació d'Adams estava lluny de la de Kràmnik el 2002. Alguns comentaristes creuen que Hydra serà definitivament clarament superior als millors jugadors humans o sinó, ho serà el seu directe successor. La trobada va tenir lloc al centre de conferències de Wembley (Londres).

El novembre-desembre de 2006, el Campió del Món Vladimir Kràmnik va jugar contra Deep Fritz i aquesta vegada va guanyar l'ordinador per 2-4.

El març de 2007, a Nova Jersey, el GM Jaan Ehlvest (2.610) es va enfrontar al mòdul Rybka (3.020 Elo aprox.), finalitzant 2.5 - 5.5 a favor de Rybka.

Taules de finals

Els ordinadors, des dels seus inicis, analitzaven completament les posicions dels finals. Les bases de dades de finals estan generades per avançat usant l'anàlisi retrospectiva, començant amb posicions on el resultat final és conegut (per exemple en posicions on un bàndol ha guanyat per escac i mat), i analitzar quins moviments han conduït a la combinació final de peces. Ken Thompson, més conegut per ser un dels creadors del sistema operatiu UNIX, va ser un dels pioners en aquest tema.

Durant molt temps, els programes d'escacs van tenir greus problemes en jugar els finals, i eren molt febles en aquest tram de la partida, a causa de la necessitat d'una alta profunditat de cerca. Amb diferents programes d'alt nivell van ser incapaços de vèncer en posicions que qualsevol humà de nivell intermedi seria capaç de guanyar.

De vegades, els resultats de les anàlisis de les computadores sorprenen a les persones. El 1977, Belle, la màquina d'escacs de Ken Thompson, usant la taula de finals KQKR, va aconseguir empatar una posició, en teoria perduda, de Rei i Torre contra Rei i Dama, contra diversos jugadors nord-americans professionals.

Molts Grans Mestres refusar jugar contra l'ordinador en els finals de dama contra torre, però Walter Browne va acceptar el desafiament. A la partida es va produir un final de dama contra torre, on la dama podia guanyar en trenta moviments, amb un joc perfecte. Browne disposava de dues hores i mitja per jugar cinquanta moviments. Després de quaranta-cinc moviments, Browne va acceptar les taules, essent incapaç de forçar el mat o guanyar la torre en els següents cinc moviments. En la posició final, Browne estava encara a disset moviments d'aconseguir l'escac mat, però no gaire lluny de capturar la torre. Browne va analitzar el final, i va jugar contra l'ordinador una setmana més tard. Aquesta vegada, va capturar la torre en el moviment cinquanta, finalitzant amb una posició guanyadora.

Els avenços en les taules de finals de Ken Thompson, van produir que a principis dels anys 80, es canviés la regla dels cinquanta moviments, en demostrar que certs finals necessitaven més de cinquanta moviments per poder vèncer, com el final de rei, torre i alfil, contra rei i torre.

Amb el pas del temps s'han anat publicant altres formats de bases de dades de finals, incloent-hi la base de dades Edward , la base de dades De Koning (publicada el 2002) i les Bases de Dades Nalimov, que és el format més utilitzat en l'actualitat, suportat per la majoria dels programes d'escacs com Shredder i Fritz. Gairebé tots els finals de sis o menys de sis peces, i diversos de set peces, han estat analitzats per complet.

Les bases de dades es creen emmagatzemant en la memòria valors de les posicions, i fent servir aquests resultats per podar els finals dels arbres de cerca si sorgissin de nou. Encara que el nombre de possibles partides després que un nombre de moviments augmenti exponencialment amb el nombre de jugades, el nombre de les possibles posicions amb unes poques peces és exponencial només en el nombre de peces - i eficaçment limitat, però algunes jugades dels finals són analitzades. L'haver de recordar el valor de totes les posicions obtingudes amb anterioritat vol dir que el factor limitant per resoldre finals es redueix simplement a la quantitat de memòria disponible a l'ordinador. És per això que mentre les mides de les memòries dels ordinadors continuïn augmentant, no hi ha raó per creure que els finals d'elevada complexitat no continuïn resolent.

Un ordinador que utilitza aquestes bases de dades va, en assolir la posició en elles, si pot jugar perfectament, i immediatament determinar si la posició acaba en victòria, derrota, o taules. El coneixement de si la posició acaba en victòria, derrota, o taules, també és útil per endavant, ja que pot ajudar a l'ordinador a evadir o encaminar-se cap aquestes posicions depenent de la situació.

Les taules de finals van prendre gran importància el 1999, quan Garri Kaspàrov va jugar una partida d'exhibició a Internet contra la Resta del Món, en la qual hi va haver certa polèmica. En aquesta partida van arribar a un final de set peces, dama i peó, quan la Resta del Món intentava aconseguir unes taules. Eugene Nalimov va col·laborar generant al final de sis peces quan tots dos bàndols tenien dues dames, la qual cosa va ajudar en gran manera a l'anàlisi.

Qüestions d'implementació d'ordinadors d'escacs

Els desenvolupadors de sistemes d'ordinadors d'escacs han de decidir diverses qüestions d'implementació fonamentals. Aquestes són:

• Representació del tauler: com es representa una posició simple en estructures de dades.
• Tècniques de recerca: com identificar els possibles moviments i seleccionar els més prometedors per examinar-los posteriorment.
• Avaluació de fulles: com avaluar el valor d'una posició del tauler, si no es fa una recerca posterior.

Els programadors també necessiten decidir si faran servir bases de dades de finals o altres optimitzacions i sovint implementar estàndards d'escacs comuns de facto .

Representació del tauler

Article principal: Representació del tauler (Escacs)

L'estructura de dades utilitzada per representar cada posició d'escacs és clau per al rendiment de la generació de moviments i l'avaluació de posicions. Els mètodes inclouen l'emmagatzematge de les peces en una matriu, les posicions de les peces en una llista ("llista de peces"), col·leccions de conjunts de Birsen per a la localització de peces i posicions codificades amb codificació Huffman per a compactar l'emmagatzematge a llarg termini.

Tècniques de recerca

Els programes d'ordinador d'escacs consideren els moviments com un arbre de joc. En teoria, examinen tots els moviments i llavors tots els contramovimientos a aquests i després tots els seus respectius contramovimientos, i així successivament, on cada moviment individual es diu "cadena" o "ply". Aquesta avaluació continua fins que arriba a una "full" final que és avaluada.

No obstant això, una implementació simplista d'aquesta tècnica mai no acabaria en una quantitat de temps pràctica, a conseqüència d'això s'han ideat diversos mètodes per augmentar la velocitat de cerca per bons moviments.

Per a més informació, vegeu:

• Algorisme minimax
• Podat alfa-beta
• Heurística assassina
• IDDFS
• Heurística de moviment nul
• Reduccions de moviment tardà

Avaluació de fulles

Per a moltes posicions d'escacs, els ordinadors no poden considerar totes les possibles posicions. En comptes d'això, han de seguir unes quantes brins i llavors avaluar la posició final al tauler. L'algorisme que avalua les posicions finals es denomina la "funció d'avaluació" i aquests algorismes sovint són molt diferents entre els diferents programes d'escacs.

Les funcions d'avaluació típicament avaluen posicions en centèsimes de peó i consideren el valor del material juntament amb altres factors que afecten la força de cada bàndol. Quan hi ha el material de tots dos bàndols, els valors típics per a peces són 1 punt per a un peó, 3 punts per als cavalls i els alfills, 5 punts per a les torres i 9 punts per a una dama. Per convenció, una avaluació positiva afavoreix les blanques i una de negativa, les negres.

Al rei de vegades se li dona un valor arbitrari alt, com ara 200 punts (article de Claude Shannon) o 1.000.000 de punts (programa de l'URSS de 1961) per assegurar que un mat sobrepassi sempre la resta de factors. Les funcions d'avaluació tenen en compte molts factors, com l'estructura de peons, la parella d'alfils, la centralització de les peces, etc. També se sol considerar la protecció del rei, així com la fase en què es troba la partida (obertura, Mig joc o final).

Utilitzant bases de dades de finals

Alguns operadors d'ordinadors d'escacs han apuntat que les bases de dades de finals tenen el potencial d'afeblir el rendiment en ordinadors d'escacs si s'utilitzen incorrectament. Com algunes posicions són analitzades com victòries forçades per un bàndol, el programa evitarà les posicions del bàndol perdedor de totes totes. No obstant això, molts finals només són forçats amb un joc molt precís, on fins i tot un lleuger error produiria un resultat diferent. Conseqüentment, moltes màquines modernes jugaran molts finals prou bé per als seus propis interessos.

Un símptoma d'aquest problema és que els ordinadors poden abandonar massa aviat perquè veuen que estan sent forçats en una posició que està perduda teòricament (encara que poden estar a trenta o més moviments del final de la partida ja molts oponents humans els costaria molt guanyar en aquest temps). Aquesta observació només és rellevant quan un programa d'ordinador està en una situació on ha de triar entre dos moviments perdedors, un dels quals de fet és més difícil per l'oponent, però condic a una posició a la base de dades amb un valor conegut i és fins i tot de molta menor importància.

Les bases de dades de Nalimov no consideren la regla dels cinquanta moviments, en què una partida on passi cinquanta moviments sense una captura o sense moure un peó pugui ser reclamada com taules per un jugador. Això dona com a resultat una base de dades que retorna resultats com "Mate forçat de 66 moviments" en algunes posicions que serien taules a causa de la regla dels cinquanta moviments. No obstant això, una màquina correctament programada coneix la regla dels cinquanta moviments i en cap cas utilitzant una base de dades de finals elegiria el moviment que conduiria a la victòria més ràpida (fins i tot si sobrepassés la regla dels cinquanta moviments amb un joc perfecte). Si jugant amb un oponent no es fa servir una base de dades de finals, aquestes eleccions donarien bones oportunitats de victòria dins de la regla dels cinquanta moviments.

Una raó per això és que si les regles dels escacs canviés una altra vegada, donant més temps per guanyar aquestes posicions, no seria necessari regenerar totes les bases de dades. També seria molt fàcil per al programa utilitzar les bases de dades per a notar i tenir en compte aquesta 'característica'.

Les bases de dades de Nalimov, que utilitzen l'estat de l'art de les tècniques de compressió, necessiten 7.05 GB d'espai al disc dur per a tots els finals de cinc peces. Per cobrir tots els finals de sis peces necessita aproximadament 1.2 terabyte. S'estima que les bases de dades de set peces necessitaran més capacitat d'emmagatzematge de la qual estarà disponible en el futur previsible.

És sorprenent, però fàcilment comprovable, que sense una base de dades de finals fins i tot ordinadors d'escacs més forts puguin fallar a l'hora de trobar un pla guanyador fins i tot en finals amb sis o menys peces, quan necessiten més moviments que l'horitzó de càlcul per aconseguir un escac mat, un guany de material o l'avanç d'un peó. Molts finals necessiten més moviments que el seu horitzó de càlcul.

Altres optimitzacions

Moltes altres optimitzacions es poden utilitzar per realitzar programes d'escacs més forts. Per exemple, les taules de transposicions s'utilitzen per gravar posicions que ja han estat avaluades, per evitar recalculables. Les taules de refutació emmagatzemen moviments clau que "refuten" el que sembla un bon moviment, aquestes es van utilitzar per primera vegada en les variants (ja que un moviment que refuta una posició és probable que refute altra). Els llibres d'obertures ajuden els programes d'ordinadors donant les obertures comuns que són considerades bones (i bons camins contra les obertures més pobres).

Per descomptat, amb maquinari de més velocitat i processadors addicionals es pot millorar la capacitat dels programes d'escacs i alguns sistemes (com Deep Blue) utilitzen maquinari especialitzat en escacs en lloc de només implementacions programari.

Estàndards

Els programes d'escacs per a ordinadors normalment suporten diversos estàndards comuns de facto. Gairebé tots els programes actuals poden llegir i escriure moviments d'escacs en el format PGN i pot llegir i escriure posicions individuals en format FEN. Els antics programes d'escacs sovint només comprenen la notació algebraica llarga, però els usuaris actuals esperen que els programes d'escacs comprengui la notació algebraica convencional.

Molts programes d'ordinador d'escacs es divideixen en un «motor» (que calcula el millor moviment de la posició actual) i una interfície d'usuari. Molts motors estan separats de la interfície d'usuari i les dues parts es comuniquen entre si utilitzant un protocol de comunicació públic. El protocol més popular és el protocol Xboard/Winboard Communication. Un altre protocol obert de comunicació d'escacs alternatiu és l'Interfície universal d'escacs. En dividir els programes d'escacs en aquestes dues parts, els desenvolupadors només han de programar la interfície d'usuari o el motor, i no fa menester escriure les dues parts del programa.

Força de joc contra velocitat de procés

S'ha estimat que al doblar la velocitat de computació es guanya aproximadament entre cinquanta i setanta punts de ELO en força de joc.

Tanmateix, això s'aplica principalment a matxs entre ordinadors i no a matxs entre ordinadors i humans, on aquest increment seria bastant menor.

Altres programaris d'escacs

Hi ha nombrosos programaris relacionats amb escacs:

• Visors de partides d'escacs : permeten als jugadors visualitzar una partida transcrita en un ordinador. Molts programes que juguen als escacs també poden ser utilitzats per estre propòsit, però existeixen programes especialitzats.
• Software per a ensenyament d'escacs : són dissenyats especialment per a l'ensenyament dels escacs.
• Bases de dades d'escacs : sistemes que permeten la recerca d'una gran biblioteca de partides històriques. La Shane's Chess Information Database (SCID) és un bon exemple d'una base de dades d'escacs. Scid pot utilitzar-se amb Microsoft Windows, Unix, Linux i Mac OS X. També hi ha bases de dades comercials, com ChessBase i Chess Assistant per a Windows i ExaChess per a Mac OSX.
• Software per gestionar problemes d'escacs

Escacs avançat

Els escacs avançats són una forma d'escacs desenvolupada el 1998 per Kaspàrov on un humà juga contra un altre humà i tots dos tenen accés a ordinadors per augmentar la seva força. El jugador "avançat" resultant argumentava Kaspàrov que seria més fort que un humà o un ordinador en solitari, encara que això no ha estat provat.

Tornejos d'escacs avançat

En els últims anys s'han produït nombrosos torneigs arreu del món d'escacs avançat. Els més importants van ser, sens dubte, el PAL / CSS Freestyle-Tournament, patrocinat pel Grup PAL a Abu Dhabi (Emirats Àrabs Units). Aquests torneigs mundials van tenir lloc al Playchess servidor web (ChessBase) i han tingut un molt alt nivell de joc, potser el més alt mai vist en un joc d'escacs amb el control de temps. Aquests són els guanyadors en ordre cronològic: Zacks (Steven Cramton i Zackary Stephen, EUA), Zorchamp (Hydra, Emirats Àrabs Units), Rajlich (Vasik Rajlich, Hongria), Xakru (Jiri Dufek, República Txeca), Flying Saucers (Daniel Nielsen, Dinamarca), Rajlich (Vasik Rajlich, Hongria), Ibermax (Anson Williams, Anglaterra), Ultima (Eros Riccio, Itàlia).

Tornejos similars també van ser organitzades per FICGS i Infinity Chess.

Amb base en els resultats obtinguts en els torneigs d'escacs avançat, va ser desenvolupat per Infinity Chess una especial classificació Elo per als centaures, que veu el primer lloc Sephiroth (Eros Riccio) amb 2755 punts Elo.

Teòrics de computació en escacs

Els teòrics en computació d'escacs més coneguts són:

• D. F. Beal
• David Levy
• Robert Hyatt (autor del programa de codi obert Crafty)
• Hans Berliner
• Claude Elwood Shannon

El futur dels escacs per ordinador

Un camp d'investigació potencialment fructífer és la computació distribuïda, en què molts ordinadors estan treballant conjuntament a través d'Internet i cada un té la tasca d'una petita secció de l'arbre de cerca al complet per analitzar. El projecte principal és el ChessBrain, que va aconseguir un rècord del món el 2004 amb el major nombre d'ordinadors jugant una partida d'escacs simultàniament (2.070).

Resolució dels escacs

La perspectiva de resoldre completament els escacs és considerada de manera remota. Hi ha una conjectura àmpliament acceptada que no hi ha un mètode computacionalment permissible per resoldre els escacs en sentit feble i així, la idea de resoldre els escacs en sentit fort d'obtenir una descripció pràcticament utilitzable d'una estratègia per a un joc perfecte per a tots dos bàndols no sembla realista avui en dia. No obstant això, s'hauria de considerar que no s'ha provat que hi hagi un camí computacionalment assequible de determinar el millor moviment en una posició d'escacs, ni s'ha provat matemàticament que un algorisme tradicional alfa-beta amb el maquinari actual pugui resoldre la posició inicial en una quantitat de temps acceptable. La dificultat de provar això rau en el fet que, mentre el nombre de posicions en el tauler que poden ocórrer en el curs d'una partida d'escacs és alt (de l'ordre de 10⁴⁰), és difícil d'establir les regles amb rigorositat matemàtica per dir que la posició inicial permeti a un bàndol forçar un mat o una triple repetició després d'uns quants moviments, l'arbre de recerca només podrà incloure un petit subconjunt dins de tot el conjunt de posicions possibles. De fet, es pot dir precisament que no hi ha res que indica una possibilitat pràctica de resolució d'escacs en el present en qualsevol sentit de la paraula.

Cronologia de les computadores d'escacs

Any	Esdeveniment
1769	Wolfgang von Kempele construeix El Turc, que es converteix en un dels majors enganys d'aquest període
1868	Charles Hooper va presentar l'autòmat Ajeeb, que també tenia un jugador humà amagat a l'interior.
1912	Leonardo Torres Quevedo construeix una màquina que jugava finals de rei i torre contra rei
1948	El llibre de Norbert Wiener Cybernetics descriu com es podria desenvolupar un programa d'escacs utilitzant una recerca de profunditat limitada minimax amb una funció de funció d'avaluació.
1950	Claude Shannon publica "Programació d'una Computadora per Jugar a Escacs", un dels primers articles sobre el problema de l'ordinador d'escacs.
1951	Alan Turing desenvolupa en paper el primer programa capaç de jugar una partida completa d'escacs.
1952	Dietrich Prinz desenvolupà un programa que resolia problemes d'escacs.
1956	Escacs Los Alamos és el primer en jugar a una cosa semblant als escacs, desenvolupat per Paul Stein i Mark Wells per l'ordinador MANIAC I.
1956	John McCarthy inventa l'algorisme de cerca alfa-beta.
1958	NSS es converteix en el primer programa d'escacs en utilitzar l'algorisme de cerca alfa-beta.
1958	Es van desenvolupar els primers programes que podien jugar una partida completa d'escacs, un per part d'Alex Bernstein i un altre per part de programadors russos utilitzant un Besmir.
1962	Apareix el primer programa que juga acceptablement, el Kotok-McCarthy (Alan Kotok i John McCarthy) publicat en el MIT.
1966-1967	Es juga el primer matx entre programes d'ordinadors. L'Institut de Física Teòrica i Experimental (ITEP) de Moscou va derrotar el Kotok-McCarthy a la Universitat de Stanford per telègraf després de nou mesos de joc.
1967	El programa MacHack de Richard Greenblatt i altres introdueix taules de transposició i es converteix en el primer en derrotar una persona en torneig.
1970	Primera edició del Campionat de computadors d'Escacs d'Amèrica del Nord (ACM).
1974	Kaissa guanya el primer Campionat del món de computadors d'escacs.
1977	Es crea la primera màquina microordinadors que juga als escacs: CHESS CHALLENGER.
1977	Creació de l'Associació Internacional de computadors d'escacs.
1977	Chess 4.6 es converteix en el primer ordinador d'escacs en aconseguir un èxit en un gran torneig d'escacs.
1980	Primera edició del Campionat del món de microordinadors d'escacs
1980	Creació del Premi Fredkin.
1981	Cray Blitz guanya el Campionat Estatal de Mississipi amb un marcador perfecte de 5-0 i una actuació de 2.258 punts Elo. A la ronda 4 derrota Joe Sentef (2262) convertint-se en el primer ordinador en guanyar un mestre en un torneig i en el primer ordinador a aconseguir la qualificació de mestre.
1982	El maquinari d'escacs de Ken Thompson, Belle, va aconseguir el títol de Mestre dels EUA.
1988	HiTech desenvolupada per Hans Berliner i Carl Ebeling guanya un matx contra el Gran Mestre Arnold Denker per 3½ - 0½.
1988	Deep Thought comparteix en primer lloc amb Tony Miles al Campionat d'eines Software, per davant del campió del món d'escacs Mikhaïl Tal i diversos altres Grans Mestres com ara Samuel Reshevsky, Walter Browne, Ernst Gruenfeld i Mikhaïl Gurévitx. També va derrotar el GM Bent Larsen, essent el primer ordinador en guanyar un GM en un torneig. La seva performance Elo en aquest torneig va ser de 2.745, la més alta obtinguda fins a aquell moment per un ordinador.
1989	Deep Thought perd dues partides d'exhibició contra Garri Kaspàrov, el campió del món regnant en aquell moment.
1992	Primera vegada que una microordinadors, la màquina Gideon 3.1 d'Ed Schroeder, guanya el 7è Campionat del Mmón de computadors d'escacs contra mainframes, superordinadors i maquinari especial.
1997	Deep Blue guanya un matx a sis partides contra Garri Kaspàrov (+2 -1 =3) (vegeu chess.ibm.com Arxivat 1999-04-29 a Wayback Machine.).
2002	Vladímir Kràmnik entaula un matx a vuit partides contra Deep Fritz.
2003	Kaspàrov entaula un matx a sis partides contra Deep Junior.
2003	Kaspàrov entaula un matx a quatre partides contra X3D Fritz.
2005	Hydra derrota Michael Adams per un contundent 5½-0½.
2005	Un equip d'ordinadors (Hydra, Deep Junior i Fritz), guanya 8½-3½ contra un fort equip d'humans format per Vesselín Topàlov, Ruslan Ponomariov i Serguei Kariakin, que tenia una mitjana de Elo de 2.681.
2006	Al campionat del món oficiós, Vladímir Kràmnik és derrotat per Deep Fritz 4-2.

Vegeu també

• Nombre de Shannon.
• Bitboard
• Arbre de joc

Bibliografia

• Plantilla:Harvard reference
• Plantilla:Harvard reference
• Plantilla:Harvard reference
• Mestratge del Joc: Una Història dels Escacs per Computador al d'Història de la Computació
• Cronologia de la Història dels Escacs per ordinador de Bill Wall Arxivat 2009-10-28 a Wayback Machine.
• Ludek Pachman. Martinez Roca. Escacs i ordinadors, 1982. ISBN 84-270-0724-8. 

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Escacs per ordinador

• Història dels escacs per ordinador Arxivat 2009-10-25 a Wayback Machine.
• Defensant l'Honor de la Humanitat, un article de Tim Krabbé sobre l'estil d'escacs "anti-ordinadors"
• Club d'Escacs per ordinador - Butlletí en què els professionals discuteixen sobre els seus programes
• La Història dels Escacs per Ordinador: Una Perspectiva d'Intel·ligència Artificial (vídeo de 2 hores)