Messaggio
da MindFlyer » 19 ago 2005, 17:07
Ecco quello che intendevo con "definire induttivamente le configurazioni di vittoria e di patta sull'albero delle partite" (ché forse non mi ero spiegato alla bisogna).
Sia $ P $ l'insieme dei pezzi degli scacchi $ P=\{\mbox{Re}, \mbox{Regina}, \mbox{Torre}, \mbox{Alfiere}, \mbox{Cavallo}, \mbox{Pedone}\} $.
Sia $ Pos $ l'insieme delle posizioni dei pezzi sulla scacchiera $ Pos=(P \cup \{\mbox{Vuoto}\})^{64} $.
Sia $ C $ l'insieme delle configurazioni di partita $ C=Pos\times \{\mbox{Bianco}, \mbox{Nero}\}\times \{1,2,3\} $.
A livello intuitivo, il primo elemento della terna rappresenta le posizioni dei pezzi sulla scacchiera, il secondo elemento indica il giocatore che deve muovere, il terzo elemento indica quante volte è stata raggiunta la posizione nella partita.
Sia $ i=(p,\mbox{Bianco}, 1)\in C $ la configurazione iniziale degli scacchi, dove $ p $ è la posizione con i 32 pezzi nelle case di partenza.
Sia $ F \subset C $ l'insieme delle configurazioni finali, ovvero le configurazioni $ (p,t,v) $ dove $ v=3 $ oppure $ p $ è una posizione di matto o di stallo (qui non considero la regola delle 50 mosse o delle 120 mosse, perché i due giochi risultanti sono equivalenti).
Sia $ c=\#C $ la cardinalità (finita) di $ C $.
Sia $ T=(N,A) $ un albero $ c $-ario di radice $ r $ e di profondità $ c $, e sia $ f_0 : N \rightarrow (C \cup \{\mbox{Nullla}\}) $ una funzione tale che $ f_0(r)=i $ e $ f_0(n)=\mbox{Nullla} $, per ogni $ n\in N $, $ n\neq r $.
Sia $ h : (N \setminus \{r\}) \rightarrow N $ la funzione predecessore rispetto all'albero $ T $ (ovvero la funzione che manda ogni nodo non radice nel suo nodo "padre").
Sia $ b : N \rightarrow \wp (N) $ la funzione tale che $ b(r)=\{r\} $ e $ b(n)=\{s\in N \mid h(s)=h(n)\} $ per ogni $ n\in N $, $ n\neq r $, (ovvero la funzione che manda ogni nodo nell'insieme dei suoi "fratelli").
Definiamo induttivamente la successione di funzioni $ \{f_n\} $, dove $ f_n : N \rightarrow (C \cup \{\mbox{Nullla}\}) $, in modo che $ f_{n+1}(s)=f_n(s) $ se $ f_n(b(s)) \neq \{\mbox{Nulla}\} $, oppure se $ f_n(h(s)) \in (F \cup \{\mbox{Nulla}\}) $. In caso contrario, supponiamo definito un ordinamento totale tra gli elementi di $ C $, e tra ogni insieme di $ c $ nodi "fratelli" di $ T $. Allora, se $ s $ è il $ k $-esimo elemento di $ b(s) $, sia $ a=(p,t,v)=f_n(h(s)) $ e sia $ a'=(p',t',v') $ il $ k $-esimo elemento di $ C $. Diciamo che $ a' $ segue $ a $ se $ p' $ è la posizione risultante da una mossa legale del giocatore $ t $ nella posizione $ p $, $ t \neq t' $, ed inoltre $ v' $ è pari al successore del numero di volte che la posizione $ p' $ compare come primo elemento delle configurazioni del tipo $ f_n(m) $, dove $ m $ varia sull'unico cammino di $ T $ da $ r $ a $ h(s) $ (estremi inclusi). In caso di arrocco o presa en passant va fatto un ulteriore controllo, analogo a quello appena descritto, sul cammino fino alla radice, per verificare che sussistano le condizioni sulle mosse precedenti. Se $ a' $ segue $ a $, allora poniamo $ f_{n+1}(s)=a' $, altrimenti poniamo $ f_{n+1}(s)=\mbox{Nulla} $. Si verifica facilmente per induzione che queste definizioni sono consistenti (ovvero ogni configurazione non in $ F $ è seguita da qualche configurazione, etc).
Consideriamo ora l'albero $ Z=(N',A') $ ottenuto da $ T $ rimuovendo i nodi $ n $ tali che $ f_c(n)=\mbox{Nulla} $, e rimuovendo gli archi con un estremo in tali nodi (la dimostrazione che $ Z $ è un albero è per induzione sulla definizione di $ \{f_n\} $), e sia $ f: N' \rightarrow C $ la restrizione di $ f_c $ a $ N' $.
La coppia $ (Z,f) $ prende il nome di albero delle partite di scacchi, e si dimostra che, se $ n $ è una foglia di $ Z $, allora $ f(n)\in F $.
Si definisca induttivamente una successione di funzioni $ \{g_n\} $, dove $ g_n : N' \rightarrow \{\mbox{Vince}, \mbox{Perde}, \mbox{Patta}, \mbox{Nulla}\} $, come segue.
Se $ s\in N' $ non è una foglia di $ Z $, allora $ g_0(s)=\mbox{Nulla} $. In caso contrario, sia $ f(s)=(p,t,v)\in F $. Se $ p $ è una posizione di matto, allora $ g_0(s)=\mbox{Perde} $, altrimenti $ g_0(s)=\mbox{Patta} $.
Se $ g_n(s)\neq \mbox{Nulla} $ oppure se esiste un nodo $ s'\in N' $ tale che $ s=h(s') $ (dove $ h $ è la restrizione dell'omonima funzione "padre" definita su $ N\setminus \{r\} $) e $ g_n(s')=\mbox{Nulla} $, allora $ g_{n+1}(s)=g_n(s) $. Altrimenti, sia $ H=\{s'\in N' \mid h(s')=s\} $. Se $ g_n(H)=\{\mbox{Vince}\} $, allora $ g_{n+1}(s)=\mbox{Perde} $; se $ \mbox{Perde}\in g_n(H) $, allora $ g_{n+1}(s)=\mbox{Vince} $; altrimenti $ g_{n+1}(s)=\mbox{Patta} $.
Si dimostra facilmente per induzione che $ \mbox{Nulla}\not\in g_c(N') $, e quindi si ponga $ g=g_c $, con $ g: N' \rightarrow \{\mbox{Vince}, \mbox{Perde}, \mbox{Patta}\} $.
La terna $ (Z,f,g) $ è la classificazione delle configurazioni di vittoria e patta sull'albero delle partite di scacchi. Per sapere se gli scacchi sono un gioco vinto per un giocatore o pari, basta calcolare $ g(r) $.
).
)... ma quando gioco a scacchi tutto quello che faccio è provare più combinazioni possibili finchè ci riesco mnemonicamente (per questo sforzo mnemonico, lo sforzo di andare lontano a pensare..) invece quando faccio un problema devo fare assolutamente l'opposto... passata la prima fase dove per guardare come va il problema faccio 2 o 3 tentativi mi concentro per trovare la via che mi porterà alla vittoria senza andare per tentativi... o meglio, andando per tentativi ma in un altro senso perchè in questo caso provo più approcci risolutivi...