Newsgroup: it.comp.lang.c++
Titolo: Codice FORZA4, si trova??

chi di voi sa dove possa trovare il codice c++ del noto gioco "FORZA 4"?
grazie

 chi di voi sa dove possa trovare il codice c++ del noto gioco "FORZA 4"?
Io ne ho fatto uno per windows.
Il codice non e' nulla di speciale se non un algoritmo minimax (alpha beta
pruning, negamax,etc.. sono tutte ottimizzazioni del minimax stesso).
Guardati il minimax ed in pratica e' questo che vuoi.
Affinche' sia piu' forte (calcoli piu' in profondita') devi poi guardarti
iterative deepening, most probable path, hashing, openings etc...
Voglio essere onesto: farne uno che sia forte come alcuni che sono in giro
e' davvero dura.... Farne uno che funzioni e che batta spesso un giocatore
medio e' facile. Gia' con minimax con alpha beta cut off (alpha beta
pruning) il gioco funziona bene e ..... sono davvero poche righe di
codice!!!
Se hai problemi con il minimax ti aiuto... ma e' semplice.
Oltre a questa funzione (minimax) te ne servono altre due: GameOver() che
guarda se si verifica o meno un game over e Evaluate che da una stime della
"bonta'" di una certa configurazione di gioco (in quanto all''inizio del
gioco il PC non sara' in grado di "finire" tutta la cascata ricorsiva del
minimax, allora dopo tot secondi (o livelli) stoppi e valuti invece).
Se vuoi fare pratica con il minimax, scrivi un tris (tic tac toe) prima, il
principio e' lo stesso. Quando la funzione ti va, con qualche minima
modifica la puoi usare anche nel forza 4! (in questo modo sai se funziona o
meno prima di doverla testare su di un gioco piu' complicato).
Non so che altro dirti. Io mi sono divertito parecchio e mi ha preso anche
parecchio tempo.... Spero tu ti diverta!
Tommy

 wrote
Dimenticavo... Quando il gioco era gia' fatto volevo renderlo piu' forte ed
ho deciso (cosa che mi ero promesso di non fare prima perche' chissa quale
motivo) di guardare sorgenti di altri programmi....
Di forza4 non trovi molto.... ho trovato qualche vecchia roba in C che non
ho nemmeno poi guardato.
Alla fine molto del materiale che ho usato l'ho preso da documentazioni di
programmi di scacchi (stesso principio, ma molto piu' complicato). Ora il
mio programma e' forte, ma ci sono altri programmi che lo battono.... sigh!
(magari un giorno mi ci metto davvero sotto. Ero arrivato a buon punto, poi
mi sono stancato... era gia' troppo tempo che ci stavo dietro!)
Tommy

 grazie
Tor Vergata, Fondamenti di Inf. 1, prof. Italiano? ;-)

 Tor Vergata, Fondamenti di Inf. 1, prof. Italiano? ;-)
Beh, se e' un progetto per il primo anno non e' male... Dopo soli 6 mesi di
uni e programmazione mi pare un progetto interessante.
Un semplice minimax con alpha beta ed una funzione "semplicistica" di
valutazione lo rendono semplice da implementare. Diventa difficile quando si
vuole andare oltre... Avete per caso le specifiche del programma, sara'
anche un pochino OT magari, ma sono curioso a questo punto!
Tommy

Tommy ha scritto:

Che strategia hai usato? Io ho fatto un gioco di tris, piuttosto simile,
col campo di dimensioni configurabili, e avevo usato la MinMax. I
sorgenti sono free?
-- 
Andrea Bergia - studente              Linux Registred User #281550
"The one thing we're all waiting for, is peace on Earth and an end to
war,
it's a miracle we need, the miracle, the miracle, 
Peace on earth and end to war today,
That time will come one day you'll see when we can all be friends"

 I sorgenti sono free?
Scusa se rispondo cosi' ma il mio server BT non mi ha scaricato il tuo
messaggio e l'ho incontrato invece su google ;-)
Ho usato un algoritmo inventato da me, una via di mezzo tra alpha-beta
pruning e negamax.
Poi ho usato l'iterative deepening (ogni volta provo con una profondita'
maggiore, quando finisce il tempo stacco ed uso l'ultima conclusa). Ogni
iterazione incomincia con la mossa migliore dell'iterazione precedente
(questo migliore l'alpha beta cuttoff).
Poi invece di valutare ogni volta che blocco la cascata ricorsiva con una
funzione Evaluate che controlla l'intera board (lenta), cerco di tenere
aggiornata in modo approssimativo una statistica ad ogni mossa. Quando
voglio Evaluate() esco semplicemente ed uso le statistiche. (per come ho
codificato io in questo modo e' un tantino piu' veloce).
Ho provato di usare Transposition Tables, ma con scarso successo.... e' qui
che mi sono piantato. L'Opening Books e' molto limitato, per le prime 3
mosse e nemmeno completo. Mi ero promesso di fare un algoritmo che finisse
il gioco (dandogli tempo) e compilasse le opening migliori per le prime5
mosse almeno....poi non ho mai fatto.
Non ho mai voluto cambiare il mio algoritmo personale con MTD(f), questo e'
meglio del mio negamax, ma il mio me lo sento mio, quindi..... non sono
nemmeno sicuro di quanto sia migliore. So che e' piu' difficile da
codificare in modo efficiente, ma quando uno ci riesce dovrebbe essere
buono!
Esistono tante altre tecniche avanzate che arrivano dagli scacchi, io non le
ho utilizzate ancora. Posso dirti che molto sta in una buona funzione (o
meccanismo) di valutazione. Non importa arrivare in un secondo a profondita'
14 o 16, sbagliavo quando pensavo facesse una enorme differenza, non e'
vero! 16 con una valutazione fatta male, le prende da un 8 con una
valutazione fatta un anche solo un tantino meglio.
Ho inoltre usato varie tecniche che ho scoperto nel programmare. L'errore
l'ho fatto quando mi sono messo a migliorare la veste grafica, a fare il
supporto network, varie skins etc... alla fine non ho avuto piu' voglia di
rimettermi sotto con il cuore del programma. Credo che prima o poi lo
faro'... Ho in mente gia' un paio di programmi da battere!
I sorgenti non sono free, potrei anche farlo, ma non credo gioverebbero
molto a nessuno. Conviene guardare implementazioni (molto migliori della
mia) di dama (checkers), scacchi (chess) etc...
Il principio e' quello del tris che hai fatto tu! Qualche differenza:
- devi pensare alla velocita' in quanto ogni PC finisce il tris in
pochissimo tempo, non e' lo stesso per il F4!
- devi introdurre la valutazione, ovvero all'inizio del gioco, quando non
puoi finire il gioco (finire la cascata ricorsiva), devi interrompere dopo
un tot di tempo. Non avrai quindi dati veri, ma approssimativi, una stima!
(valutazione)
- se parti con profondita' max (per finire il gioco) e poi stoppi dopo tot
secondi, hai controllato 0,1 (o su pc veloci di piu') delle possibili mosse,
e magari la migliore era la 7a! Devi quindi introdurre l'iterative
deepening. La prima volta vai a profondita' 8 (ad esempio) e la finisci, poi
9, poi 10, poi 11 poi 12 la stoppi (sono passsati i 2 secondi) quando ha
provato solo 3 mosse, quindi utilizzi i risultati NON parziali di
profondita' 11 (e scarti quelli di 12).
- forza4 non puo' mettere le pedine ovunque (vanno per caduta dall'alto)
qundi anche nel minimax devi solo provare le mosse valide (che sono al
massimo la larghezza della base, o meno se qualche colonne e' finita). In
pratica il tuo "campo delle dimensioni configurabile" ti aiuta, ma devi
cambiare questa parte, non devi mettere in tutte le posizioni libere, ma
solo in quelle che si appoggiano sulla base o su altre pedine.
- devi connettere 4 (questo pare ovvio).
Non mi viene in mente altro.... Sono sicuro ci sia molto altro da dire e
sono sicuro di averci messo molte piu' cose di quante dette nel mio
programma, ma.... e' passato del tempo e questo e' cio che mi e' rimasto in
mente!
Tommy
l...@libero.it

 rimasto in mente!
Grazie comunque della risposta. PS: se hai un PC con KDE 3.x puoi
scaricare e provare a compilare il gioco. Il sito è
http://kextragames.sf.net
. E scusate per lo spam ;-)


 
http://kextragames.sf.net
. E scusate per lo spam ;-)
Si, oramai uso poco linux, ma non lo tengo sempre (e come si fa a
disinstallarlo, mi piace troppo ;-)
Appena ho tempo faro' come dici, son curioso di provare e guardare la tua
implementazione.
Se vuoi guardare l'ultima versione stabile (ma non priva di bugs) del mio
programma: 
http://www.lantaka.it/tommy/tommy4.html
 (messa sul sito di un
amico (su gentile concessione) per l'occasione)
Non e' di sicuro imbattibile. Nota che questa versione e' priva di aperture
e pure di hashing pero'!
Tommy