Newsgroup: it.hobby.scacchi
Titolo: algoritmo di abbinamento per tornei svizzeri

Salve,
non so se Montaruli sta ancora lavorando a quel progetto di algoritmo
svizzero in Perl. Vorrei dare al suo gruppo, e a qualcun altro all'ascolto,
lo spunto per qualche riflessione. Come sanno gli arbitri il problema
principale di un algoritmo di abbinamento FIDE è quello di generare le
coppie in un ordine particolare, quello del regolamento. Il problema risolto
a mano non e' affatto banale. Molti arbitri ritengono semplice lo svizzero
olandese  solo perche' non si sono trovati gruppi con diverse coppie
impossibili e perche' lasciavano al computer l'onere di trovare la
soluzione. In casi di poco non usuali cominciano a girare a vuoto come ho
sperimentato di persona. Esistono diverse tecniche per generare gli
abbinamenti per testarne la legalita':
1) uno brutale (e cretino) ma che funziona sempre, cioè generare tutte le
coppie eseguendo le trasposizioni e gli scambi previsti dal regolamento. Il
guaio è che così facendo si ottengono anche coppie che in precedenza si sono
escluse e si perde molto tempo per ricontrollarle; inoltre l'abbinamento
giusto potrebbe essere l'ultimo da generare e ciò fa perdere ulteriore
tempo;
2) brunch and bond: è come quello di prima ma con controlli per capire in
qualche modo che un abbinamento non funziona e quindi occorre smetterla con
inutili trasposizioni e passare agli scambi;
3) il maximum weighted matching: è il migliore per flessibilità in quanto ad
ogni coppia si da' un peso e si lascia al programma il compito di trovare il
massimo peso che è quello dell'abbinamento ideale. L'unico problema, non
banale, è quello di trovare una regola per assegnare il peso ad ogni coppia
in modo da generarle nel giusto ordine. Ciò viene fatto da una particolare
procedura. In principio cambiando tale procedura si possono riprodurre tutti
i sistemi di abbinamento ed inventarne di nuovi (lo svizzero olandese è
stato anche implementato in questo modo);
4) lo stable roommates problem: anch'esso è un metodo interessante e che
nelle mani giuste dovrebbe produrre dei buoni risultati. Per chi ne vuole
sapere di piu'  in rete trovate questo articolo
http://www.cs.uta.fi/reports/pdf/A-1995-2.pdf
 . In questa referenza gli
autori non hanno ottenuto risultati soddisfacenti ma credo vi siano ampi
margini di miglioramento se si ordinano meglio le liste delle preferenze
come loro stessi suggeriscono.
In rete trovate all'indirizzo
http://www.dcs.gla.ac.uk/research/algorithms/stable/default.html
 l'algoritmo
che opportunamento modificato rappresenta il cuore del programma. Io l'ho
scoperto tardi quando avevo perso la voglia di riscrivere un nuovo sistema.
Inoltre esso e' scritto in ADA 95 che non conosco. Tuttavia se in giro
esiste qualcuno che ha voglia di tradurlo in C e vuole collaborare forse
potrebbe rivenirmi la voglia.
Luigi

Premesso che non so di cosa sto parlando :) ma se il problema e' quello di 
trovare una soluzione "buona" anche che non sia la "migliore" -chiedo venia 
se ho capito male-, magari un algoritmo genetico puo' essere di aiuto.
Ho detto una stronz...???
Ciao
PLP 

 potrebbe rivenirmi la voglia.
Domani ci guardo e poi ne riparliamo.

 In questo modo tutti gli accoppiamenti possibili saltano fuori per forza.
Dopo 32.000 anni, ma saltano fuori :)
Alex


[ 32.000 * 365 + 32.000/4 (i bisestili) ] * 86400 fa circa 10^12 secondi
Ipotizzando un accoppiamento al secondo (ma proprio a stare larghi) vuol 
dire che per metterci 32.000 anni non bastano neppure tutti gli aventi 
elo fide in un unico immenso open.
Forse si presentera' il problema quando si disputera' il primo mega open 
intergalattico.

 Accoppio i primi due, e poi riapplico l'algoritmo ...
ho fatto la stessa cosa nel mio calcolo dell'italo svizzero; funziona e
semplifica la vita, l'unica difficoltà è garantire che la routine di
calcolo sia rientrante :)
Ciao. 
-- 
73 es 51 de i3hev, op. mario
Il vero Radioamatore si riconosce... dal call in firma! 
- Campagna 2005 "Sono un Radioamatore e me ne vanto"
it.hobby.radioamatori.moderato
http://digilander.libero.it/hamweb
http://digilander.libero.it/esperantovenezia

 fide in un unico immenso open.
Cerca "iperbole", figura retorica.
Alex

 ho fatto la stessa cosa nel mio calcolo dell'italo svizzero
Ma l'italo-svizzero funziona diversamente, si fa cosě di regola!
Alex

 fide in un unico immenso open.
Dimenticavo: mi dici quanti accoppiamenti possibili, ignorando i colori, ci 
sono con diciamo, 26 giocatori?
Alex

Alex Brunetti ha scritto:

non so cosa intendi per "di regola", visto che di programmi che lo fanno
ce ne sono tanto pochi da non poter certo fare una statistica... >:)
Peraltro, nel caso dell'italo svizzero il procedimento descritto dal
regolamento non č ricorsivo, č iterativo - quello che ci salva č il
teorema generale di equivalenza, quello che afferma che qualsiasi
algoritmo iterativo puň essere trasformato in un equivalente algoritmo
ricorsivo, e viceversa... ma non dice nulla sul quanto incasinata sia in
pratica la faccenda! ;)


 4) lo stable roommates problem: anch'esso è un metodo interessante
Sto lavorandoci da un paio d'anni; ho rallentato imbattendomi in una 
matematica piuttosto complessa. Darò un ochio alle tue fonti, grazie.
Alex

 Ho detto una stronz...???
No, non hai detto una strnz ma devi tenere presente che un algoritmo 
genetico non ti assicura di trovare un risultato. Potresti generare 
generazioni di accoppiamenti non validi, regolamento alla mano.
Non mi sono mai occupato del problema e non ne conosco il grado di 
complessità. Suppongo che si abbia una crescita esponenziale, come per la 
scelta delle mosse in un prg di scacchi. In questi casi, io preferisco 
sempre ricorrere direttamente all'assembly, a parità di algoritmo, 
s'intende.
Stefano 

 In questo modo tutti gli accoppiamenti possibili saltano fuori per forza.
 
Sicuramente si riusciranno a generare tutti gli abbinamenti (abbinamento =
insieme delle coppie in un dato gruppo di punteggio) ma poi devi ordinarli
per scegliere quello buono. Oppure devi avere un criterio che ti dica che
ottenuto un abbinamento non ce ne sara' un altro migliore. Altrimenti il
numero delle combinazioni diventa ingestibile in tempi brevi come ha notato
Brunetti.
Con l'italo svizzero e' piu' semplice e, come e' stato rilevato, fattibile.
Li' tu vai sempre avanti e qualche problema potrebbe esserci solo verso la
fine per chiudere il processo. Ma se non si chiudesse il problema potrebbe
essere risolto accoppiando i pochi giocatori rimasti con un altro metodo
piu' spartano. Purtroppo l'italo-svizzero e', giustamente, bandito anche in
Italia per motivi di cui abbiamo ampiamento discusso in questo NG.
Ad ogni modo anche una procedura del tipo 1) non è da buttare via. Infatti
se il gruppo e' poco popolato allora la procedura non dovrebbe pesare troppo
in termini di tempo. Mentre se il gruppo e' molto popolato si riduce il
numero delle coppie incompatibili e quindi l'abbinamento buono puo' essere
generato subito. Esistono pero' casi estremi che potrebbero renderlo molto
lento. Anche qui il regolamento FIDE non aiuta molto. In un gruppo di 12
giocatori puo' essere necessario scambiare 3 giocatori alla volta da S1 a
S2. Nel regolamento si parla solo di 2. Qualcuno e' sicuro sulla tecnica da
usare in questi casi?
Luigi
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 ci sono con diciamo, 26 giocatori?
Secondo la mia matematica arrugginita. Il primo si può accoppiare con 25, il 
prossimo con 23 e così via, fino agli ultimi due. So che c'è una formula, 
per calcolarlo... ma non ho voglia di cercarla... andando a memoria/intuito, 
direi:
25*23*21*...*3*1
circa 8*10^12, ovvero circa 8.000.000.000.000 (otto mila miliardi). I 
possibili colori dovrebbero essere definiti da regolamento. Se fossero da 
determinare, si dovrebbe moltiplicare il tutto per 2^13, che aggiunge circa 
4 zeri. Non considerandoli, un programma in grado di accoppiare 1.000.000 di 
giocatori al secondo impiegherebbe 8.000.000 di secondi ovvero più di 2000 
ore, che equivale ad un turno ogni 3 mesi.
Stefano Gemma
PS: matematici non insultatemi... ma correggetemi pure, dove ho sbagliato! 
;) 

 matematica piuttosto complessa. Darò un ochio alle tue fonti, grazie.
Il compilatore ADA 95 esiste freeware sotto linux. Su quel sito c'e' anche
una versione in Java. La versione che serve per fini scacchistici e' quella
scritta in ADA 95 che elenca le coppie realizzate oltre le persone unmatched
(i nostri floater).
Tale algoritmo talvolta ammette piu' di un matching stabile per cui occorre
individuare proprio quello corretto.


 wrote in message
news:438b7...@x-privat.org

Boh... aspetta che li conto.
C'e' da prendere il triangolo di Tartaglia
Allora...
gioc. coppie
1	0
2	1
3	3
4	6
5	10
6	15
7	21
8	28
9	36
10	45
11	55
12	66
13	78
14	91
15	105
16	120
17	136
18	153
19	171
20	190
21	210
22	231
23	253
24	276
25	300
26	325
Fa 325. E quindi?
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 C'e' da prendere il triangolo di Tartaglia
mmmm... mi sa che io ho contato le possibili combinazioni di accoppiamenti, 
non le possibili coppie!!! (che ovviamente si possono ripetere, in 
combinazioni diverse di accoppiamenti). Se è come dici tu (e non lo metto in 
dubbio), un qualsiasi prg ce la fa in un attimesimo di secondo... o 
sbagliamo entrambi? ;)
Stefano

sono con diciamo, 26 giocatori?
Se non conta l'ordine di estrazione delle coppie
allora sono circa 7900 miliardi.

 wrote in message
news:dmh9o9$sa2$
1...@newsreader.mailgate.org

Dunque, ragioniamo.
Se i giocatori fossero 2, la coppia e' una AB
Se i giocatori fossero 3 le coppie sono AB AC BC
Se i giocatori fossero 4 le coppie sono AB AC AD BC BD
Se i giocatori fossero 5 le coppie sono AB AC AD AE BC BD BE CD CE DE
etc...
Io ho contato queste.
Qui la domanda da porre e': stiamo contando la stessa cosa io e te?
Perche' tu puoi benissimo aver contato una cosa diversa dalla mia e
quindi aver ottenuto un risultato diverso dal mio.


C'e' da prendere il triangolo di Tartaglia
Roberto, si parlava di liste di accoppiamenti...proprio
quelle che dovresti generare, guarda un po' :)

 Fa 325. E quindi?
E quindi niente, 325 sono le coppie possibili, i possibili accoppiamenti 
sono quelli indicati da Gemma.
Alex

 Italia
Non è bandito, è solo limitato ai tornei di promozione (per l'RTF; a cadenza 
rapida è libero) anche se alcuni tornei non di promozione lo adottano 
ugualmente.
Alex

 ;)
Non sono un matematico.
Ciao,
Marco.


 cioe' 26! / [2!(26-2)!] = 25*26/2=325.
No, quello è il numero di coppie diverse possibili (ignorando il colore, 
sennò raddoppiano.)
Alex

"Adriano Lorenzini" <escher.c...@libero.it.invalid> wrote in
message 
news:i78oo1hrh5nvlud9d...@4ax.com

?
Non ho mica capito...
Se AB CD e' un accoppiamento
diverso da CD AB allora mi puo' tornare quello che
dici, ma se AB CD e CD AB sono equivalenti allora perche' questo numero?
(magari con 4-5 giocatori si puo' fare)


 Marco.
Ok, ho visto la spiegazione di Brunetti,
Ciao,
Marco


 sennò raddoppiano.)
Si effettivamente non avevo capito la domanda..


individuare proprio quello corretto.
A proposito di matching, in questi giorni stavo giocherellando con
Swiss Manager e Vega, dando loro in pasto i dati di un torneino
svizzero a 8 giocatori cui ho appena partecipato.
Ebbene, al 4. turno Vega non ne vuole sapere di invertire i colori
sulla prima scacchiera, come da accoppiamento effettivo: anche se
reimposto il turno a mano, lui poi ridà invariabilmente il Bianco al
giocatore con più punti (o rating, o peli sulle braccia, o che so).
Ipotizzando un possibile errore degli arbitri (che usavano il Diena,
ma quel turno l'avevano rifatto a mano a seguito di un forfait), ho
fatto la controprova con Swiss Manager, il quale però accetta
tranquillamente che io forzi il Nero al giocatore più quotato.
Dove sta l'inghippo?
Grazie in anticipo per qualunque chiarimento e cordiali saluti.
-- 
Andrea Malfagìa
L'indirizzo giusto per contattarmi è "andrea punto malfagia chiocciola fastwebnet punto it".

tranquillamente che io forzi il Nero al giocatore più quotato.
Mi sembra di aver letto da qualche parte sul manuale del Vega che lui
comunque fa il controllo di correttezza dei colori e non ti permette,
quindi, di cambiare il colore se questo è contrario alle sue regole
di abbinamento. Però non sono sicuro, Forlano potrà essere più preciso.
Con Diena e con lo Swiss invece si può fare (partendo dal principio
che è se è l'arbitro che lo fa, qualunque motivo abbia, vuol dire che
sa quello che fa; tra l'altro potrebbe essere un'azione necessaria
"a posteriori", dopo una partita giocata per errore con i colori
invertiti, per dare a ogni giocatore il colore corretto ogni turno,
nel tentativo di bilanciare i colori nei turni successivi).
Ciao!
Maurizio Mascheroni

nel tentativo di bilanciare i colori nei turni successivi).
Infatti mi pare che Vega su questo aspetto sia troppo rigido a
paragone degli altri due.
Salutoni.


 fide in un unico immenso open.
Per i 65.793 giocatori con Elo FIDE, morti compresi, ci sono circa 
10^144.000 possibili accoppiamenti, naturalmente trascurando il colore, 
altrimenti si deve moltiplicare per 4,8*10^9.902. In effetti 32.000 anni non 
è molto corretto.
Alex

 Dove sta l'inghippo?
Il programma accetta tutte le modifiche fatte dall'arbitro ed e' stato anzi
progettato per inchinarsi ai voleri e capricci dell'arbitro. Da quanto ho
capito hai realizzato un abbinamento manuale. All'OK il programma ha
riassegnato il Bianco al giocatore "sbagliato". Infatti durante
l'inserimento manuale  l'arbitro non deve preoccupoarsi dei colori che
verranno riassegnati automaticamente.
E se i colori non mi piacciono e voglio forzarli diversamente? Come spiegato
in piu' punti del manuale basta un doppio click sulla coppia interessata ed
avviene lo scambio. Per piacere prova e fammi sapere qualora non
funzionasse.
Luigi Forlano

funzionasse.
L'avevo letta questa cosa del doppio click, ma non ero riuscito a
farla andare. Poco fa, confortato dal fatto che tu l'abbia ribadita,
ho riprovato e ha funzionato. O avevo i polpastrelli appisolati,
oppure lo facevo nel momento sbagliato, non so, comunque ho risolto e
posso proseguire nella compilazione del torneo.
Grazie ancora!


 2) brunch and bond:
Branch and bound.
(Correggo non per pignoleria, ma per aiutare chi volesse googlare)
Ciao
P.