Newsgroup: it.hobby.enigmi
Titolo: Scacchi?

Ciao, ho trovato un quesito interessante da porvi ( anche se ho la netta
senzazione che sia una specie di classico ), nelle FAQ non appare
comunque.
Allora, abbiamo la classica scacchiera di 64 caselle con il quadrato
centrale di quattro caselle occupato da:
- Un re
- Una regina
- Una torre
- Un alfiere
( RE REG
  TO ALF )
I pezzi si possono muovere secondo le comuni regole degli scacchi, ma
solo in direzione dei bordi della scacchiera, quindi quando un pezzo
raggiunge l'angolo non puo' piu' muoversi. 
Due giocatori si affrontano, chi non puo' piu' muovere niente quando
viene il suo turno perde. 
La prima mossa e' vostra... esiste la mossa che assicura la vittoria?
Se si' qual'e'? Con relativa spiegazione della risposta ovviamente :-)
... e per favore, non risolvetelo in 2 minuti ;-)
-- 
Fabio   fabio161616(at)
libero.it
 blackmagic(at)
penguinpowered.com
 
If you're not part of the solution, be part of the problem!

 raggiunge l'angolo non puo' piu' muoversi.
Non ho ben capito. Ipotizziamo che io muova il re in alto di una casella. Tu
puoi muoverlo dinuovo in basso? Ovviamente no, penso io. Allora mi viene da
pensare che i pezzi si possano muovare solo verso i bordi più vicini a loro.
E' esatto dire che i pezzi si spostano esclusivamente nel seguente modo?
RE - O, N
REG - N, N/E, E
ALF - S/E
TO - S, O
<Anche se ho le zanne e le corna, io sto solo piangendo,
eppure vogliono uccidermi ugualmente...>
By(t)e By(t)e
Giuseppe Bertone

 TO - S, O
Si'
Hai capito perfettamente :-)
-- 
Fabio   fabio161616(at)
libero.it
 blackmagic(at)
penguinpowered.com
 
Your mouse has moved. Windows NT must be restarted for the change to 
take effect. Reboot now?  [ OK ] 

Ora che hai chiarito possiamo risolverlo :-)
Probabilmente in questo caso con mosse limitate ci saranno metodi migliori,
comunque come al solito grazie a Grundy ci calcoliamo i relativi valori per
tutti e 4 i pezzi, ricordiamo che la disposizione e' la seguente:
RD
TA
I valori si ottengono in questo modo: si parte dai bordi i quali hanno
valore zero, poi man mano si guarda una casella dalla quale si possono
raggiungere solo i bordi, e le si da il valore del minimo delle caselle che
puo' raggiungere aumentato di uno.
Tale valore si chiama il valore della funzione di grundy della casella per
quel pezzo. A meno di errori questi sono i valori per ognuno dei 4 pezzi.
-------------
|0 |3 |4 |1 |
-------------
|0 |2 |1 |4 |
-------------
|0 |1 |2 |3 |
-------------
|0 |0 |0 |0 |
-------------
torre
-------------
|0 |0 |0 |0 |
-------------
|3 |2 |1 |0 |
-------------
|1 |3 |2 |0 |
-------------
|2 |1 |3 |0 |
-------------
Donna
-------------
|3 |  |  |0 |
-------------
|  |2 |  |0 |
-------------
|  |  |1 |0 |
-------------
|0 |0 |0 |0 |
-------------
alfiere
-------------
|0 |0 |0 |0 |
-------------
|0 |1 |2 |1 |
-------------
|0 |2 |0 |3 |
-------------
|0 |1 |3 |1 |
-------------
re
Ricapitolando le posizioni iniziali chiamando 0 la posizione iniziale
abbiamo
T(0)=1 R(0) = 1 D(0) = 2 A(0) = 3;
Ricordo che una posizione e' perdente per chi deve giocare se facendo l'Xor
di tutte le posizioni ottengo zero. Ossia trasformando in binario tutte le
posizioni iniziali, se la somma di tutte le colonne da pari allora per chi
deve giocare sono guai!
Quindi trasformando in binario abbiamo
Posizione iniziale donna   = D(0) = 2 =      1 0
Posizione iniziale re      = D(0) = 1 =      0 1
Posizione iniziale torre   = D(0) = 2 =      0 1
Posizione iniziale alfiere = D(0) = 2 =      1 1
La somma dell'ultima colonna e' dispari, dobbiamo renderla pari.
Quindi soluzione:
Abbiamo 3 modi: fare un passo in diagonale col re, fare un passo avanti
con alfiere, o andare sul bordo con la torre.
Sono interdetto, tu parli di una mossa (parrebbe unica).
Ciao
Andrea
P.S. Spero si incolonni tutto giusto
--
Posted from [212.17.205.1] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Sono interdetto, tu parli di una mossa (parrebbe unica).
Nessuno dei tuoi modi corrisponde con la soluzione che ho io. Ora non ho
tempo di verificare, lo faro' presto :-)
-- 
Fabio   fabio161616(at)
libero.it
 blackmagic(at)
penguinpowered.com
 
Every program has two purposes -- one for which it was written and
another for which it wasn't.

 Sono interdetto, tu parli di una mossa (parrebbe unica).
mmm! E' vera la perfetta corrispondenza al Nim, ma la sol. e' veramente
unica.
Conosco il prob. cosi' mi astengo dalla discussione.
La mossa che suggerisci della torre, ad es. e' contradditoria,
portandola al bordo, il tuo avversario puo' spostarla nell'angolo
bloccandola, oppure fermarsi un passo prima lasciando alla torre ancora
una mossa. Queste 2 situazioni sono di parita' differente.....
In realta' la Torre, si trova a 3,3 caselle dal bordo, corrisponde
percio' a due linee di 3 pezzi ciascuno, e quindi e' favorevole al
secondo giocatore, che puo' giocare in modo simmetrico, percio' puo'
essere ignorata nel senso che se il mio avversario la sposta di 1,2,3
caselle, ribilancio la posizione muovendo di 1,2,3 perpendicolarmente.
ciao :) dario

Avevo semplicemente capito che quando un pezzo toccava il bordo
si fermava, non l'angolo. Colpa mia.
Riporto la soluzione corretta. Si Dario la soluzione e' la stessa del Nim,
ampliata. Conway docet. Guarda anche le permutazioni sincronizzate.
Ciao Fabio guarda se questa corrisponde :-) Abbiamo 1 solo  modo: fare un
passo in diagonale con la donna.
Probabilmente in questo caso con mosse limitate ci saranno metodi migliori,
comunque come al solito grazie a Grundy ci calcoliamo i relativi valori per
tutti e 4 i pezzi, ricordiamo che la disposizione e' la seguente:
RD
TA
I valori si ottengono in questo modo: si parte dai bordi i quali hanno
valore zero, poi man mano si guarda una casella dalla quale si possono
raggiungere solo i bordi, e le si da il valore del minimo delle caselle che
puo' raggiungere aumentato di uno.
Tale valore si chiama il valore della funzione di grundy della casella per
quel pezzo. A meno di errori questi sono i valori per ognuno dei 4 pezzi.
-------------
|3 |2 |1 |0 |
-------------
|2 |3 |0 |1 |
-------------
|1 |0 |3 |2 |
-------------
|0 |1 |2 |3 |
-------------
torre
-------------
|3 |2 |1 |0 |
-------------
|4 |0 |2 |1 |
-------------
|5 |1 |0 |2 |
-------------
|6 |5 |4 |3 |
-------------
Donna
-------------
|3 |  |  |  |
-------------
|  |2 |  |  |
-------------
|  |  |1 |  |
-------------
|  |  |  |0 |
-------------
alfiere
-------------
|0 |1 |0 |1 |
-------------
|1 |2 |3 |2 |
-------------
|0 |3 |0 |1 |
-------------
|1 |2 |1 |2 |
-------------
re
Ricapitolando le posizioni iniziali chiamando 0 la posizione iniziale
abbiamo
T(0)=0 R(0) = 2 D(0) = 6 A(0) = 3;
Ricordo che una posizione e' perdente per chi deve giocare se facendo l'Xor
di tutte le posizioni ottengo zero. Ossia trasformando in binario tutte le
posizioni iniziali, se la somma di tutte le colonne da pari allora per chi
deve giocare sono guai!
Quindi trasformando in binario abbiamo
Posizione iniziale donna   = D(0) = 6 =    1  1 0
Posizione iniziale re      = D(0) = 2 =    0  1 0
Posizione iniziale torre   = D(0) = 0 =    0  0 0
Posizione iniziale alfiere = D(0) = 3 =    0  1 1
La somma dell'ultima e prima colonna e' dispari, dobbiamo renderla pari.
Abbiamo 1 solo  modo: fare un passo in diagonale con la donna.
--
Posted from [212.17.205.100] by way of 
law-oe33.hotmail.com
 [209.185.131.32] 



Anch'io ho notato le somiglianze col Nim ma dopo alcuni tentativi mi è
sembrato che ci fossero troppe diversità e ho tentato un approccio
più "scacchistico".
La mossa vincente per il primo giocatore mi pare che sia :
S
P
O
I
L
E
R
2 passi della donna in diagonale
Sto cercando di scrivere una spiegazione comprensibile che posterò al più
presto.
Ciao
Massimo

 Abbiamo 1 solo  modo: fare un passo in diagonale con la donna.
Bravo.
Il quesito l'ho trovato su un vecchio numero di MCmicrocomputer
(luglio/agosto 1995) e mi aveva affascinato anche per la spiegazione
molto chiara. Spiegava il problema del nim e come calcolare le posizioni
sicure e insicure.
A quanto pare questo era davvero un classico e ovviamente tutti voi
conoscete il nim, ho voluto fare il tentataivo :-)
L'articolo cita anche Conway, che a quanto ho capito anche dal tuo post,
dev'essere una specie di santone del genere e cita pure due libri:
Winning ways e On numbers and games che suppongo siano un cosa tipo il
vecchio e nuovo testamento per voi :-)
Sapete dove posso trovare informazioni su questi libri e magari anche su
Conway?
Poi: l'articolo finisce con un "Ma la cosa piu' affascinante eě l'enorme
numero di problemi cui questa tecnica si adatta". Ne avete qualche
esempio? (mi sono perso il numero seguente :-))
(consideratelo come un nuovo quesito dato che non mi avete dato
soddisfazioni con questo ;-) )
-- 
Fabio   fabio161616(at)
libero.it
 blackmagic(at)
penguinpowered.com
 
There are two major products that come out of Berkeley: LSD and UNIX.
We don't believe this to be a coincidence.  -- Jeremy S. Anderson


La soddisfazione c'e' quando uno lo indovina, altrimenti non c'e' gusto!

Ho toppato la tabella del Re, per fortuna non cambia il valore della casa di
partenza.
Re
+-----------#-
|0 |1 |0 |1 #
|--+--+--+--#-
|1 |2 |3 |2 #
|--+--+--+--#-
|0 |3 |0 |1 #
|--+--+--+--#-
|1 |2 |1 |2 #
#############-
|  |  |  |  |
Silv:o)

 che puo' raggiungere aumentato di uno.
Io lo conoscevo cosi' (mi pare che si chiami MEX, minimo escluso): ogni
casella prende il minimo tra i valori non compresi tra quelli raggiungibili.
Per esempio, la Donna in F6 puo raggiungere solo 0 oppure 2, ma non l'1 (il
minimo escluso), quindi F6 ha valore 1.
Con questa regola la tabella diventa
Re                  Donna
+-----------#-----------+
|0 |1 |0 |1 #3 |2 |1 |0 |
|--+--+--+--#--+--+--+--|
|1 |1 |2 |3 #4 |0 |2 |1 |
|--+--+--+--#--+--+--+--|
|0 |2 |0 |1 #5 |1 |0 |2 |
|--+--+--+--#--+--+--+--|
|1 |3 |1 |2 #6 |5 |4 |3 |
#########################
|3 |2 |1 |0 #3 |  |  |  |
|--+--+--+--#--+--+--+--|
|2 |3 |0 |1 #  |2 |  |  |
|--+--+--+--#--+--+--+--|
|1 |0 |3 |2 #  |  |1 |  |
|--+--+--+--#--+--+--+--|
|0 |1 |2 |3 #  |  |  |0 |
+-----------#--+--+--+--+
Torre             Alfiere
Ed i valori iniziali sono
R => 2 = 0 1 0
D => 6 = 1 1 0
T => 0 = 0 0 0
A => 3 = 0 1 1
Xor    = 1 1 1
Quindi tutte le colonne vanno cambiate in una sola mossa. L'unica mossa
possibile e` Donna in F6.
Ciao, Silv:o)
PS il gioco lo conoscevo da tempo, ma risolverlo di nuovo mi ha divertito.


  Scusate ma non sono molto convinto dalla soluzione.
Secondo me la mossa vincente č DUE  passi in diagonale con la donna.
Alla mossa di un passo in diagonale con la donna ripondo con un altro
passo in diagonale con la stessa. Qual č la terza mossa?
Proviamo a giocare una partita, se perdo sarņ convinto.
Ciao
Massimo

Muovo l'alfiere fino all'angolo.
Puoi fare le mosse anche tu se vuoi.
Muovendo la donna in diagonale avanti di 2 caselle
finisci in una posizione di donna di valore 2,
quindi
Posizione tua donna   = D(0) = 2=      0  1 0
Posizione iniziale re      = D(0) = 2 =    0  1 0
Posizione iniziale torre   = D(0) = 0 =    0  0 0
Posizione iniziale alfiere = D(0) = 3 =    0  1 1
per rendere la somma di tutte le colonne pari occorre
appunto fare si che l'ultima riga sia zero, ossia andare
con l'alfiere in angolo.
Non vorrai mica giocare tutta la prtita qui sul newsgroup spero :-)
Ciao
Andrea
--
Posted from [212.17.205.1] 


 quel pezzo.
Lo avevo già scritto in un messaggio di qualche giorno fa che il server di
Galattica forse si è mangiato, comunque...
Io il metodo lo conoscevo con un altro nome (MEX, minimo escluso), e la
regola non è esattamente quella che enunci tu, anche se poi le tabelle sono
uguali. Hai scritto male la regola o non l'ho bene interpretata io? Boh.
Lo conoscevo così: il valore di una casella è pari al più piccolo dei valori
non compresi tra quelli raggiungibili. Se da una casella ho accesso a
caselle marcate 0, 1 e 3, il valore della casella è 2, il primo degli
esclusi, mentre come l'hai enunciato tu (il minimo aumentato di uno) pare
che il valore da assegnare sia 1.
MEX = grundy?
Ciao, Silv:o)

MEX = grundy?
Mah, MEX mai visto, Grundy e' il nome che ho trovato su un
libro di analisi di grafi, ma per la bibliografia chiedere lumi a Dario
e' meglio :-)
Ciao
Andrea
P.S. Scommetto che stai già facendo un programma che calcola le otto terne
di Dario :-)))


Tuttavia un anno fa mi dava disponibilita' sia amazon che books.com...
Solo per il secondo volume, il primo e' assolutamente introvabile (ci
provo da anni).
ciao :) dario
PS Per dare a Cesare quel che e' di Cesare l'articolo ed il problema
sono di Dani Ferrari.
MCmicrocomputer 153 luglio/agosto 1995 pagg 251-253.

 Non vorrai mica giocare tutta la prtita qui sul newsgroup spero :-)
No, non è necessario. Ho scoperto un bug nel mio calcolo :-(
Grazie
Ciao
Massimo

 all'incrocio e troviamo N(3).
Tutto bene, faccio notare che mi bastano i valori per una dimensione,
ossia
   0 1 2 3 4 5 6 7...
-------------------
0| 0 1 2 3 4 5 6 7 ..
1| 1
2| 2
3| 3
4| 4
5| 5
6| 6
7| 7
Per simmetria righe e colonne sono uguali, in piu' l'incrocio lo calcolo con
l'operazione Xor, es 7 Xor 1 = 6;
In piu' questo mi permettere di fondere n righe in una immediatamente v1 Xor
v2 Xor v3 etc.
Comunque e' proprio la stessa cosa.
Io ci ho provato e c'era disponibilita', forse sono stato fortunato (e non
ho colto l'occasione, mi ricordo $63 + spese).
Ciao
Andrea
