Tre pedine

[axpgn]

Si abbia una striscia orizzontale di $8$ caselle, numerate da $0$ a $7$ da sinistra a destra.
Vi siano tre pedine posizionate sulle caselle $3-5-7$.
I giocatori sono due e l'unica mossa che, a turno, possono fare è lo spostamento di una sola pedina nella casella che preferiscono, anche se occupata da una o due pedine, purché sia a sinistra della casella di partenza.
Il vincitore è colui che pone l'ultima pedina nella casella $0$.

Chi vince? E come fa?

Cordialmente, Alex

[orsoulx]

"Bolle":Vedo che iniziano a trapelare i pari e dispari...

Se leggessi con più attenzione, potresti anche capire che non si parla di pari/dispari per la posizione di una pedina, ma bensì di 'dispari' per la somma di una colonna. In questa discussione il termine "pari" compare la prima volta nello spoiler incriminato che, secondo te, sarebbe stato modificato per indurti ad osservazioni errate.
Ora a programmare, visto che da vent'anni non lo faccio più, sono un'autentica scarpa e non mi metto certo a scrivere un programma per giocare a Nim, l'ultima volta che l'ho fatto era in Assembly per uno Zilog Z80. Altre stagioni!
Posso però indicarti, in italiano, come far diventare intelligente un computer che sappia già giocare in maniera stupida.
Supponendo che la posizione delle $ n $ ( 3 è un caso veramente misero) pedine sia conservata in un vettore di interi, bastano le seguenti operazioni:

1) eseguire lo $ XOR $ di tutte le posizioni, chiamiamolo $ s $
2) se $ s=0 $ il computer non può vincere (a meno che l'avversario sbagli) ed allora muove a caso, altrimenti...
3) scorrere tutte le posizioni fino a quando se ne trova una (esiste sicuramente), chiamiamola $ p $, in cui $ (p XOR s) < p $. Quella pedina deve esser mossa da $ p $ a $ p XOR s $ .

Secondo te, che scrivi come niente 600 righe di codice, quante istruzioni servono?
Ti ricordo ancora il tuo impegno

"Bolle":Io non scomodo la notazione binaria...me la gioco a pari e dispari, parlando un linguaggio comprensibile a tutti!

Quando vorrai, come dici tu, ablare (sic), leggeremo.

[Bolle1]

"orsoulx": Sul suo forum c'è scritto che la prima mossa è sorteggiata e c'è pure scritto che sarebbe stato schiaffeggiato (mi brucia ancora la mano). Dovresti provare a batterlo dopo avergli dato la possibilità di vincere.

Sinceramente non capisco perchè la stai prendendo a male...la frase che ho scritto (dall'altra parte) era dovuta alla mio errore iniziale...ed in effetti mi sono sentito ( anche giustamente ) schiaffeggiato per aver sbagliato e tu mi hai 'corretto' con una frase che successivamente hai levato trasformandola nella spiegazione del gioco del Nim senza lasciare traccia alcuna...ma evidentemente sono un visionario o no?
Trasformando quella frase riporti uno scritto che perde senso e cmq l'essere schiaffeggiato non è una critica mentre per il resto c'è da sbizzarrirsi ma non vorrei che qualcuno la prendi a male, sto scrivendo un mio punto di vista!
Dire o asserire delle cose in modo criptico e sibillino per poi vantarsi e dare del disattendo all'interlocutore...che senso ha?
Sembra che stai molto più concentrato nel 'cazziarmi' o trovarmi errori che ad altro...ma sto sicuramente interpretando male le cose che scrivi e quindi mi scuso anticipatamente!

Ora si che che hai dato una spiegazione, la sto analizzando...perdonami ma sono lento in queste cose...ma ho una domanda da porti:pensi veramente che quella sia l'unica 'soluzione'?
Un Saluto
B.

[Bolle1]

Ora si che che hai dato una spiegazione, la sto analizzando...

Azz...mette paura...

[axpgn]

La mia fonte (quella che contava fino a $88$ ma con le sue regole non ho passato il $53$ ... ) parla anche del Nim e dice che la teoria matematica di questo gioco è stata ampiamente spiegata da C.L.Bouton (vedi Annals of Mathematics, 1902, series 2, vol. III, pp. 35-39) ed è quella spiegata da orsoulx.
In matematica esistono spesso molte strade per arrivare a meta, quindi io non escludo che la tua sia corretta però mi piacerebbe sapere esattamente qual è ...

Sempre la mia fonte accenna ad una variante del Nim che chiama $text(Moore's Nim)_k$ nella quale è possibile rimuovere i "fiammiferi" (pedine, gettoni, pezzi, quello che è ...) da più "mucchietti", fino a $k$.
Un po' più complicata ...

Cordialmente, Alex

[orsoulx]

"Bolle":ma ho una domanda da porti:pensi veramente che quella sia l'unica 'soluzione'?

Assolutamente no, e non credo di averlo mai lasciato intendere. Quando ero adolescente mi son pure beccato un sette di condotta, perché giocavo a "L'anno scorso a Marienbad" con un mio compagno disegnando, col gesso, i fiammiferi sul bancone dell'officina. Non sapevo neppure si chiamasse Nim e che potesse esser giocato con la strategia proposta. Conoscevo però tutte le posizioni vincenti, in fin dei conti, a parte quelle banali con coppie di file della medesima lunghezza (pedine sovrapposte) oppure con variazioni unitarie rispetto alla posizione iniziale (1, 3, 5, 7), sono solo 6.
Alex ha detto di averne un'altra ed anche tu ne hai una segreta.
Mi meraviglierebbe, invece, ma ne sarei molto contento se ce ne fosse una più semplice.

Lasciamo perdere la querelle sui reciproci maltrattamenti, tanto rimarremmo ognuno convinto delle colpe altrui. Quando sarai più sereno, prova a rileggere la discussione e se hai qualche rimostranza da fare mandami un MP.

"Bolle":Dire o asserire delle cose in modo criptico e sibillino per poi vantarsi e dare del disattendo all'interlocutore...che senso ha?

Qui se ho ben capito si parla invece di matematica. Ti riporto quanto ho scritto il 16/3 alle 17:28 e oggi alle 15:09:

Scritte, in base 2, le posizioni occupate dalle pedine, si incolonnano allineando, normalmente, a destra. Se il numero di 1 presenti in ciascuna colonna è pari la posizione è vincente (nel senso che chi è costretto a muovere non può che alterare la parità di una o più colonne). Chi si trova, invece, a muovere da una posizione con una o più colonne aventi somma dispari, ha sempre almeno una mossa che gli permette di farle diventare tutte pari; come è pari la somma di ciascuna colonna quando tutte le pedine sono arrivate nella posizione 0.

1) eseguire lo $ XOR $ di tutte le posizioni, chiamiamolo $ s $
2) se $ s=0 $ il computer non può vincere (a meno che l'avversario sbagli) ed allora muove a caso, altrimenti...
3) scorrere tutte le posizioni fino a quando se ne trova una (esiste sicuramente), chiamiamola $ p $, in cui $ (pXORs)

Non vedo, dal punto di vista matematico, alcuna differenza: la prima è la dimostrazione dell'esattezza della seconda. Però la prima non ti andava bene e la seconda la stai analizzando, e non capisco cosa voglia dire.
Ciao
B.

Cita

Segnala

[orsoulx]

@Bolle
mi son dimenticato di segnalarti che l'algoritmo proposto è ancora migliorabile: ad esempio lo XOR del passo (1) è facilmente sostituibile con qualcosa di molto più leggero (specialmente quando si gioca con tante pedine).
Ciao
B.

[Bolle1]

"axpgn":In matematica esistono spesso molte strade per arrivare a meta, quindi io non escludo che la tua sia corretta però mi piacerebbe sapere esattamente qual è ...

Ho messo in piedi 4 semplici regole...ma datemi ancora del tempo...ho paura di essere schiaffeggiato ancora ...mi permetto di scherzare perchè vedo che abbiamo preso una piega molto più consona!

La mia fonte (quella che contava fino a 8888 ma con le sue regole non ho passato il 5353 ...

Ti ringrazio, ho scaricato un testo (Mathematical Recreations and Essays)...grazie per il suggerimento mi hai illuminato su tutta la questione...sto studiando le varie implicazioni

Mi meraviglierebbe, invece, ma ne sarei molto contento se ce ne fosse una più semplice.

Non penso...la sto elaborando da un giorno, nei ritagli di tempo...programma SW incluso!

Qui se ho ben capito si parla invece di matematica.

Mica penserai che io venga dalla montagna del sapone... ho frequentato il Guido Castelnuovo per farci qualche esame e dopo qualche anno per farci qualche lezione...poi dopo sono scappato perchè mi erano venuti gli occhi a forma di dollaro!

Una critica ti faccio, poi chiudo la questione dell'alterazione della tua risposta in assenza di modifica....ma no...spero solo di essermi sbagliato...forse era tardi ed ho letto male!

[orsoulx]

"Bolle": Qui se ho ben capito si parla invece di matematica.


Mica penserai che io venga dalla montagna del sapone... ho frequentato il Guido Castelnuovo per farci qualche esame e dopo qualche anno per farci qualche lezione...poi dopo sono scappato perchè mi erano venuti gli occhi a forma di dollaro!

???
Ciao
B.

[Bolle1]

Rispondo oggi ...altrimenti avrei risposto lunedì.

Si vince se si rispettano queste 4 regolette:

1. Se la prima pedina è in posizione zero, posizionare la terza pedina sopra la seconda (d'altra parte evitare di mettere due (o anche tre) pedine una sull'altra altrimenti l'avversario mette l'altra pedina in posizione zero.Questa è anche la mossa di vincita finale!)

2. Tentare di conquistare con le pedine la posizione di 1 2 3 ( d'altra parte evitare di lasciare una configurazione dove con una mossa l'avversario conquisti questa posizione)

3. Tentare di conquistare con la pedina centrale, la posizione 4 mantenendo la somma delle distanze dalle altre pedine guale a due ( d'altra parte evitare di lasciare una configurazione dove con una mossa l'avversario conquisti questa posizione.

Questa è l'immagine mnemonica...può essere utile da un punto di vista visivo!

)

4. Tentare di conquistare con la pedina centrale, la posizione 5 con le altre pedine la cui somma delle colonne è pari a 9 ( d'altra parte evitare di lasciare una configurazione dove con una mossa l'avversario conquisti questa posizione. Ex:2 5 7 --> dove 2+7=9)

[axpgn]

... mmmm ...

"Fare o non fare, non c'è tentare ..." (semicit.) ...

Cordialmente, Alex

[Bolle1]

Errata corrige :"Tentare di conquistare con le " in "Muovere, se possibile,"

Ciappa!

[axpgn]

"Muovere se possibile" l'è istess de prima ...

Mi pare che tu non abbia colto il significato profondo della mia battuta (va beh, si fa per dire ... )
A questo gioco (e più precisamente al Nim) esiste un strategia CERTA per vincere (non possibile ma certa): chi si trova davanti una situazione "dispari" (nel senso già esplicitato precedentemente) vince SEMPRE. Chiaro?
Una strategia alternativa DEVE essere altrettanto certa, altrimenti non é un'alternativa ...

Cordialmente, Alex

[Bolle1]

Infatti, al gioco delle tre pedine se si seguono quelle quattro regolette, comprensibili da chiunque,si vince!
Il quesito della domanda iniziale era quello e penso di aver risposto...a meno che non trovi una situazione che non contemplata dalle regolette!
Dimenticavo, quale l'altra tua soluzione segreta?
Cordialmente
Bolle

[orsoulx]

"Bolle":Mica penserai che io venga dalla montagna del sapone... ho frequentato il Guido Castelnuovo per farci qualche esame e dopo qualche anno per farci qualche lezione...poi dopo sono scappato perchè mi erano venuti gli occhi a forma di dollaro!

Quando hai tempo mi traduci quello che hai scritto?
Ciao
B.

[axpgn]

"Bolle":... comprensibili da chiunque ...

Da me, no ...

Mi ripeto, le frasi "tentare di conquistare" o "muovere se possibile" secondo me sono ambigue, per esempio non si specifica cosa si deve fare nel caso in cui non sia possibile fare ciò (quantomeno a me non è chiaro ...) oppure come ci deve muovere per conquistare la posizione $123$ (peraltro una posizione perdente e quindi con "conquistare" cosa intendi? lasciarla all'avversario o farsela lasciare?) ... IMHO non è chiaro ...

Non ho nessuna strategia segreta (né l'ho mai affermato), semplicemente, come detto, ho usato un'altra strada che è consistita nell'analizzare le posizioni, trovandone alcune di base (buone per chi muove come $00n, 0xy, text(nnn), text(xnn)$ o cattive come $000, text(0nn), 123$) dalle quali giocare è più facile (perché la "dimensione" del gioco permetteva una tattica del genere ...)

Cordialmente, Alex

[Bolle1]

"orsoulx":
Quando hai tempo mi traduci quello che hai scritto?

Mica penserai che io venga dalla montagna del sapone equivale a dire che non sono uno sprovveduto, Il Guido Castelnuovo è l'edificio che ospita il dipartimento di matematica della Sapienza di Roma...il resto penso si capisca!

per esempio non si specifica cosa si deve fare nel caso in cui non sia possibile fare ciò (quantomeno a me non è chiaro ...)

Vanno rispettate le 4 regolette, altrimenti si muove come si vuole!

123 (peraltro una posizione perdente)

non mi sembra proprio, chi mette le pedine in quelle posizioni...non perde!

PS:Per domani (oggi non ho molto tempo) completo il gioco con le 4 regolette...posso mettere anche un flag per selezionare il calcolatore con cui giocare "4 Regolette" oppure "orsoulx" ... ( che aggiungo come autore...sempre se questo non crea problemi ) poi quasi quasi faccio in modo che si scontrino tra di loro...vediamo come si comportano!Inoltre se elimino le attese...li faccio giocare a ripetizione...una sorta di test forza bruta per testare l'algoritmo...spero che sappiate a cosa mi riferisca!
Un saluto

[orsoulx]

@Bolle:
quella della montagna del sapone, andrò a cercare in rete da dove salta fuori. Per il resto avevo capito che avevi studiato e insegnato in una scuola (non pensavo proprio alla Sapienza), ma non capivo se te ne eri andato, perché ti pagavano poco o perché l'ambiente era di gente ricca con la puzza sotto il naso.
Comunque, per quel poco che può valere il mio parere, hai fatto bene: l'ambiente accademico, da quello che mi dicono mio figlio, che ci lavora, ed i miei tanti quasi figli (ex allievi) che ci provano, non mi piace proprio.
OK. Avevi capito tutto e ti divertivi a provocarmi con tanti: non condivido, non ci credo,... fino al mitico "Dire o asserire delle cose in modo criptico e sibillino per poi vantarsi e dare del disattendo all'interlocutore...che senso ha?". Come queste cose possano piacerti farà parte del tuo modo di rapportarti con gli altri. Io mi chiamo fuori.

L'algoritmo con le "quattro regolette" che proponi, a mio avviso, funziona perfettamente: coincide con quello che utilizzavo quando frequentavo la scuola dell'obbligo. Si può migliorare: tutte quelle parentesi, con "d'altra parte...", non aggiungono nulla, appesantiscono solo il discorso. Non ci vedo, però traccia del "...me la gioco a pari e dispari...": contiene il lemma "pari", ma nel significato di "uguale".
Se sia più semplice quella strategia rispetto a quella che ho proposto è un'opinione, e in quanto tale incontestabile.
Come ti ho già detto, da almeno vent'anni programmare non mi diverte più, preferisco giocare con i problemini stupidi. Sicuramente i due SW che hai prodotto, se non ci sono errori nell'implementazione, vinceranno o perderanno a seconda di quale dei due inizia e dalla posizione di partenza. Evita di citare il mio nick, come ti ha detto Alex, quella strategia è nota almeno dall'inizio del secolo scorso, l'unico merito che posso avere è quello di aver capito che il gioco con le pedine era uno dei tanti Nim possibili. Esiste, secondo quel che mi disse, un ex allievo un teorema che afferma (cito a memoria): qualunque gioco di questo tipo (alternanza con le medesime regole per i due giocatori) si può ricondurre ad uno o più Nim giocati in parallelo: ciascun giocatore sceglie su quale Nim eseguire la propria mossa e vince chi completa l'ultimo superstite. Roba per me troppo complicata: volo mooolto più in basso.

"Bolle":...una sorta di test forza bruta per testare l'algoritmo...spero che sappiate a cosa mi riferisca!

Secondo me, facendoli giocare l'uno contro l'altro non testi gli algoritmi, la cui correttezza è dimostrata dalla logica, testi, al più, la loro implementazione.
Ciao
B.

[axpgn]

@Bolle
A me la tua strategia continua a rimanere poco chiara; dici che orsoulx è criptico ma tu non sei da meno ... sicuramente non passerei delle specifiche ad un programmatore in quel modo...

"Bolle":

123 (peraltro una posizione perdente)

non mi sembra proprio, chi mette le pedine in quelle posizioni...non perde!

Non mi sembra che tu abbia letto per intero il mio post precedente, nel quale ho scritto cosa intendo per posizione "buona" o "cattiva" ... ed è un esempio della poca chiarezza a cui mi riferisco ...

Cordialmente, Alex

[Bolle1]

A me la tua strategia continua a rimanere poco chiara; dici che orsoulx è criptico ma tu non sei da meno ...

Mi sono adeguato ...

sicuramente non passerei delle specifiche ad un programmatore in quel modo...

Sicuramente ... faccio tutto da solo!

"orsoulx":@Bolle:
quella della montagna del sapone, andrò a cercare in rete da dove salta fuori.

E' un detto romano: https://ilblogchenessunoleggera.wordpre ... el-sapone/

L'algoritmo con le "quattro regolette" che proponi, a mio avviso, funziona perfettamente:

Azz...allora ho la tua benedizione?

coincide con quello che utilizzavo quando frequentavo la scuola dell'obbligo.

Giuro che è farina del mio sacco...

con "d'altra parte...", non aggiungono nulla, appesantiscono solo il discorso.

Vero ma a me piace spiegare...o almeno dire due parole in più che una in meno!

Se sia più semplice quella strategia rispetto a quella che ho proposto è un'opinione, e in quanto tale incontestabile.

Possiamo verificarlo...secondo me la tua strategia non viene capita da molti...anzi da praticamente una percentuale molto ridotta di persone!

Sicuramente i due SW che hai prodotto

Ne ho fatto uno solo...domani ci rimetto le mani e faccio quello che ho detto!

Evita di citare il mio nick, come ti ha detto Alex, quella strategia è nota almeno dall'inizio del secolo scorso, l'unico merito che posso avere è quello di aver capito che il gioco con le pedine era uno dei tanti Nim possibili.

Nemmeno i ringraziamenti per aver suggerito la soluzione informatica?

qualunque gioco di questo tipo (alternanza con le medesime regole per i due giocatori) si può ricondurre ad uno o più Nim giocati in parallelo: ciascun giocatore sceglie su quale Nim eseguire la propria mossa e vince chi completa l'ultimo superstite.

Sto studiando ... queste cose , fino ad una settimana fa sconosciute, stanno ampliando la mia conoscenza!

Roba per me troppo complicata: volo mooolto più in basso.

Non ti credo!

Cordialmente
B.

[axpgn]

"Bolle":Nemmeno i ringraziamenti per aver suggerito la soluzione informatica?

A dir la verità, secondo me, "informaticamente" la soluzione più semplice (in questo caso) è fare due semplici elenchi di posizioni "buone" e posizioni "cattive" ...

"Bolle":Sto studiando ... queste cose , fino ad una settimana fa sconosciute, stanno ampliando la mia conoscenza!

Allora sei tu che dovresti ringraziare noi ...

Noto che commenti solo ciò che più ti garba (giustamente) ...

Cordialmente, Alex