Newsgroup: it.hobby.scacchi
Titolo: Spiegato l'errore di Shredder

Vedi 
http://www.chessbase.com/newsdetail.asp?newsid=2525
 al paragrafo
"Mercosur Cup, Argentina"
E' interessante la frase
"the organisers tested the critical position again with Shredder and
diagnosed the problem as a "one in a million" error in the hash tables."
Quindi anche i software scacchistici, essendo fatti da noi, possono
cappellare...
Luigi Caselli

 cappellare...
Complimenti ai programmatori...
Se l'hash è usato per quello che penso io, avrebbero dovuto fare in modo da
ridurre a 0 la probabilità di collisione.
E non credo sarebbe stato troppo difficile :)
Spider

 E non credo sarebbe stato troppo difficile :)
Infatti è banale: basta avere una hash che possa contenere più o meno 10^48
entrate.
Alex

 ha scritto nel messaggio
news:CVXDe.191700$75.82...@news4.tin.it...

Ma in che senso può esserci una collisione nella hash table?
Non è solo una velocizzazione dell'analisi considerando posizioni già
analizzate in precedenza?
Luigi Caselli

 analizzate in precedenza?
Sì, e per fare questo le memorizzi in una tabella ad accesso rapido (hash),
la quale è indicizzata con una chiave funzione della posizione. Siccome le
posizioni possibili sono diversi ordini di grandezza di più della dimensione
tecnicamente possibile per una tabella, comunque buona sia la tua funzione
di chiave, le collisioni, cioè la possibilità di imbattersi in una posizione
la cui chiave sia uguale a quella di un'altra posizione diversa già in
tabella, sono possibili. Naturalmente c'è modo e modo di agire di
conseguenza, ma la collisione in sè, oggi, è inevitabile.
Alex

 ha scritto nel messaggio
news:5A1Ee.192026$75.83...@news4.tin.it...

Grazie, adesso ho capito.
Quindi, se le hash table sono attivate, è bene non abbandonare anche in
netto svantaggio perchè il computer potrebbe cappellare?
O la partita citata è veramente un caso più unico che raro?
Luigi Caselli

 O la partita citata č veramente un caso piů unico che raro?
La seconda che hai detto.
Alex


Sul forum del Computer-Chess Club , Bob Hyatt dice che non può essere una 
hash collision :
[Bob Hyatt]
"I would agree.  Hash collisions simply will not cause this.  Even if you 
use 32
bit signatures..."
[/Bob Hyatt]
e parla di un PC overclocked non sufficientemente testato:
[Bob Hyatt]
"That is _highly_ likely.  I've seen it many times.  I even spent time more 
than
once debugging something someone sent me only to be unable to reproduce it 
at
all.  Then they say "this is on an overclocked machine running at XXX, but 
it
passed all the overclocking tests.."  That is now always the first question 
I
ask when someone sends me an unusual problem."
[/Bob Hyatt]
Ciao, Ciro

 entrate.
Scrivere un programma di scacchi è certamente una cosa difficile, non ne
dubito.
Ma per dire "due posizioni sono uguali" non puoi affidarti ad un hash,
proprio per
l'elevato numero di posizioni possibili. L'hash lo usi per dire "queste due
posizioni
sono sicuramente diverse", ma se gli hash sono uguali ci vuole qualche altro
controllo.
E se la probabilità di collisione è abbastanza bassa, questi controlli
aggiuntivi capiteranno
talmente raramente da non costituire un overhead apprezzabile.
In ogni caso, non ho mai provato a scrivere un programma di scacchi, perciò
sono
all'oscuro delle problematiche che si possano effettivamente presentare
nella realizzazione.
Ciao,
Spider

 talmente raramente da non costituire un overhead apprezzabile.
Come ho già scritto, i controlli aggiuntivi li puoi fare, puoi fare tutto
quello che vuoi, rimediarvi e renderne nullo l'effetto negativo. Ma la
collisione in sè permane.
Alex

 collisione in sè permane.
E' quello che intendevo, loro evidentemente non l'hanno reso nullo l'effetto
della collisione, o magari non fanno proprio nessun controllo.
Potevano aspettarselo allora che prima o poi sarebbe capitato.
Spider

 Potevano aspettarselo allora che prima o poi sarebbe capitato.
Se il problema fosse dovuto alla hash, ma forse no: leggi il post di Ciro :)
Alex

nella realizzazione.
Domanda (sia pur tardiva): se delle posizioni precedentemente
analizzate conservi solo codice hash e valutazione, che "altro
controllo" pensi di poter fare?

 controllo" pensi di poter fare?
In genere si memorizzano anche altre informazioni (qui puoi vedere per
esempio la struttura usata da Crafty: 
http://tinyurl.com/8uea4
). Se conservi
solo quei due dati è quasi impossibile. O meglio, in realtà il codice hash
non lo conservi, perché lo usi come indice della tabella hash, quindi se
conservi un codice è una seconda funzione di hash, con cui verifichi se la
posizione è effettivamente quella desiderata (come fa appunto Crafty).
Materiale didattico con Google: "hash table" "handle collisions".
Alex