Logikai játék megoldása
2015-07-02T19:29:16+02:00
2015-07-04T01:20:18+02:00
2022-07-19T03:47:54+02:00
  • Itt a forras, kicsit elborult bitbuveszkedosre csinaltam, hogy memoriasporolos es egesz gyors legyen.
    Kommentezni nem volt idom:

    import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class DiceGame { // Possible cell states: LEFT, RIGHT, FORWARD, BACKWARD, TOP, BOTTOM, EMPTY (meaning where the white part is) // Possible directions to move a dice: LEFT, RIGHT, FORWARD, BACKWARD private static final int LEFT = 0; private static final int RIGHT = 1; private static final int FORWARD = 2; private static final int BACKWARD = 3; private static final int TOP = 4; private static final int BOTTOM = 5; private static final int EMPTY = 6; private static int[] stateTeansitions = new int[24]; // 6*4 // key: a possible game state. value: from which state we came here first. private static Map<Integer,Integer> gameStates = new HashMap<Integer, Integer>(); private static void transition(int oldState, int direction, int newState) { stateTeansitions[oldState*4+direction] = newState; } private static int transition(int oldState, int direction) { return stateTeansitions[oldState*4 + direction]; } private static int getHoleIndex(int gameState) { for(int i=0; i<9; i++) { if(getStateAtCell(gameState, i) == EMPTY) return i; } return 0; // Should never come here. } private static int getStateAtCell(int gameState, int cellIndex) { return (gameState >> (cellIndex*3)) & 7; } // Returns the new game state. private static int setStateAtCell(int oldGameState, int cellIndex, int newCellState) { int inverseMask = ~(7 << (cellIndex*3)); int newStateMask = newCellState << (cellIndex*3); return (oldGameState & inverseMask) | newStateMask; } private static int moveHoleLeft(int gameState) { int holeIndex = getHoleIndex(gameState); gameState = setStateAtCell(gameState, holeIndex, transition(getStateAtCell(gameState, holeIndex-1), RIGHT)); return setStateAtCell(gameState, holeIndex-1, EMPTY); } private static int moveHoleRight(int gameState) { int holeIndex = getHoleIndex(gameState); gameState = setStateAtCell(gameState, holeIndex, transition(getStateAtCell(gameState, holeIndex+1), LEFT)); return setStateAtCell(gameState, holeIndex+1, EMPTY); } private static int moveHoleForward(int gameState) { int holeIndex = getHoleIndex(gameState); gameState = setStateAtCell(gameState, holeIndex, transition(getStateAtCell(gameState, holeIndex-3), BACKWARD)); return setStateAtCell(gameState, holeIndex-3, EMPTY); } private static int moveHoleBackward(int gameState) { int holeIndex = getHoleIndex(gameState); gameState = setStateAtCell(gameState, holeIndex, transition(getStateAtCell(gameState, holeIndex+3), FORWARD)); return setStateAtCell(gameState, holeIndex+3, EMPTY); } private static List<Integer> getPossibleNextGameStates(int gameState) { List<Integer> ret = new ArrayList<Integer>(); int holeIndex = getHoleIndex(gameState); int holeRow = holeIndex / 3; int holeColumn = holeIndex % 3; if(holeColumn > 0) ret.add(moveHoleLeft(gameState)); if(holeColumn < 2) ret.add(moveHoleRight(gameState)); if(holeRow > 0) ret.add(moveHoleForward(gameState)); if(holeRow < 2) ret.add(moveHoleBackward(gameState)); return ret; } private static boolean isAllBottom(int gameState) { for(int i=0; i<9; i++) { int state = getStateAtCell(gameState, i); if((state != EMPTY) && (state != BOTTOM)) return false; } return true; } public static void searchSolution(int initialGameState) { gameStates.clear(); gameStates.put(initialGameState, initialGameState); List<Integer> lastStates = new ArrayList<Integer>(); lastStates.add(initialGameState); boolean wasNewState = true; int turn = 0; while(wasNewState) { wasNewState = false; List<Integer> currentStates = new ArrayList<Integer>(); System.out.println("turn: " + turn + " num of game states: " + gameStates.size()); for(Integer gameState : lastStates) { List<Integer> nextGameStates = getPossibleNextGameStates(gameState); for(Integer s : nextGameStates) { if(!gameStates.containsKey(s)) { wasNewState = true; gameStates.put(s, gameState); currentStates.add(s); } if(isAllBottom(s)) { System.out.println("Found a solution!: " + s); List<Integer> path = getPathTo(s); printPath(path); return; } } } lastStates = currentStates; turn++; } } public static void printPath(List<Integer> path) { for(Integer s : path) { printGameState(s); System.out.println(); } } private static char stateToChar(int state) { switch(state) { case LEFT: return '<'; case RIGHT: return '>'; case FORWARD: return '^'; case BACKWARD: return 'v'; case TOP: return 'T'; case BOTTOM: return 'B'; case EMPTY: default: return ' '; } } private static void printGameState(int gameState) { for(int row=0; row < 3; row++) { for(int column=0; column < 3; column++) { System.out.print(stateToChar(getStateAtCell(gameState, row*3+column))); } System.out.println(); } } public static List<Integer> getPathTo(int gameState) { List<Integer> tmp = new ArrayList<Integer>(); tmp.add(gameState); while(true) { int prevGameState = gameStates.get(gameState); if(prevGameState == gameState) { // this is the first state break; } tmp.add(prevGameState); gameState = prevGameState; } List<Integer> ret = new ArrayList<Integer>(); for(int i=tmp.size()-1; i>=0; i--) { ret.add(tmp.get(i)); } return ret; } public static void init() { transition(LEFT, LEFT, BOTTOM); transition(LEFT, RIGHT, TOP); transition(LEFT, FORWARD, LEFT); transition(LEFT, BACKWARD, LEFT); transition(RIGHT, LEFT, TOP); transition(RIGHT, RIGHT, BOTTOM); transition(RIGHT, FORWARD, RIGHT); transition(RIGHT, BACKWARD, RIGHT); transition(FORWARD, LEFT, FORWARD); transition(FORWARD, RIGHT, FORWARD); transition(FORWARD, FORWARD, BOTTOM); transition(FORWARD, BACKWARD, TOP); transition(BACKWARD, LEFT, BACKWARD); transition(BACKWARD, RIGHT, BACKWARD); transition(BACKWARD, FORWARD, TOP); transition(BACKWARD, BACKWARD, BOTTOM); transition(TOP, LEFT, LEFT); transition(TOP, RIGHT, RIGHT); transition(TOP, FORWARD, FORWARD); transition(TOP, BACKWARD, BACKWARD); transition(BOTTOM, LEFT, RIGHT); transition(BOTTOM, RIGHT, LEFT); transition(BOTTOM, FORWARD, BACKWARD); transition(BOTTOM, BACKWARD, FORWARD); } public static void main(String[] args) { init(); int gameState = 0; gameState = setStateAtCell(gameState, 0, TOP); gameState = setStateAtCell(gameState, 1, TOP); gameState = setStateAtCell(gameState, 2, TOP); gameState = setStateAtCell(gameState, 3, TOP); gameState = setStateAtCell(gameState, 4, EMPTY); gameState = setStateAtCell(gameState, 5, TOP); gameState = setStateAtCell(gameState, 6, TOP); gameState = setStateAtCell(gameState, 7, TOP); gameState = setStateAtCell(gameState, 8, TOP); searchSolution(gameState); } }
    Mutasd a teljes hozzászólást!
  • Ugyanaz jott ki nekem is mint neked.

    Az en programom ezt irja ki:

    turn: 0 num of game states: 1 turn: 1 num of game states: 5 turn: 2 num of game states: 13 turn: 3 num of game states: 21 turn: 4 num of game states: 37 turn: 5 num of game states: 69 turn: 6 num of game states: 133 turn: 7 num of game states: 213 turn: 8 num of game states: 361 turn: 9 num of game states: 585 turn: 10 num of game states: 1033 turn: 11 num of game states: 1665 turn: 12 num of game states: 2881 turn: 13 num of game states: 4649 turn: 14 num of game states: 8113 turn: 15 num of game states: 13073 turn: 16 num of game states: 22555 turn: 17 num of game states: 35851 turn: 18 num of game states: 61335 turn: 19 num of game states: 97079 turn: 20 num of game states: 164175 turn: 21 num of game states: 254759 turn: 22 num of game states: 421317 turn: 23 num of game states: 638929 turn: 24 num of game states: 1022533 turn: 25 num of game states: 1488625 turn: 26 num of game states: 2255836 turn: 27 num of game states: 3094560 turn: 28 num of game states: 4354768 turn: 29 num of game states: 5563540 turn: 30 num of game states: 7194780 turn: 31 num of game states: 8537092 turn: 32 num of game states: 10155559 turn: 33 num of game states: 11300883 Found a solution!: 112647021 TTT T T TTT TTT >T TTT TT v>T TTT < T v>T TTT << v>T TTT <<^ v> TTT <<^ v B TTT < ^ v<B TTT T^ v<B TTT TT^ <B TTT TT^ B B TTT T ^ BvB TTT >^ BvB TTT v>^ vB TTT v>^ v B TTT v>^ v^B T T v>^ v^B T< v>^ v^ T<^ v> v^T T<^ v B v^T T<^ vBB v T T<^ vBB vT T<^ vBB ^vT <^ vBB ^vT B ^ vBB ^ T BB^ vBB ^< BB^ vB ^<^ BB^ v < ^<^ BB^ v< ^<^ BB^ Bv< <^ BB^ Bv< B ^ BB^ B < BB^ BB^ BB BB^ BB^ BBB BB BB^ BBB BBB BB
    A 'T' azt jelenti, hogy 'Top' vagyis fent van a feher, a 'B', hogy Bottom, vagyis lent van a feher, a tobbinel meg arra van amerre a nyil mutat.

    A kovetkezo hozzaszolasomba beirom a java forrast.
    Mutasd a teljes hozzászólást!
  • Igazából neked mint játék készítőnek csak az a dolgod, hogy olyan feladat elé állítsd a játékosokat, amit meg lehet oldani. Tehét jogos a brute force-os felvetés.
    Ha a gép meg tudja csinálni, akkor a matematikai megközelítést hagyd a játékosokra.

    Amúgy van egy jó hírem, meg lehet oldani a feladatot.
    És van egy még jobb. Bármilyen állapotból el lehet érni bármilyen másik állapotot.
    Tehát nem tudsz olyan feladatot adni, amit ne lehetne megoldani.

    A nadamhu által adott felsőbecslés pontos.
    9*(6^8) = 15116544
    Pontosan ennyi állapota van a játékra írt programom szerint is.

    A programom az első megoldást 34 lépés után találta meg a kezdőállapotból.

    FBLLJFBFJLBFJLJLBBFJFJLBLBFFJLBLJJ
    Gondolom egyértelműek az irány rövidítések Fel, Le, Jobbra, Balra.
    A fel azt jelenti, hogy a üres terület alatti kockát mozgatjuk felfelé.

    Az a megoldás, ahol az üres terület középen helyezkedik el 36 lépésből van meg.

    FBLJFJLBLJFBLBFFJLJFBLBFJLJFBBLJJLBF
    49 lépés kellett, hogy az összes állapotot elérjük a kezdőállapotból.

    Szerintem nem érdemes nagyobb pályákat készíteni, szerintem azok csak könnyebbek.
    Ha valaki megtudja oldani a 3x3-as pályát, akkor bármelyiket megtudja.

    Amúgy ötletes játék.
    Mutasd a teljes hozzászólást!
  • Miert, mi a baj a brute force-al?

    Igyekszem matematikai úton megközelíteni.

    Bővebben:
    Anno amikor ezzel a játékkal foglalkoztam (a screenshot-ok egész konkrétan az érettségimunkámból vannak), szerettem volna megcsinálni több level-es játéknak megcsinálni, hiszen a játékmechanizmus adott volt hozzá.
    Ehhez viszont jó lett volna tudni, hogy pl egy 8x8 pálya 2 üres mezővel megoldható-e. Jó lenne tudni, hogy hogyan tudom nehézség szerint rangsorolni a pályákat anélkül hogy az összes létező lehetőséget lefuttatom. StbStbStb.

    Elég a szócséplésből, holnap lekódolom a bruteforce-ot, nézzük ugyanarra jutunk-e mindannyian 
    (Most meg sör a kézbe, elvégre péntek este van
    Mutasd a teljes hozzászólást!
  • Ezt a tilitoli hasonlatot nem teljesen értem.

    A tilitolinál tologatod az üres mezőre az egyik négyzetet.
    A játékomnál szintúgy. 

    Ha a tilitoliban "A" négyzetet eltolsz egy irányba akkor az üres mező "0" pozíciója és az adott négyzet "helyet cserélnek"
    Remélem érthető ha ezt így írom fel: A.x++, 0,y-- 

    Viszont ha a játékomban teszed meg ugyanezt akkor a pozíciók ugyanúgy változnak mint a tilitolinál, viszont a mozgatott kocka "értéke" is változik, hiszen azt átfordítottuk.
    Röviden: A.x++, 0.y--, A=f(A) - ahol a "f" transzformációt leíró függvényt jelenti.

    Üdv:
    Balázs
    Mutasd a teljes hozzászólást!
  • Van valakinek valamilyen ötlete a megoldására (bruteforce nélkül)?

    Miert, mi a baj a brute force-al?

    Most nem erek ra, de ha estig nem lesz szebb megoldas, megcsinalom a brute-force programot javaban (breadth first search shortest path); ami vagy bizonyitja, hogy nincs megoldas, vagy megadja (az egyik) legrovidebb uthosszu megoldast.
    Az alapotterre a trivialis felso korlat 7^9, ami csak 40 millio, az aktualis allapotter ennel is jelentosen kisebb, szoval arra szamitok, hogy viszonylag gyorsan le fog futni es termeszetesen lazan beferek a memoriaba is.

    Szerk.: meg mindig eleg trivialis felso korlat az allapotok szamara a 9*(6^8) ami meg mar csak kb. 15 millio.
    Mutasd a teljes hozzászólást!
  • Szerintem, ez a következő tili-toli-nak felel meg:

    +-+-+-+ |9|8|7| +-+-+-+ |6| |4| +-+-+-+ |3|2|1| +-+-+-+
    Amennyibe ez megoldható, úgy ugyanazokkal a lépésekkel az eredeti probléma is.
    Mutasd a teljes hozzászólást!
  • Érdekes játékötlet.
    Először azt hittem ez nagyon egyszerű, de most látom hogy nem.

    Egy előnye van, a játékos sokáig törné a fejét azon, hogy hogyan is lehet megoldani. "Ez csak az első pálya, nehogy már kifogjon rajtam." Szóval lekötné az embert jó időre.

    Amíg nincs bizonyítva hogy megoldhatatlan, addig "jó ez így".
    Mutasd a teljes hozzászólást!
  • Első ránézésre én is könnyebbnek találom, mint a tili-tolit, de mivel itt egy kockát minimálisan kétszer kell forgatni, ezért lehet, hogy még nehezebb megoldani. Mindenesetre érdekes feladat.
    Mutasd a teljes hozzászólást!
  • Bár jövő szerdáig nincsen sajnos időm belemélyedni (ha addig esetleg nem írna senki (ami valószínűtlen), akkor emlékeztess), de így első ránézésre én hasonlóan állnék neki, mint a tili-toli játéknak.
    A* algoritmussal, meg egy minél jobb költségfüggvénnyel (bár elsőnek talán a rosszul elhelyzett kockák száma is megfelelhet). Érzésre szerintem könnyebb is, mint a tili-toli játék....

    (Bár jobban átgondolva, nem vagyok benne biztos, hogy 3x3as méretben megoldható)
    Mutasd a teljes hozzászólást!
  • Az első lépés utáni screenshot
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Üdv mindenkinek!

    Amikor gyerekkoromban elkezdtem ismerkedni a programozás világával, kitaláltam egy játékot, amit utána meg is valósítottam. Azóta ezt a játékot minden programnyelven megvalósítottam amivel - legalább érintőlegesen foglalkoztam (QBasic, TurboPascal, TurboC, VisualBasic, Android-Java, C# - nem feltétlenül ebben a sorrendben)

    A napokban nézegettem a régi kódjaimat, és újra a kezem közé került.

    A játék leírása a következő:
    Adott egy 3x3 négyzetből álló játéktér.
    Kezdéskor a mindegyiken négyzeten van egy félig fekete, félig fehér kocka, a fehér felével felfelé - kivéve a középső mezőt. A játékban úgy mozgathatjuk a kockákat, hogy gurítjuk azokat (az élén átfordítjuk a szabad mezőre). A cél, hogy az eredetileg fehér felükkel felfelé néző kockákat úgy forgassuk, hogy a teljesen fehér részek lefelé legyenek. (Huhh, ez kicsit kusza leírás lett, de csatolok képeket )

    Nem emlékszem, hogy valaha is sikerült volna megoldanom - vagy bárkinek aki játszott vele.

    Van valakinek valamilyen ötlete a megoldására (bruteforce nélkül)?

    Üdv: Balázs
    Mutasd a teljes hozzászólást!
    Csatolt állomány
abcd