» »

[Delphi] štiri v vrsto (nasprotnik je računalnik)

[Delphi] štiri v vrsto (nasprotnik je računalnik)

«
1
2

kulSMS ::

V delphiju sem sprogramiral 4 v vrsto (nasprotnik je računalnik). Zanima me kako težavna se vam zdi igra (je možno računalnik premagat?)
Najprej preizkusite exe nato pa pride še koda.

Prenesi - 4 v vrsto

@LOL ::

Jaz sem ga na 6stopnji s prvo. 8 pa sem probal vendar se čaka na PC potezo ko debil tko da naprej nisem igral
je pa kul;)
Hippy: The Doors?
Geek: The Windows!

MeGreat ::

Na 8 sem ga v prvo premagal, mogoče malo predolgo računa :)
Drugače pa zanimivo hehe
PS. Ali nima štiri v vrsto 7vrst?

Zgodovina sprememb…

  • spremenilo: MeGreat ()

WarpedGone ::

Najpreh pohvale za velikost exeja. Dandanes so še virusi čez 1mb :)

Na nivoju 8 sm mu pustu direkt šanso zmage in jo je spregledal ter 'se pustu' premagat. Logika očitno še ne deluje ok.
Zbogom in hvala za vse ribe

steev ::

Treba dodelat logiko. Se od mene pohvale, da se nekaj takega spraviš delat. Na 8 sem ga zmagal na tisti način, ko mu ne preostane drugega, zato jo je vrgel v edino vrstico, kjer jo je lahko, in meni podaril zmago.
:|

kulSMS ::

nekaj vprašanj za vse:
@LOL in MeGreat: na kakšen način sta ga premagala (tako da ni imel druge možnosti?)

WarpedOne: "sm mu pustu direkt šanso zmage in jo je spregledal" kako je to izgledalo?
načeloma če ima možnost zmage oz preprečitve poraza v eni potezi to takoj naredi brez računanja

@LOL ::

@LOL in MeGreat: na kakšen način sta ga premagala (tako da ni imel druge možnosti?)

Da:))
Hippy: The Doors?
Geek: The Windows!

OwcA ::

Glede na oddelek, povej še kaj o algoritmih in izvedbi nasploh.
Otroška radovednost - gonilo napredka.

kulSMS ::

algoritem je približno takšen: MINIMAX algoritem (nekaj primesi ALFA BETA iskanja)
program izračuna vse poteze do Nivoja igre globoko (nivo 6: tri računalnikove poteze in tri igralčeve) če naleti na zmago oz poraz prej konča.
oceni vse končne situacije.
nato pa ocene prenaša navzgor do prve poteze.
če je v tem nivoju na potezi računalnik vzame najboljšo potezo, če je igralec najslabšo (s stališča igralca je to najboljša)

na koncu dobi ocene 6 potez in izbere najboljšo (oz. izbira naključno med nekaj najboljšimi --> ne moreš ga vedno premagat na isti trik)

MeGreat ::

Ahm, 2x na srečo, pač na koncu kolikor sem dajal in kdor je prej prišel do 4 v vrsto(res je, da je imel on 1x trojko jaz pa 2.)
enkrat pa tako da ni mel šanse
PS. Zakaj na začetku tko dolg računa zmer :D

l0g1t3ch ::

A lohk poveš kaj več o algoritmih oz kakšne link iz kje si črpu znanje.

Se mi sliš zanimiv pa bi še sam poskusu kaj tazga narest. Sam verjetno v Javi :D

kulSMS ::

MeGreat:
kaj ti ga je uspelo zmagat brez razveljavljanja?
na začetku računa zelo dolgo, ker ni bilo nobene poenostavitve (da bi prišel kje do 4 v vrsto, pa ocene so podobne itd...)
sedaj sem malo izboljšal da prvih 5 potez ne računa toliko ker itak nima smisla.
dodal sem en stolpec sedaj jih je 7 (sem pogledal malo po internetu pa jih res imajo 7)
pa še velikost exe-ja sem zmanjšal za cca 60%

l0g1t3ch:
poglej na google: Algoritem Minimax imaš dosti materiala tudi v slovenščini

Prenesi - 4 v vrsto

jan01 ::

oprosti, a računalnik nima za burek...
Sem imel od enga 4 v vrsto v cju(bom poiskal kodo). Če je računalnik začel, skoraj nisi mogel zmagati(še najbolje je bilo taktizirati, da bo računalnik bo prisiljen narediti napako....

MeGreat ::

Ja seveda brez razveljavljenja, ti bom poslal par screenov. :)
to je iz v2 http://shrani.si/?screenshotpx0r.jpg
ta je pa iz v3, težavnost več kot 7 ne dovoli http://shrani.si/?screenshotpx13.jpg
Hmm, mogoče težavnost je še kar če na hitro špilaš, če pa malo razmišljaš pa hitro spuši

Zgodovina sprememb…

  • spremenilo: MeGreat ()

kulSMS ::

Sem malo več igral pa sem res videl da ne igra ravno najbolje. Mislim da sem malo pretiraval z naključnimi potezami (to sem dodal da ne bi izgubil vedno na isti način, potem je pa vseeno igubil na drugačen način:D pa ravno to sem dodal tik preden sem poslal prvo verzijo).
Mislim da je NOVA verzija 4 boljša od v3 in v2 (v medsebojnem tekmovanju je bila)

Sergio ::

kulSMS: Naključne poteze izbiraj tako, da randomiziras najboljse, in se odlocis med njimi.

Ne pa kar na slepo nekaj ugibat ;-).
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

kulSMS ::

saj nisem na slepo ugibal, vendar je bila meja verjetno prenizka

MeGreat ::

jah, da na začetku neki ob strani nalaga je res mimo

kulSMS ::

na začetku so ocene dosti podobne in zato se je zaradi prenizke meje skoraj naključno odločil v kateri stolpec bo dal.

Thomas ::

Ja, odlično. Odlično.

Samo mora pa IMO takle program biti nepremagljiv. Mora poznati optimalno strategijo, če ne, ni dovolj dober. Vse kar je manj, zahteva izboljšanje.
Man muss immer generalisieren - Carl Jacobi

kulSMS ::

Kako sedaj kaj deluje (v4)?
Zanima me predvsem mnenje tistih, ki so ga na začetku zlahka premagovali, če ga da še zmeraj?

dr. Zgemba ::

Kakih 15-18 let nazaj je imel Moj Mikro tekmovanje teh 4 v vrsto programov.

Drugače pa recimo tale program igra optimalno. Če ima prvo potezo zmaga, drugače izsili neodločeno.

Thomas ::

Kar za to igro ni optimalen program, je samo vaja. More vlečt, kot se zagre.

Sicer je samo ena vaja. Koristna, vseeno, jasno.
Man muss immer generalisieren - Carl Jacobi

MeGreat ::

in kje je v4?

kulSMS ::

v4 je na istem linku (zamenjan v3)

Pa res tale Mustrum igra boljše od mojega.
dr. Zgemba pravi:
Drugače pa recimo tale program igra optimalno. Če ima prvo potezo zmaga, drugače izsili neodločeno.

to ni res (ni logično)--> če ima prvo potezo zmaga to je v redu,
sicer izsili neodločeno pa ni v redu (če tekmujeta dva enaka programa med seboj bo tisti, ki bo prvi začel zmagal drugi pa izgubil in ne igral najmanj neodločeno ---preverjeno:D )

sklep: če je res da ta program (oz katerikoli drugi) zmaga vedno ko ima prvo potezo, potem programa ki v nobenem primeru ne bo igubil ni možno narediti (se morda motim)

Zgodovina sprememb…

  • spremenil: kulSMS ()

dr. Zgemba ::

Sklep je pravilen, napisal sem malo prehitro.
Če prvi začne v kateri koli koloni razen sredinski, potem drugi z optimalno igro vedno izsili vsaj neodločeno. Torej, z optimalno igro zmaga prvi igralec.

Tule je še nekaj teorije in izpeljave/razlage.

Thomas ::

Jaz si teorije te igre predstavljam tako, da z grobo silo raziščeš vse možne partije.

Mislim, da je doable.
Man muss immer generalisieren - Carl Jacobi

jernejl ::

S samo brute-force metodo traja predolgo.

Potrebno je pametno implementirati alfa-beta, in si dobro zastaviti ocenjevalno funkcijo položajev. Bolj obetavne položaje lahko raziskuješ v večjo globino, manj obetavne pa pustiš.
Priporočam, da si izgradiš še tabelo otvoritev (če je še nimaš). Tako delujejo tudi programi za igranje šaha.
Znano namreč je, da se idealna igra začne tako, da vržeš obroček v srednji stolpec (d).

Thomas ::

Šah je šah. Tole gre pa bruta forca bez po muke. Na PCu.

Trust me.
Man muss immer generalisieren - Carl Jacobi

@LOL ::

Dvomim da boš kaj naredil z bruteforcem v doglednem času. Ker že če se čaka na računalniško potezo več kot kaka sekunda (ali par) je zame neuporabno.
Hippy: The Doors?
Geek: The Windows!

Thomas ::

Ah ne, jaz bi vse izračunal vnaprej. Zato bi morda šli tedni. Ampak program bi se potem izvajal ko strela. Ko sneta skira!
Man muss immer generalisieren - Carl Jacobi

@LOL ::

hehe tudi to je varjanta:D
Hippy: The Doors?
Geek: The Windows!

Irbis ::

> Kakih 15-18 let nazaj je imel Moj Mikro tekmovanje teh 4 v vrsto programov.

Spomnim se, da so imeli tekmovanje v križcih-krožcih na polju 21x21, ko jih je bilo treba dobiti 5 v vrsto.

jernejl ::

Zaenkrat smo še predaleč, da bi se lahko igrali z brute-force on the fly. Samo preštej, koliko je različnih iger. Ja, šlo bi, če bi vnaprej izračunal z brute force, pa še tukaj bi se moral precej potrudit z dobrim in hitrim algoritmom. Pa bi verjetno kar nekaj tednov čakal.

Če greš gradit drevo iger - sedmiško drevo, je v grobem treba iti do globine 42 (toliko je polj v igri 7x6).
Povej mi še, kam bi si potem to vse shranil?

Kompromis, ki sem ga že predlagal: kje na netu poiščeš seznam otvoritev, ali pa res pustiš nekaj dni računanja računalniku z veliko globino igranja, da ti vrže ven dotlej najboljše začetne poteze in potem poskusiš s tistimi.

@LOL ::

Zanimiva bi bila kvečjemu igra dveh računal ki bi preračunavala v real-time in bi bil čas omejen. Tam bi se že videlo kateri algoritem je boljši.
Hippy: The Doors?
Geek: The Windows!

Backup22 ::

Jep, to bi pokazalo kateri algoritem je hitrejši. Ni treba it do konca... Važno je samo kateri algoritem najde neko optimalno (zadovoljivo) rešitev v določem času. Boljši algitem pa najde v nekem časovnem intervalu bolj optimalno rešitev.
Huh sedmiško drevo globine 42...>:D
//

Thomas ::

Ni tako hudo, kot zgleda na prvi pogled. Res ne. Bom utemeljil ponoči ali jutri enkrat. Walk in the park, so to speak.
Man muss immer generalisieren - Carl Jacobi

dr. Zgemba ::

>Spomnim se, da so imeli tekmovanje v križcih-krožcih na polju 21x21, ko jih je bilo treba dobiti 5 v vrsto.

Eh, ja, no, blizu pa sem vseeno bil :D

Ampak tale brute force me pa res zanima. Pa ni mišljeno kot provokacija, čisto zares me zanima. Predvsem kako oklestit množico možnih stanj.

Brane2 ::

Pa se ne bi dalo kje na ST prirediti računalniški turnir ?

Lahko bi se dogovorili za pravila in format izmenjave podatkov.

Nato bi za vsako tekmo odprli novo temo kjer recimo v loži ali kaj podobnega z naslcovom recimo:

Krogci: Blue Dragon vs Tai Pan [2327]

besedilo vsakega sporočila bi bilo v domenjenem formatu.

Recimo

(številka poteze)-(Igralec)-koda poteze-

in

(številka poteze)-(Igralec)-potrditev sprejete prejšnje poteze nasprotnika

Tako zmagovalec kot poraženec bi prijavila rezultat v posebni temi in poseben arbiter bi vzdrževal stanje prvenstva, lestvico tekmovalcev z rezultati in vabil pare tekmovalcev v nadaljnje bitke.
On the journey of life, I chose the psycho path.

steev ::

Dobra ideja. Samo jaz bi dal omejen čas pri igranju teh 4 v vrsto. Ker to preko foruma se lahko igra cel teden, razen če ja res kak uber težka igra (križci-krožci na 100*100 polju).
:|

@LOL ::

Seveda omejen čas če ne ne bi bilo zanimivo
Hippy: The Doors?
Geek: The Windows!

Thomas ::

No, vas bom opremil z bruta forca teorijo, za na turnir.

Torej, najprej nas sploh ne zanimajo vse partije, ampak samo vse pozicije. Teh je manj kot 2^42 (slabih 10 bilijonov), right?

Pravzaprav jih je celo manj, ker je večina ilegalnih. So se partije morale ustaviti že prej, ker je nekdo zmagal.

Če smo tukaj enotni, gremo lahko naprej. Smo?
Man muss immer generalisieren - Carl Jacobi

kulSMS ::

ti misliš samo končne pozicije
vseh je manj kot 3^42 (rdeči modri prazno) se motim?

Thomas ::

Aha, se že ne strinjamo.

Manj kot 2^42 jih je, možnih pozicij.
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Prazno polje ne more biti kjerkoli. Lahko je samo NAD vsemi modrimi in rdečimi v tistem stolpcu. Right?
Man muss immer generalisieren - Carl Jacobi

Brane2 ::

Ne štekam zakaj ravno 2^42. A je "igrišče" omejeno ?
On the journey of life, I chose the psycho path.

Brane2 ::

Ah. Sem ravnokar poškili pod menu "igre" v Gnomeu in tam našev "Four in a row". Vidi, vidi. 6x7 polj, dva igralca, metanje kuglic na stack.

Sem mislil, da gre bolj za igro tipa križci in krogci, kot smo jo poznali v starih časih šolskega dolgčasa med navijanji prfoxa in karisrastega papirja... :8)
On the journey of life, I chose the psycho path.

Zgodovina sprememb…

  • spremenil: Brane2 ()

WarpedGone ::

Misliš varianto "neomejenega" polja, kjer se je začelo iz sredine karirastega papirja in doštukovalo liste?:)
V tej varianti vnaprejšnji izračun lepo odpade, ker gre kompleksnost BF metode skozi strop. Tut še nism vidu programa, ki bi špilal to. Pozna kdo?
Zbogom in hvala za vse ribe

sverde21 ::

Optimiziran BF algoritm ti stisne skoz cevovod procesorja tud po 10-20 miljonov (ali še več) različnih kombinacij pri sedanjih računalnikih, tak da real-time bruteforcing je kr realnost... število možnosti se ustrezno zmanjša, ko izničiš neveljavne poteze...
<?php echo `w`; ?>

kulSMS ::

Prazno polje ne more biti kjerkoli. Lahko je samo NAD vsemi modrimi in rdečimi v tistem stolpcu. Right?


Tudi modro in rdeče ne more biti kjerkoli, samo pod vsemi belimi
«
1
2


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Šahovski problem - mat v dveh potezah (strani: 1 2 3 4 )

Oddelek: Znanost in tehnologija
19119380 (7823) msjr
»

V šahu čedalje več remijev, prednost belega pa ostaja (strani: 1 2 )

Oddelek: Novice / Znanost in tehnologija
7225712 (18647) Jst
»

2 perfektna igralca šaha kdo zmaga (strani: 1 2 3 4 5 )

Oddelek: Znanost in tehnologija
20613281 (10419) GregiB
»

Človek proti Umetni inteligenci (strani: 1 2 3 4 )

Oddelek: Novice / Ostale najave
17214695 (11232) Roadkill
»

Kako igrate štiri v vrsto?

Oddelek: Znanost in tehnologija
383374 (2861) snow

Več podobnih tem