Results 1 to 11 of 11
Like Tree5Likes
  • 2 Post By DarrylBurke
  • 3 Post By Norm

Thread: not-unique keys in hashmap possible?

  1. #1
    Maarten is offline Member
    Join Date
    Dec 2011
    Location
    Utrecht
    Posts
    35
    Rep Power
    0

    Default not-unique keys in hashmap possible?

    Hello,
    For a checkers program I am trying to write, I want to make a list of all the possible moves the computer can do. For that I want to create a hashmap of all the checkerpiece-destination possibilities. But that way I do not have unique values in the hashmap because a piece can do different moves sometimes.
    Is there a way to make a list of piece-destination possibilities that does not require unique keys?
    thanks
    Maarten.

  2. #2
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    12,059
    Rep Power
    26

    Default Re: not-unique keys in hashmap possible?

    Map<Piece, List<Destination>> OR Set<PieceDestination> where PieceDestination encapsulates a Piece and a Destination.

    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  3. #3
    Xen
    Xen is offline Member
    Join Date
    Jan 2015
    Posts
    86
    Rep Power
    0

    Default Re: not-unique keys in hashmap possible?

    So in other words: you want to have (Piece, Destination) tuples where Piece is not unique.

    The question is also how you want to operate (traverse) on the data set.

    You can easily turn the Map into a <Piece, List<Destination>> thing. Or, alternatively, into <Piece, List<PieceDestination>>.

    This is how I am currently doing it: I just draw an ArrayList out of a HashMap (or EnumMap, in my case, often) and I use the ArrayList to store the "additional" entries.

    Ideally, you would have a Set based on <PieceDestination> (Piece, Destination) that you can filter based on Piece.

    You could create your custom Set object/class that can do unions/difference and all that.

    You need a method that will return a subset of the Set based on a certain criterium.

    You would create a "PieceDestination" object that is sorted based on Piece first, and Destination later.

    The method would be indexed by Piece and would yield either a subset of the Set for that specific particular Piece object, or even just a list of Destinations.

    Java Code:
    public Set subset(Piece p) {
        Set newSet = new TreeSet();
        foreach (PieceDestination pd: this) {
            if (pd.piece.equals(p)) {
                newSet.add(pd);
            }
        }
        return newSet;
    }
    Just something like that. This traversal operates in linear time. You can use TreeSet to be faster. I think. I don't know.

  4. #4
    Maarten is offline Member
    Join Date
    Dec 2011
    Location
    Utrecht
    Posts
    35
    Rep Power
    0

    Default Re: not-unique keys in hashmap possible?

    Thanks for the replies.
    I made it like this:

    Java Code:
    private HashMap<DamSchijf, ArrayList> mogelijkeZetten;
    then I put the destinations in an Arraylist and then put the checkerpiece-destinationlist combo's in the hashmap.
    and it worked, thanks for the ideas!

    Next step is how i can make the computer select a smart move, i think i will be back on the forum in the near future :)

    cheers Maarten.

  5. #5
    Xen
    Xen is offline Member
    Join Date
    Jan 2015
    Posts
    86
    Rep Power
    0

    Default Re: not-unique keys in hashmap possible?

    Oh my. I would suggest you take a look at:

    https://en.wikipedia.org/wiki/Minimax

    Het idee is dat je gaat bepalen wat de beste zet is die je tegenstander kan doen voor elke zet die je zelf doet. Je moet er van uit gaan dat de tegenstander de voor hem beste zet zal kiezen, wat dus voor jou het slechtst is. Maar omdat je niet moet uitgaan van een slechte tegenstander (in de hoop dat het niet zo erg zal zijn) kijk je dus bij elke zet van jezelf wat de uitkomst gaat zijn als de tegenstander op z'n best presteert. Die zet van jou waarbij de uiteindelijke uitkomst het beste is (waarbij de maximale score van je tegenstander het laagst is) is de zet die je dan gaat doen.

    Het mooie hiervan is dat je het meerdere levels diep kan doen. Want wat is de beste zet van je tegenstander? Dat is de zet waar jij vervolgens weer het slechtste beste antwoord op hebt. Daarbij is het natuurlijk nodig dat je in staat bent de resultaten te evalueren. Je kan bijvoorbeeld het aantal stenen en dammen tellen. Je kan ook de concentratie van stenen rond het centrum als uitgangspunt nemen, of juist dat een steen die ver is doorgedrongen in het territorium van de tegenstander, misschien wel meer waard is. Als je het goed speelt, kun je elke zet op het bord ongedaan maken, zodat je in je zoektocht maar één bord hoeft te beheren, als je tenminste diepte-eerst zoekt, dwz. dat je elke tak van de boom af gaat op het moment dat je hem tegenkomt tot een bepaalde diepte. Het lastige daarvan is dat je de diepte van te voren moet zetten zodat als je bijvoorbeeld 10 zetten per bord hebt (per toestand) en vervolgens 6 halfzetten diep gaat, dat je dan op 10 tot de macht 6 aan mogelijke 'borden' gaat moeten evalueren (aan het einde van de boom). Dat zouden er dan een miljoen zijn, wat niet zo veel is.

    Je kunt ook 'breedte eerst' gaan, maar dan moet je voor elk level alle mogelijke zetten in een Queue plaatsen, vervolgens bijv. alle borden die daarvan resulteren in een Queue plaatsen, vervolgens (bij het volgende level/niveau/diepte) al die borden een voor een verwerken, zetten genereren, zetten maken, weer in de Queue voor het volgende level, zodat je uiteindelijk een miljoen verschillende borden in je geheugen hebt. Maar dan kan je wel makkelijker centraal het algoritme/de zoektocht afbreken.

    Als het te lang duurt dus, bijvoorbeeld ;-). Bovendien kun je dan een vaste tijdslimiet vaststellen en dat je afbreekt (alles evalueert) wanneer je daar zin in hebt. Bij diepte-eerst is dat eigenlijk onmogelijk, tenminste het kan wel, maar dan breek je het af op het moment dat je zoektocht vrij onvolledig is (bepaalde takken heb je dan helemaal afgezocht, andere helemaal niet).

    Je kunt voortijdig afbreken op het moment dat het er heel slecht voor je uit begint te zien, bijvoorbeeld als na 5 zetten de toestand wanhopig is, hoef je niet meer verder te zoeken in die tak. Een andere tak kan je dan langer door laten gaan als die wel heel prettig is voor je. Zo kun je je zoektocht wat optimaliseren, en met andere dingen.

    Dat betekent dat je voor een bepaalde tak de evaluatie op niveau 5 als waarde neemt of als uitgangspunt voor de uiteindelijke beslissing op niveau 1 (of niveau 0) terwijl je voor een gunstigere tak de waardering pas op niveau 10 (bijv.) als uitgangspunt neemt voor de uiteindelijke beslissing op niveau 1 (of 0). Zo bepaal je gewoon hoe je je tijd besteedt.

    Best leuk dit, succes er mee :).
    Last edited by Xen; 08-08-2015 at 06:27 PM.

  6. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: not-unique keys in hashmap possible?

    Please post in English.
    If you don't understand my response, don't ignore it, ask a question.

  7. #7
    Xen
    Xen is offline Member
    Join Date
    Jan 2015
    Posts
    86
    Rep Power
    0

    Default Re: not-unique keys in hashmap possible?

    Now was that not predictable. Why not let a person be? Always bugging people with your demands...

  8. #8
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    12,059
    Rep Power
    26

    Default Re: not-unique keys in hashmap possible?

    Quote Originally Posted by Xen View Post
    Now was that not predictable. Why not let a person be? Always bugging people with your demands...
    This is an English language forum. Please post a translation of your post at #5 above or it may be removed.

    db
    Norm and JosAH like this.
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,003
    Rep Power
    33

    Default Re: not-unique keys in hashmap possible?

    Always bugging people with your demands
    How was a request prefixed with a Please a demand?
    jim829, JosAH and DarrylBurke like this.
    If you don't understand my response, don't ignore it, ask a question.

  10. #10
    Xen
    Xen is offline Member
    Join Date
    Jan 2015
    Posts
    86
    Rep Power
    0

    Default Re: not-unique keys in hashmap possible?

    I've sent the Dutch text to the OP in private. You can delete it, if you want.

    Oh I didn't send the English part though. Regards.

  11. #11
    DarrylBurke's Avatar
    DarrylBurke is offline Forum Police
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    12,059
    Rep Power
    26

    Default Re: not-unique keys in hashmap possible?

    I've moved two posts from this thread to a more appropriate place: http://www.java-forums.org/suggestio...-possible.html

    For other readers, this is what Google Translate produces from post #5.
    The idea is that you determine the best move that can make your opponent for every move you make yourself. You have to assume that the opponent will choose the best move for him, so what is worst for you. But because you should not go out of a bad opponent (in the hope that it will not be so bad) you look so at every turn yourself what the outcome will be if the opponent is performing at its best. That puts you on where the final outcome is the best (maximum score of your opponent is lowest) is the move that you will do.

    The benefit is that you can do it several levels deep. For what is the best move of your opponent? That's where you put then again have the worst best answer. It is of course necessary that you are able to evaluate the results. For example, you can count the number of stones and dams. You can also the concentration of stones around the center as a starting point, or just a stone that has penetrated far into the territory of the opponent, perhaps more worth. If you play well, you can undo every move on the board, so you have to manage in your quest but one sign, at least if you depth-first search, that is. you go down each branch of the tree at the moment you meet him at a certain depth. The tricky part is that you have to put the depth in advance so if for example you have 10 moves per plate (per state) and then goes 6 half moves deep that you 10 will have to evaluate the power 6 to possible 'signs' (at the end of the tree). That there would be a million, which is not so much.

    You can also 'breadth first' go, but you must take all possible for each level in a Queue places, then eg. All signs that it will result in a Queue places, then (at the next level / level / depth) all those plates generate a process, putting, make, again in the Queue for the next level, so that you finally have a million different signs in your memory. But you can easily centrally algorithm / abort the search.

    If it takes too long, for example ;-). Moreover, you can then set a fixed time limit, and that you break (evaluates all) when you feel like it. In depth-first is actually impossible, at least it can, but then you break it off when you quest is pretty incomplete (some branches have you completely searched, others not at all).

    You can prematurely at the time to see it very bad for you from starting, such as after 5 put the situation is desperate, you do not continue searching in that branch. Another branch longer than you can let go like that is very pleasant for you. So you can search some optimization, and other things.

    That means that for a given branch, take the assessment at Level 5 as value or as the basis for the final decision at Level 1 (or level 0), while a more favorable valuation branch until level 10 (eg.) As a starting point the final decision at Level 1 (or 0). So you decide just how you spend your time.

    Quite fun this success with it :).
    db
    If you're forever cleaning cobwebs, it's time to get rid of the spiders.

Similar Threads

  1. Replies: 0
    Last Post: 05-12-2013, 10:51 AM
  2. HashMap with multiple keys for single value
    By CodeX Pro in forum New To Java
    Replies: 5
    Last Post: 05-07-2013, 02:20 PM
  3. final HashMap hm=new HashMap();
    By sangramkeshari.jena in forum New To Java
    Replies: 4
    Last Post: 07-21-2011, 09:44 PM
  4. Replies: 7
    Last Post: 12-08-2009, 07:17 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •