Keresés

Részletes keresés

fekete akos Creative Commons License 2017.09.13 0 0 916

Befértem a 3x3-as részletek véletlenszerű azonosításával 0...3,6*10^11 tartományba, ami 42GB-os adatblokkokat jelent. Ez még mindig messze van a szekvenciális azonosítás <12GB-os blokkjaitól, de ezzel már lehet játszogatni. Kicsi trükkel 36GB is elég lehet... alakul. :)

Előzmény: fekete akos (915)
fekete akos Creative Commons License 2017.08.06 0 0 915

Próbáltam precíziós eljárást találni a 3x3-as cellák sorrendfüggetlen azonosítására.

Elvileg 37 biten már azonosítható lenne mind a 125 milliárd kirakható kombináció.

Egyelőre 90 bitről 44 bitre ( 764 * 47^4 * 7^4 ) sikerült közvetlenül konvertálni.

fekete akos Creative Commons License 2016.08.20 0 0 914

Sikerült még 6%-ot faragni a sebességen... :P

Illetve dolgozom egy eljáráson ami extrém memóriaigény nélkül teszi lehetővé az átjárást, akár 3x3-nál nagyobb méretű átfedések esetén is!

Előzmény: fekete akos (913)
fekete akos Creative Commons License 2016.06.26 0 0 913

Megvannak az első teszteredmények.

A legfontosabb, hogy működik az elképzelés!

 

Tehát legeneráltam az összes 3x3-as blokkot, amelyek részben (2x3 puzzle-nyi részen) fedik egymást.

Ezeket a brute force algoritmussal "jól körbepakoltam", hogy kiszűrjem azokat a triviális eseteket amelyek biztosan nem részei a megoldásnak.

Majd megvizsgáltam, hogy két szomszédos, egymást átfedő blokk összes lehetséges átfedése milyen eseteket enged/tilt kölcsönösen a két blokkban.

...és volt kieső! Igaz, hogy csak minimális ( 0,02% arányban ) és csak néhány blokknál, de volt!

 

Most szűröm a nagyobb blokkokat abból a 196-ból...

Ezek időigényesebbek, kb. 5 nap / blokk / gép.

Még pár hét, aztán nekieresztem a teljes táblának az új algoritmust. :)

Kíváncsi vagyok, hogy a "halálzónás" blokkokból sikerül-e akár egyetlen kombót is kiütni... :)

Előzmény: fekete akos (911)
fekete akos Creative Commons License 2016.05.16 0 0 912

A fenti ábra mutatja, hogy a tábla 3x3-as részeit hányféle módon lehet lefedni a jelenlegi adatok szerint.

fekete akos Creative Commons License 2016.05.06 0 0 911

Valamit elszámoltam... 128GiB -> 4,7%; 256GiB -> 2,5% lett az átlapolódás.

Kvázi-random modulációval több menetben 0,025^n*100[%] érhető el.

Kár, hogy 2-3 óra / kör / cella. 196 cella van, lehet csökkentem a számukat.

Előzmény: fekete akos (907)
fekete akos Creative Commons License 2016.04.29 0 0 910

Na igen, ha csak a BF teljesítményét nézzük, akkor értelmetlen beszélni az időről... :)

De már régóta nem a BF-en van a hangsúly...

Előzmény: pingvin (909)
pingvin Creative Commons License 2016.04.29 0 0 909

Szép eredmény! Akkor már csak kb 10646 év a teljes bejárás..:-)

fekete akos Creative Commons License 2016.04.28 0 0 908

Kicsit csiszoltam a BF magon: 31-36 órajel / lépés.

Kb. 100 millió lerakás másodpercenként szálanként.

Előzmény: fekete akos (907)
fekete akos Creative Commons License 2016.04.20 0 0 907

Megjegyzés jövőbeli magamnak:

Legközelebb akkor próbálkozom, ha lesz legalább 200GB RAM-om.

Oda már be tudok pakolni két 2^40 bites táblát némi trükközéssel (mROT transzfer vagy 256GB+).

Kb. 1000-szeres gyorsulás érhető el a táblák közti átjárásnál, de minimális kombó átlapolással számolni kell (0,1% alatt tartható 5x5C, 4x3MClue0 esetén is).

Előzmény: fekete akos (906)
fekete akos Creative Commons License 2016.04.03 0 0 906

Szia! Szinte már senki nem foglalkozik az EternityII-vel, még a legnagyobb fórum (Yahoo/Eternity_two) is régen kihalt. Az általam ír kód assemblyben készült és kb. ötven alkalommal írtam meg újra és újra. :) Ugyanis mikor az aktuális ötletről kiderült, hogy halott ügy, akkor kidobtam az egészet a kukába. Aztán mikor elég új ötlet gyűlt össze, akkor újraírtam, ugyanis kb. 20 sor a hot spot, az meg a fejemben van. Jelenleg már hónapok óta nem programoztam a témával kapcsolatban. Persze állandóan jönnek újabb és újabb ötletek, de azokról mindig kiderül még a tervezési fázisban, hogy nem elég hatékonyak. Egyébként szívesen segítek, de a "netről letölthető program" kategóriában nem tudok. Olyanokat sosem próbáltam.

Előzmény: kricsek (905)
kricsek Creative Commons License 2016.03.28 0 0 905

Sziasztok.

Én magam is foglalkoztam a problémával. Még 2010-ben írtam c-ben egy programot, ami backtrack nélkül brute force-olt viszonylag gyenge 35.000 másodpercenkénti próbálkozással. Középről indulva spirálba helyezte fel az elemeket, amíg tudta. Utána kezdte elölről. Kb 5 perc alatt 100 elemet tud így felrakni.

A kérdésem az lenne, hogy melyik a legjobb netről letölthető program, amit tudnék futtatni? Esetleg van még olyan project, ami számítógépek között elosztva dolgozik? (BOINC)

Fekete Ákos: a te megoldásod mennyire "open source"?

fekete akos Creative Commons License 2015.12.17 0 0 904

Találtam egy egyszerű módszert, amivel nagyságrendekkel csökkenthető a véletlen hozzáférésű memória (RAM) igény.

Előzmény: fekete akos (903)
fekete akos Creative Commons License 2015.07.15 0 0 903

Egy kis szemléltető ábra, hogy a két szomszédos szín (2*5 bit) helyetti két szomszédos puzzle+orientáció (2*10 bit) adatra való átállás milyen hatással volt a "sötét zónára".

Az első esetben kb. 115 MB adattal dolgozik a kereső, a másodikban 17GB.

Szerintem logikus a következő lépés, megpróbálkozok a két szomszédos négyes (2*40 bit) kombinációval.

Az adatokkal persze trükközni kell, de előzetes számítások alapján elegendő lehet 128GB RAM.

Előzmény: fekete akos (901)
fekete akos Creative Commons License 2015.07.05 0 0 902

M13-on az új RLW szűrővel is kiesett a 0294H és 03D3H páros.

Csak épp fényévekkel gyorsabban... 

0294H -> 149. puzzle 180°-os elforgatással

03D3H -> 212. puzzle 270°-os elforgatással

Előzmény: fekete akos (900)
fekete akos Creative Commons License 2015.06.13 0 0 901

Sikerült további 10%-kal növelni a lerakási sebességet. Ráadásul mindezt úgy értem el, hogy a soron következő pozícióba lerakható puzzle kiválasztása szigorúbb feltételekkel szűrt listából történik. Ez a feleslegesen bejárandó zsákutcák számát csökkenti, ami szintén sebességnövelő tényező. Megspóroltam az index tábla olvasást, cserébe 4GB memóriát esznek az adatok. Alakul... :D

fekete akos Creative Commons License 2015.03.15 0 0 900

Végre valami eredmény!

M13 cellában továbbra is lerakható mind a 191 puzzle, viszont 2 orientációt sikerült kiszűrni.

Az ábra szerint már csak 569 bejegyzés van ott az eddigi 571 helyett! :)

fekete akos Creative Commons License 2015.03.11 0 0 899

Szia!

 

Öröm látni, hogy még van valaki aki rajtam kívül is foglalkozik a témával. :)

A linken a megoldások nem valódiak, több egyforma elemet is tartalmaznak.

 

Szvsz. a 6x6-os táblán a 115 milliárd kombinációt a mostani algoritmusom kb. 1 óra alatt bejárná.

Legalábbis 4 éve 2 óra kellett hozzá és azóta még egy kicsit tudtam csiszolni rajta.

A sebességre lentebb lesz még célzás...

 

Jelenleg 1-1 bittel reprezentálom az adatokat és a back-track algoritmust csak a visszakonvertálásra használom.

A lényeg, hogy a bitmátrixból próbálom kiszűrni az adott helyekre nem lerakható kombinációkat.

 

A teljes táblát 3x3-as, 3x2-es és 2x3-as csoportokra osztottam fel, így kaptam egy 14x14-es, 14x15-ös és egy 15x14-es táblákat.

Az általad említett 895-ös hozzászólásban látszó képnek megfelelően így nézett ki 2015.02.27-én a 3x3-as tábla:

 

 

Ez a 895-ös hozzászólásban látható 1x1-es "kombinációkból" generált állapothoz képest a jelenlegi állapot kb. 15%-kal kevesebb bejegyzést tartalmaz ( ennyi bit lett már nullázva a mátrixban ). Érdekes módon, mikor visszaskálázom az adatokat 1x1-esre, tehát a "895"-ös elrendezésre, akkor még mindig ugyanott vagyok. :) Szeretnék legalább egy puzzle-t kiiktatni valahonnan a triviális eseteken kívül. Azt nem hiszem, hogy valaha is eljutnék a tábla bármely részén ( legvalószínűbb, hogy a bal alsó negyedben a két clue puzzle közti átlón ) egy "összeomlásig". Legalábbis a 3x3-as elemekkel ( kb. 100 milliárd bejegyzés / cella ) biztosan nem lehetséges, de tesztek alapján a 4x4-es sem lenne elég. Talán az 5x5-ös elrendezés (12x12-es tábla). Megjegyzem, hogy a 3x3-as esetén kb. 1 óra a számítási igény a legtöbb cellánál ( mindig, mind a 100 milliárd bejegyzést szépen sorban elő kell állítani, hogy az 1 bit alapján el tudjam dönteni, kell-e még foglalkozni vele vagy sem ). Jelenleg 34,5GB RAM-ot foglal a program és egy 4TB-os merevlemezt. 4x4-es tábla esetén a RAM igényt ezen a szinten lehetne tartani, viszont minden cellához kellene abból a merevlemezből úgy 2-2000 darab ami azt is jelenti, hogy egy cella feldolgozási ideje kb. 390 nap lenne.

 

A 3x2-es és 2x3-as táblákról csak annyit említenék, hogy ezeket a jóval kisebb méret miatt már majdnem direktbe (átlagosan kb. 15ns alatt) tudom ide-oda konvertálgatni, ami egy érdekes lehetőséget nyitott 5x4-es illetve 4x5-ös méretű szűrőablakok alkalmazásához. Az ablak lehetne nagyobb is, de így kb. 0,2-1,5 óra / cella a szűrőrutin sebessége ami még emberinek tekinthető. Mivel 2x210/420 cellám van, így kb. egy hét alatt fut egy kört a szűrő a mátrixon. Sajna minden körben egyre kevesebb és kevesebb kombináció esik ki ( most, hogy már 15% kibukott, kb. 0,1% / kör a tempó és egyre rosszabb lesz... :( ).

Előzmény: MetalBear (898)
MetalBear Creative Commons License 2015.03.08 0 0 898

A Clue1-re visszatérve: én előállítottam az összes lehetséges módot [természetesen nem tároltam el őket :) ], és azon az elven dolgoztam, amit a 895ös hozzászólás bal oldali képe mutat. Mindig azt a pozíciót raktam le az összes lehetőségével, ahol ez a legkevesebb. Így minimalizálni tudtam az előállított állapotok számát.

 

Ezzel a módszerrel 39 gép használatával 483 óra alatt állítottam elő a 115.071.633.408 megoldást. Igen, 1 géppel több mint 2 év lett volna.. :)

 

A nagy kirakóra ez azért nem az igazi, mert ha az első néhány választás nem jó, akkor egy örökkévalóság, mire visszamegy addig a döntésig, és elindul más irányba.

 

Amúgy az alábbi oldalt találtam, elvileg ők kapták meg a részeredményért járó jutalmat is:

http://www.shortestpath.se/eii/results.html

Elvileg az utolsó módosítás: 27 January 2011 20:13:43, szóval nem tudom, mennyire valós a teljes kirakás, nem próbáltam ki a saját kirakómon :)

Axióma Creative Commons License 2014.06.23 0 0 897

Figyi, ezt az egesz feladvanyt matematikusok raktak ossze, tehat eselytelen, hogy ennek a belso torvenyszeruseginek ismereteben (vagy anelkul) kitalalt bejarassal lefusson. Ket lehetoseged van:

1. kizarsz bizonyos tipusu megoldasokat (en egy idoben azt akartam volna - ha lett volna idom foglalkozni vele - beepiteni, hogy a darabok felsorolasa az elofordulasuk sorrendjeben van, marmint a szabalyismertetoben vagy hol volt, ez mar eleg jo korlatozast adott volna backtrack-re -- de csak akkor mukodik, ha ott mar feleslegesnek tartottak a tovabbi random-ot, amit nem hiszek, de akkor meg semmi strategia nincs ra, ez egy halovany esely lett volna)

2. ahogy tudtommal az elsot megcsinaltak: kezzel kiraktak egy "valoszinu" reszt, es csak a maradekot kereste'k gepi erovel -- ez meg nyilvan csak akkor mukodik, ha jo a megsejtesedVan egy harmadik esely, hogy nem akarsz szisztematikusan menni, hanem veletlenszeruen allitasz elo sorozatokat, aztan vagy beletalalsz az elejen, vagy nem.

Nyilvan lehet egy csomo elofeldolgozast csinalni, amig a tarhely birja, pl. 2x2-esek vagy 4x4-esek teljes listaja es utana azokat osszehozni. De hidd el, ugy alkottak meg a feladatot, hogy ezek a kitalalhato strategiak tutira NE birkozzanak meg vele. Ezert is csak az 1. szerintibe oltem volna ne'mi energiat, amugy nem hiszem hogy okosabb vagyok azoknal, akik ezt ki_szamoltak_, hogy egy nyereseges uzlet lesz.

Előzmény: fekete akos (896)
fekete akos Creative Commons License 2014.06.22 0 0 896

Mivel túl sok a kombináció, így elkezdtem lokális maximumok alapján szűrni.

Lehet, hogy kukázom a jó megoldást is, de szeretnék bejárható méretű teret kapni.

Legalább egyszer kapjon esélyt a kereső...

Kár, hogy a tábla jórésze még mindig érintetlen. :(

fekete akos Creative Commons License 2014.06.15 0 0 895

 

Az első kép már ismert, az összes variációt mutatja adott mezőre.

A második kép a lerakható a puzzle-ok számát adja, forgatás nélkül.

Sajna, semmi változás a több évvel ezelőtti állapothoz képest. :)

fekete akos Creative Commons License 2014.06.12 0 0 894

Foglalkozik még valaki a megoldással?

pingvin Creative Commons License 2013.02.05 0 0 893
Kerep Elek Creative Commons License 2013.02.04 0 0 892

Hehe, 2 oldalnyit visszaolvastam, de ceges proxy megfogta a kepek felet...

Tok jo! Koszi! :)

Axióma Creative Commons License 2013.02.04 0 0 891

#883 ? Ennyit azert visszaolvashattal volna...

Előzmény: Kerep Elek (890)
Kerep Elek Creative Commons License 2013.02.04 0 0 890

Sziasztok!

Latom mar kicsit lecsengett az Eternity orulet es a forum is pihen. :) Mivel mar nem lehet penzt nyerni a dologgal, arra gondoltam megkerdem: nincs meg valakinek az osszes hint? Az 1-es es 2-es clue puzzle-t kiraktam, es be is kuldtem, de a 3-ast es 4-est nem lehetett itthon beszerezni es mar a oldal sem el ahova a megoldasokat be lehetne kuldeni... Nincs meg valakinek a 3-as es 4-es hint puzzle szama es orientacioja?

 

Elek

Axióma Creative Commons License 2012.03.19 0 0 889

Ja, nekem a bal felso tunt volna logikusnak:) Ezert lepett meg a jobb felso sarok kornyeki suru nemegyezesek, ami ezek szerint tok logikus...

Előzmény: fekete akos (888)
fekete akos Creative Commons License 2012.03.16 0 0 888

Ezen a képen talán jobban látszik, hogy a bal alsó sarokból indítottam a keresést:

( Sötét foltok jelzik, hogy hol nem passzolnak a színek. )

 

Előzmény: Axióma (887)
Axióma Creative Commons License 2012.03.16 0 0 887

Erdekes koncepcio... marmint hogy nem csinaltad meg a keretet se hibatlanra. Persze, belulrol indulva nem trivi, hogy az jon ki elobb.

Előzmény: fekete akos (885)

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!