Gli Scacchi sono il gioco intellettuale per eccellenza. Senza far uso di strumenti casuali (come i dadi o la roulette), che inquinerebbero la contesa, due intelletti vengono contrapposti in una situazione così complessa che nessuno dei due può sperare di comprenderla completamente, e tuttavia il gioco è sufficientemente analizzabile, di modo che ciascuno dei due può sperare di sconfiggere l’altro.

Il gioco è tanto profondo e sottile che ha permesso la nascita di giocatori professionisti, ed ha sopportato senza esaurirsi oltre 200 anni di partite e di studi analitici intensivi. Tali caratteristiche rendono gli Scacchi un’arena naturale per i tentativi di meccanizzazione.
Se si potesse sviluppare un giocatore artificiale vincente, si potrebbe affermare di aver penetrato il nucleo dell’attività intellettuale umana.

Allen Newell, Cliff Shaw and Herbert Simon, 1958

Vi siete mai chiesti come cazzo fa Chessmaster a farvi sempre il culo a padella a scacchi? Cosa si nasconde dietro i software scacchistici che battono anche i migliori campioni al mondo? Sono davvero intelligenti o è solo una questione di potenza hardware?

Cercherò di rispondere a queste e altre domande che la vostra fervida immaginazione nerd riuscirà a partorire in una serie di articoli dedicati a scacchi e informatica.

Giochi di guerra


Nel 1944 il matematico statunitense John von Neumann, insieme all’economista Oskar Morgenstern, pubblicò un libro intitolato Theory of Games and Economic Behavior. Il tentativo di questi due geni del male fu quello di descrivere matematicamente il comportamento umano nei casi in cui l’interazione fra le parti comporta la vittoria e la sconfitta, o la spartizione di qualche tipo di risorsa. Questo evento può essere considerato la nascita della moderna teoria dei giochi, che vengono studiati in quanto rappresentano la più basilare forma di competizione che l’uomo conosce.

Per gli esseri umani in teoria, e per Dio in pratica (la bravura di Dio nel gioco è stata compromessa dall’ex campione del mondo Wilhelm Steinitz che affermò più volte di aver battuto Dio concedendogli un pedone e una mossa di vantaggio), il gioco degli scacchi si riduce all’albero, gigantesco ma finito, che comprende tutte le possibili mosse di tutte le possibili partite.

Il primo livello consiste delle 20 possibili aperture del bianco; il secondo livello delle 20 possibili aperture del nero in risposta a ciascuna apertura del bianco, cioè dei 400 possibili scambi di apertura; ogni livello successivo si ottiene dal precedente, aggiungendo a ciascun nodo tutte le possibili risposte dell’avversario. Per queste considerazioni, ciascun ramo dell’albero è finito, e descrive una partita che finisce o in una vittoria del bianco, o in una vittoria del nero, o in una patta.

Il ruolo dei giochi nell’IA


I primi studi informatici nel campo dei giochi si sono concentrati su particolari classi: giochi con due avversari che alternano le proprie azioni, in cui l’ambiente è deterministico e completamente osservabile da entrambi, detto quindi ad informazione perfetta. Alcuni di questi giochi sono anche a somma zero, cioè la somma dei risultati ottenuti da entrambi i contendenti in funzione delle strategie utilizzate è sempre nulla. Negli scacchi, ad esempio, questo significa che i soli tre risultati possibili (rappresentando la vittoria con 1, la sconfitta con -1 e il pareggio con 0) possono essere: (1,-1) se vince il Bianco; (-1,1) se vince il Nero; (0,0) se pareggiano. Non esiste il caso in cui vincono entrambi o perdono entrambi.

Sono esclusi da questa categoria i giochi solitari, come il Gioco del 15 e il Cubo di Rubik, i giochi che prevedono chance (Backgammon) o incertezze (Bridge), informazioni imperfette (Stratego) o negoziazioni (Monopoli).

Un primo passo per affrontare il problema dei giochi, è quello di classificarli in base alla loro complessità. È sufficiente definire uno spazio cartesiano in cui sull’ordinata viene rappresentato lo spazio degli stati (l’insieme di tutti gli stati raggiungibili a partire da quello iniziale) e sull’ascissa la complessità dell’albero di gioco.

Mostra Approfondimento ▼

È chiaro che i giochi nella categoria 1 sono molto facili da risolvere; nelle categorie 2 e 3 ci sono giochi risolvibili con differenti metodi a seconda del caso, mentre nella categoria 4 ci sono giochi non risolvibili nella pratica. La ricerca ovviamente si concentra nei giochi di categoria 2 e 3. La risoluzione dei problemi di categoria 2 dipende quasi totalmente dall’incremento della potenza dei computer, mentre la risoluzione dei giochi della categoria 3 dipende dallo sviluppo di nuove tecniche di intelligenza artificiale.

Una questione di numeri


Come ho accennato prima, le possibili aperture sono 20 per ciascun giocatore. 2 mosse per ciascuno degli 8 pedoni, 2 per ogniuno dei 2 cavalli. Le mosse successive sono generalmente di più, perché alcuni pezzi non saranno più occlusi, ma anche limitandosi a 20, dopo sole 10 mosse da entrambe le parti si arriva all’astronomica cifra di

400^{10} = 169\,518\,829\,100\,544\,000\,000\,000\approx10^{23}

Il numero massimo di mosse, quando tutti i pezzi sono ancora sulla scacchiera, si ottiene sommando il numero massimo di mosse per ciascun pezzo (cio 8 per il re, 27 per la donna, 14 per la torre, 13 per l’alfiere, 8 per il cavallo, e 2 per il pedone) per il numero di pezzi:

8 + 27 + (14\times2) + (13\times2) + (8\times2) + (2\times8) = 121

Analogamente, il numero medio di mosse si ottiene quando tutti i pezzi sono ancora sulla scacchiera, sommando il numero medio di mosse per ciascun pezzo (cio 6,5 per il re, 22,5 per la donna, 14 per la torre, 8,5 per l’alfiere, 5 per il cavallo, e 1 per il pedone) per il numero di pezzi:

7 + 22,5 + (14\times2) + (8,5\times2) + (5\times2) + (1\times8) = 92,5.

Nella pratica il numero risulteràˆ inferiore, a causa della mancanza di alcuni pezzi o all’occlusione di altri, e una valutazione empirica del numero medio di mosse disponibili durante una partita standard è circa 40.

Un limite assoluto al numero di configurazioni che si possono ottenere sulla scacchiera è ovviamente dato dal numero di possibili disposizioni dei 32 pezzi sulle 64 case della scacchiera, cioè

64^{32}\approx10^{57}

Esso pone un limite alla lunghezza delle possibili partite, perchéŽ quando due configurazioni si ripetono esattamente, ciò˜ che è successo nel frattempo non ha più importanza. Il numero delle possibili partite è dunque limitato da

121^{{10}^{57}}\approx10^{{10}^{58}}

Il primo a stimare il numero di partite possibili fu Claude Shannon, che valut˜ò una cifra di 10^{120} partite, che è un numero addirittura maggiore di 1 googol (il numero intero esprimibile con 1 seguito da 100 zeri, pari cioè a 10^{100} o 10\,000 decaexilioni).

Anche considerando solo partite più ragionevoli, di 100 mosse e con una media di 40 mosse possibili ogni volta, si ottiene comunque ancora un limite di

100^{40}=10^{80}

pari circa al numero di particelle subatomiche dell’universo visibile, stimato tra 10^{72} e 10^{87}. Ora capirete facilmente come mai con la moderna tecnologia, e probabilmente anche con quella futura, non è possibile risolvere completamente il gioco degli scacchi.

Le valutazioni dei pezzi


Come vedremo più dettagliatamente negli articoli successivi, per affrontare dal punto di vista informatico gli scacchi è necessario analizzare matematicamente le strategie utilizzate dai giocatori reali.

Il primo problema che si affronta è quello di determinare quantitativamente il valore relativo di un pezzo. Questo può essere calcolato valutando la probabilità che, posizionato un pezzo ed il re a caso sulla scacchiera, il primo dia scacco al secondo. Il re può stare in una qualsiasi delle 63 case non occupate dal pezzo in questione e la probabilità è quindi di 1/63. Bisogna valutare il numero medio di case che il pezzo può minacciare e dividerlo quindi per 63.

Il re, in base alle regole del gioco, non può dare scacco e non può essere mangiato e dunque il metodo precedentemente esposto non ha senso in questo caso; si possono comunque calcolare le case minacciate in media dal re a seconda della sua posizione:

- 3 per le 4 case agli angoli della scacchiera;
- 5 per le rimanenti case del bordo;
- 8 per le rimanenti 36 case.

Il risultato è

\frac{(3\times4)+(5\times24)+(8\times36)}{64}=\frac{105}{16}\approx6.5

La donna, impropriamente chiamata regina come traduzione del termine inglese queen, minaccia le case che stanno sulla stessa traversa e sulla stessa colonna, che sono sempre 14, e le case che stanno sulle diagonali che passano per ciascuna delle 64 case in cui essa si può trovare. Queste ultime dipendono dalla sua posizione sulla scacchiera, e sono:

- 7 per le 28 case sul bordo;
- 9 per le 20 case sul secondo bordo;
- 11 per le 12 case sul terzo bordo;
- 13 per le 4 case sul quadrato centrale.

Il valore della donna è dunque

\frac{14}{63}\cdot\frac{(28\times7)+(20\times9)+(12\times11)+(4\times13)}{64\times63}=\frac{2}{9}+\frac{5}{36}=\frac{13}{36}\approx\frac{1}{3}

La torre minaccia le stesse case in orizzontale e verticale che minaccia la donna, ed il suo valore relativo è dunque 14/63, cioè 2/9. In particolare, poichè

\frac{2}{9}+\frac{2}{9}=\frac{4}{9}=\frac{16}{36}>\frac{13}{36}

due torri valgono più di una donna.

L’alfiere minaccia le stesse case in diagonale che minaccia la donna, ed il suo valore relativo è

\frac{5}{36}\approx\frac{1}{7}

In particolare, poiché

\frac{5}{36}+\frac{5}{36}=\frac{10}{36}<\frac{13}{36}

due alfieri valgono meno di una donna.

Il cavallo minaccia le case che si trovano ad L rispetto a quella in cui esso si può trovare. Le L possibili a partire da una casa dipendono dalla posizione di questa sulla scacchiera, e sono:

- 2 per le 4 case agli angoli della scacchiera;
- 3 per le 8 case sul bordo ai lati degli angoli;
- 4 per le rimanenti 16 case sul bordo, o le 4 case agli angoli del secondo bordo;
- 6 per le rimanenti 16 case sul secondo bordo;
- 8 per le 16 case centrali.

Il valore del cavallo è

\frac{(4\times2)+(8\times3)+(20\times4)+(16\times6)+(16\times8)}{64\times63}=\frac{1}{12}

Ora direte voi, esticazzi? Che ce ne facciamo di questi valori? Bene, riducendo al comune denominatore 36, otteniamo un prima, grezza valutazione dei pezzi:
Re: + \infty
Donna: 13
Torre: 8
Alfiere: 5
Cavallo: 3
dai quali si possono trarre interessanti relazioni sul valore dei pezzi.

Mostra Approfondimento ▼

Il disclaimer verso i pro-player scacchisti è che ovviamente questa è una prima, grezza, brutale valutazione dei pezzi, la quale andrà raffinata con moltissimi dettagli aggiuntivi. Lo vedremo nei prossimi articoli.

Il Turco


Per poter capire appieno il funzionamento di un giocatore artificiale moderno, è necessario capire come si sono evolute nel tempo le tecnologie. Accendiamo dunque il flusso canalizzatore e viaggiamo indietro nel tempo fino al 1769, anno in cui un ingegnoso nobile ungherese di Presburg, Wolfgang von Kempelen, costruì una macchina in grado di giocare a scacchi per Maria Teresa d’Austria. Come già accennato questo articolo, esso raffigurava un uomo avvolto in abiti orientali, seduto dietro una specie di scrivania chiusa sul davanti da tre sportelli, con due cassetti in fondo; in realtà l’automa era una truffa molto ben congegnata: era azionato nell’interno da un uomo di piccola statura, che manovrava il braccio mobile del Turco.

I veri studi in materia dovranno invece aspettare la metà dell’Ottocento per vedere la luce e il Novecento per avere un sostanziale sviluppo.

Analytical Engine


Saltiamo avanti con la nostra macchina del tempo fino ai primi anni dell’800. La storia dei giocatori artificiali e dei loro inventori inizia proprio in questo periodo con gli studi del matematico inglese Charles Babbage, da molti considerato il primo informatico della storia.

Dopo aver progettato (sebbene mai costruito) la cosiddetta Macchina Analitica, cominciò a pensare ad alcune applicazioni risolvibili dalla sua macchina. Le sue attenzioni si concentrarono subito sulle strategie dei giochi. In un articolo scritto nel 1864 Babbage sosteneva che qualsiasi gioco di scacchiera può essere affrontato con successo da un automa.

Dopo molti studi, ho scelto l’esperimento di costruire una macchina che dovrebbe poter giocare con successo una partita di un gioco di abilità puramente intellettuale, come ad esempio il filetto, la dama, o gli scacchi… L’automa “esamina” una posizione, e poi comincia a porsi una serie di domande:

1. L’ultima mossa fatta dal mio avversario è legale? Se no, protesto.

2. Ho una posizione indifendibile (ovvero, il matto è inevitabile)? Se sì, abbandono.

3. Tra quelle possibili, c’è una mossa che mi dà la vittoria (cioè posso dare scacco matto)? Se sì, la dichiaro.

4. L’avversario sta per fare una mossa vincente? Se sì, la prevengo.

5. Se alla prossima mossa non c’è una mossa vincente per uno di noi due, debbo cercare una mossa che crea una doppia minaccia, in modo che il mio avversario ne possa parare una sola; se c’è, la effettuo.

6. Se i primi 5 test falliscono, esamino le mosse successive e in qualche modo ne scelgo una; la effettuo senz’altro.

Questo primordiale algoritmo è un primo passo verso la determinazione dei ragionamenti che portano alla costruzione del primo giocatore artificiale di scacchi. Certamente le regole inventate da Babbage sono tutt’altro che ben definite: la regola numero 6, ad esempio, si conclude con un poco chiaro “e in qualche modo ne scelgo una”.

Con questo siamo arrivata alla conclusione della prima parte della storia, il word count dell’articolo è schizzato a più di 2000 parole e direi che è ora di darci un taglio. Nei prossimo articolo vedremo come è ulteriormente evoluta la tecnologia dei giocatori artificiali, dagli studi di Shannon e prima partita giocata da Alan Turing, fino ai successi odierni di Deep Blue prima e Fritz poi.

Stay tuned!

[How machines play chess] è una rubrica tenuta da @ryanvespucci sul funzionamento dei giocatori artificiali di scacchi.

Boardgames, Matematica
, allen newell, , , cliff shaw, herbert simon, , informazione perfetta, , , , , , somma zero, spazio degli stati, turco
Loggati 62
  1. Avatar di occhibordeaux

    occhibordeaux 6:09 am on ottobre 18, 2011 | 392778

    Bellissimo articolo! :fav:
    A proposito (in realtà non c’entra molto), perché non organizzare un bel torneo tra nerd?

    • Avatar di Ryan Vespucci

      Ryan Vespucci 10:05 am on ottobre 18, 2011 | 392803

      Non sarebbe niente male, ma in quale occasione?
      Io, in realtà, non sono un giocatore molto forse, sono solo appassionato :sad:

      • Avatar di Il Cavaliere di Berzelius | Nè

        Il Cavaliere di Berzelius | Nè 11:12 am on ottobre 18, 2011 | 392818

        Io ci sono, il problema però è che se si fa per corrispondenza tutti useranno Fritz di nascosto… :rofl:
        C’era un sito chiamato playok che permetteva di giocare una partita live, con la cosa che se cambi finestra se ne accorge e lo segnala all’avversario, però io preferisco giocare dal vivo…XD

        • Avatar di dofoo

          dofoo 3:13 pm on ottobre 18, 2011 | 392946

          oppure si potrebbe fare un torneo LN vs rest of the world su gameknot

          • Avatar di sabas

            sabas 3:14 pm on ottobre 18, 2011 | 392948

            Ci sto, avviso che pero’ prendo gli scacchi come un fps :D :rofl:

            • Avatar di dofoo

              dofoo 3:22 pm on ottobre 18, 2011 | 392952

              ah beh io sono un appassionato caprone (non conosco la teoria, a parte una minimerrima base). Ma giocare mi piace parecchio. Se non la prendiamo troppo competitiva io ci sono :)

              • Avatar di William J.

                William J. 3:24 pm on ottobre 18, 2011 | 392954

                Anche a me piacerebbe.
                Sul sito Scacchisti.it è tutto già pronto, basta iscriversi e giocare, in più tutti possono guardare la partita.

              • Avatar di dofoo

                dofoo 4:37 pm on ottobre 18, 2011 | 392978

                @William J. ok, anche se ho l’impressione di essere quello che abbassa drasticamente la media (nerd avvisato mezzo salvato :) )
                come si fa? chi organizza? chi c’è?

              • Avatar di William J.

                William J. 4:49 pm on ottobre 18, 2011 | 392983

                Io non ce la faccio ad organizzare, ma un paio di partitelle le faccio volentieri.

                A proposito: se volete citarmi dovete scrivere @WebDtaBank (William è un altro utente che riceve sempre notifiche alla cazzo). ;)

              • Avatar di sabas

                sabas 4:55 pm on ottobre 18, 2011 | 392984

                Non sarà l’ora di fare come @giumini? digievolviti in @williamj :rofl:

              • Avatar di William J.

                William J. 5:00 pm on ottobre 18, 2011 | 392985

                Prego? :o

              • Avatar di sabas

                sabas 5:02 pm on ottobre 18, 2011 | 392986

                in sostanza fatti cambiare il login da itomi :D

              • Avatar di William J.

                William J. 5:10 pm on ottobre 18, 2011 | 392988

                Ahhh, scusa, non ti seguivo. :rofl:
                Boh, non so. Magari un domani vorrò tornare WebDataBank. Sono molto lunatico. :D

              • Avatar di occhibordeaux

                occhibordeaux 11:54 am on ottobre 19, 2011 | 393151

                Vedrò d’informarmi e chiedere i permessi per lanciare il torneo. :ln:

                Sono un nabbo anche io, ma mi diverto parecchio giocando.

                In ogni caso, se ne può parlare alla cena! :D

              • Avatar di dofoo

                dofoo 11:59 am on ottobre 19, 2011 | 393155

                ottimo!

        • Avatar di Ryan Vespucci

          Ryan Vespucci 12:08 am on ottobre 19, 2011 | 393103

          Secondo me sarebbe più figo organizzare dal vivo…

  2. Avatar di frodo

    frodo 6:37 am on ottobre 18, 2011 | 392779

    Bello. Detto da uno che ha provato a programmare cincionare un suo motore scacchistico, dovrebbe essere un complimento. Oppure no? Insomma, oltre alla matematica, ai fumetti e ai pirati del puzzle )non sapete cosa è Puzzle Pirates?!?(, nella mia vita c’è tempo per un pò di scacchi (preferisco la problemistica, però!) :nt:

    • Avatar di Ryan Vespucci

      Ryan Vespucci 9:49 am on ottobre 18, 2011 | 392801

      Grande! in che linguaggio hai provato? com’è andata?

  3. Avatar di insane78

    insane78 8:02 am on ottobre 18, 2011 | 392787

    +1 interessantissimo!!!

  4. avatar

    Cronos89 8:43 am on ottobre 18, 2011 | 392790

    +1 +1

    Ci dovrei dare un esame su una roba del genere.

    • Avatar di Ryan Vespucci

      Ryan Vespucci 9:51 am on ottobre 18, 2011 | 392802

      Io ci ho scritto la tesi! :D

  5. Avatar di sabas

    sabas 9:03 am on ottobre 18, 2011 | 392793

    Certo che sti articoli alle 4 del mattino :rofl:
    Fantastico, ho sempre voluto sapere come cazoz funzionassero gli scacchi sul pc :fav:

    • Avatar di Ryan Vespucci

      Ryan Vespucci 9:48 am on ottobre 18, 2011 | 392800

      I nerd, si sa, lavorano di notte, come i supereroi :D

  6. Avatar di lena

    lena 9:09 am on ottobre 18, 2011 | 392794

    Molto interessante! :fav:

    Aspetto di leggere il prossimo articolo :)

  7. avatar

    psyco-simo 9:14 am on ottobre 18, 2011 | 392795

    Interessantissimo, instant :fav: !

  8. Avatar di fra9001 | Nè

    fra9001 | Nè 10:20 am on ottobre 18, 2011 | 392804

    :fav: anche se anche una calcolatrice tascabile mi batte a scacchi

  9. Avatar di lucrezia

    lucrezia 10:38 am on ottobre 18, 2011 | 392806

    Interessante questo articolo!! Sono un’appassionata di scacchi e ahimè cononsco molto bene Chessmaster: mi ha battuto non so quante volte però nel lontano 19 Luglio 2010 verso le 2 del mattino sono riuscita a vincere una partita…è stato un momento di gloria!!

  10. Avatar di Roland

    Roland 11:21 am on ottobre 18, 2011 | 392822

    Domanda tecnica: ma l’editor supporta LaTex?

    • Avatar di Ryan Vespucci

      Ryan Vespucci 11:31 am on ottobre 18, 2011 | 392826

      Sì, chiudi il codice tra i tag [ latex ] [/ latex ]. Senza spazi ovviamente :)

      • Avatar di Roland

        Roland 11:41 am on ottobre 18, 2011 | 392833

        Buono a sapersi :)

  11. Avatar di Matita

    Matita 11:35 am on ottobre 18, 2011 | 392830

    :fav: subito e me lo segno da rileggere con piu’ attenzione e piu’ calma.
    Ho sempre avuto la curiosita’ su come funzionassero le IA scacchiste.

  12. Avatar di Scampaforche

    Scampaforche 11:40 am on ottobre 18, 2011 | 392832

    :fav:

    solo un appunto: non so perché tu abbia scelto di mettere il titolo in inglese, ma in ogni caso andrebbe corretto in: “how machines play chess” (al plurale) oppure “how machine plays chess” (al singolare) :gn:

    • Avatar di Ryan Vespucci

      Ryan Vespucci 12:45 pm on ottobre 18, 2011 | 392876

      Lo sapevo che qualcosa non andava! Fuck! L’ho scritto in inglese perché l’ho stampato sulla copertina della mia tesi.. e catzo ora che so che è sbagliato la devo ristampare, lol! :o

  13. Avatar di seashores

    seashores 12:08 pm on ottobre 18, 2011 | 392857

    +1 ci voleva il video di deep blue :D

    • Avatar di Ryan Vespucci

      Ryan Vespucci 12:45 pm on ottobre 18, 2011 | 392878

      Deep Blue arriverà nella prossima puntata! :res:

  14. Avatar di Sam Crow

    Sam Crow 12:33 pm on ottobre 18, 2011 | 392865

    :fav: +1

  15. Avatar di pri2p

    pri2p 1:03 pm on ottobre 18, 2011 | 392889

    :fav:

  16. Avatar di itomi

    itomi 1:28 pm on ottobre 18, 2011 | 392900

    :fav: :fav: :fav: Altro post EPICO, grande @ryanvespucci

    • Avatar di itomi

      itomi 1:29 pm on ottobre 18, 2011 | 392902

      e chiamo :nt: senza ombra di dubbio.

      • Avatar di pri2p

        pri2p 1:48 pm on ottobre 18, 2011 | 392920

        :nt:

      • Avatar di sabas

        sabas 1:51 pm on ottobre 18, 2011 | 392923

        Direi che con 2 :nt: più quella di itomi che vale doppio si raggiunge quota 4, quindi :nt: sia

  17. Avatar di Edran

    Edran 1:32 pm on ottobre 18, 2011 | 392904

    Complimenti per l’articolo. Da scacchista ed appassionato di Ai, non posso che FAVvare tutto ed aspettare la prossima puntata :)

  18. Avatar di Roland

    Roland 1:39 pm on ottobre 18, 2011 | 392911

    Ho un dubbio su quel 64^32 come numero di combinazioni totali.
    Letta cosi è come se tu potessi scegliere tra 64 possibilità in ognuna delle 32 caselle. Non dovrebbero essere disposizioni senza ripetizioni?
    Il re e la regina sono unici, non si possono ripetere…
    Non dovrebbero vedersi come pezzi tutti diversi?

    • Avatar di Ryan Vespucci

      Ryan Vespucci 12:18 am on ottobre 19, 2011 | 393106

      In realtà hai 32 pezzi da disporre in 64 case, quindi forse dovrebbe essere 64! / 32! ? La questione in realtà è più complicata, perché non tutte le configurazioni sono raggiungibili. Ora ho trovato questo: http://en.wikipedia.org/wiki/Chess#Mathematics_and_computers

      The number of legal positions in chess is estimated to be between 10^{43} and 10^{47} (a provable upper bound), with a game-tree complexity of approximately 10^{123}

      • Avatar di Roland

        Roland 7:25 pm on ottobre 19, 2011 | 393224

        Umh però l’ordine conta, quindi non si dovrebbe dividere per 32! Cioè per dire, re-pedone-torre è una configurazione diversa da torre-pedone-re. 64! potrebbe andare se si considera che nella prima casella possono presentarsi 64 casi (32 pezzi + 32 vuoti), nella seconda solo più 63 e cosi via. Però come dici tu penso che non tutte siano raggiungibili.

  19. Avatar di dofoo

    dofoo 3:10 pm on ottobre 18, 2011 | 392944

    menghiah, stasera studio :D
    :fav:

  20. Avatar di William J.

    William J. 3:14 pm on ottobre 18, 2011 | 392947

    Splendido post @ryanvespucci . :res: :fav:

  21. Avatar di abbo

    abbo 3:26 pm on ottobre 18, 2011 | 392955

    :fav:
    e attendo il seguito della tesi! :res:

  22. Avatar di EkV

    EkV 3:56 pm on ottobre 18, 2011 | 392965

    Questo articolo è qualcosa di epico.
    :fav: come se non ci fosse un domani!

  23. Avatar di Pandalf il Grigio

    Pandalf il Grigio 4:21 pm on ottobre 18, 2011 | 392975

    articolo interessantissimo :fav: attento alla grammatica però :sni:

    attendo le seguenti uscite

  24. Avatar di jred139

    jred139 5:21 pm on ottobre 18, 2011 | 392994

    :fav: :ln: AT ITS BEST

  25. Avatar di guillaume

    guillaume 8:48 am on ottobre 19, 2011 | 393126

    :fav: e :nt: super meritati.
    Articolo fantastico, kudos. :res:

  26. Avatar di Spaco Botilia Felix

    Spaco Botilia Felix 11:47 am on ottobre 19, 2011 | 393150

    :fav: Io favvo e leggo appena possibile.
    Ma sono l’unico che ha apprezzato anche il render introduttivo? Fatto te? Che sw? Motore di rendering?

  27. Avatar di dofoo

    dofoo 11:57 am on ottobre 19, 2011 | 393153

    io l’ho letto con calma ieri sera, è davvero un ottimo articolo. mi ha incuriosito molto, in chiave informatica, l’attribuzione del valore di cavallo e alfiere. avendo giocato spesso contro il pc (e avendo preso sonore batoste) ho notato che non è sempre così. L’ho notato perchè io, da niubbo, tendo a sacrificare l’alfiere. Quindi aspetto davvero il seguito nella speranza di capire come i software affrontano questo caso specifico e come riescano a discernere una casistica diversa dal mero valore del pezzo (sempre che sia prevista una spiegazione in merito). Mi viene il mal di testa solo a pensarci..
    +1 k

  28. Avatar di Ryan Vespucci

    Ryan Vespucci 11:10 am on ottobre 20, 2011 | 393289

    In effetti non è praticamente mai così. Quelle sono valutazioni molto grezze, sono messe lì solo per dare una base da cui partire. Vedremo più avanti che si tengono in conto molti “pesi” per dare una valutazione completa ai pezzi e alla fine non sarà solo quella che contribuirà alla decisione della mossa da fare. Ma niente spoiler! :D

  29. Avatar di lucamrblonde | veronerd™

    lucamrblonde | veronerd™ 12:58 am on ottobre 23, 2011 | 394125

    ARTICOLONE MEGA FAV :fav: domani finisco di leggerlo, ma promette benissimo, good job!

  30. La storia dei programmi scacchistici | Lega Nerd 4:08 pm on ottobre 25, 2011 | 394717

    [...] Riparte il nostro viaggio nel tempo alla scoperta della nascita dei programmi scacchistici, percorso fondamentale per capirne il significato e poi il funzionamento. Risaliamo dunque sulla DeLorean e viaggiamo a circa 100 anni da dove ci siamo lasciati l’ultima volta. [...]

  31. Avatar di fra9001 | Nè

    fra9001 | Nè 11:26 pm on novembre 15, 2011 | 401396

    :select:

  32. avatar

    nastavnic 5:58 pm on novembre 25, 2011 | 405128

    Magnific articolo!

  33. avatar

    nastavnic 5:58 pm on novembre 25, 2011 | 405129

    Magnifico articolo!

Rispondi

Devi essere loggato per lasciare un commento.