Wie systematisch Liste mit unterschiedlich langen Listenelementen aufbauen?

[bernd1]

Hallo,
ich könnte etwas Ratschlag bei einem grundsätzlichen Problem brauchen:
Und zwar will ich ein Baccaratspiel simulieren, hierbei zieht bspw. der Spieler 5 Karten, der Bankier 3 Karten, je nach Spielerkartenwert zieht der Spieler ggbfls. noch eine 6. Karte.

Und dann wird anhand dieser „Endsituation“ ausgewertet wer gewonnen hat.

Ich würde mir gerne eine Lsite dieser möglichen „Endsituationen“ bauen, aber irgendwie bin ich mir unsicher wie oder mit welchem Datentyp.

Denn: Sagen wir, am Anfang zieht der Spieler eine Karte, das kann von 2 bis Ass gehen (die üblichen Karten halt).
Müssen wir schon mal 10 Szenarien in die Lsite aufnehmen.
Nun zieht der Spieler eine 2. karte.
Für jedes der bisherigen Szenarien spaltet es sich nun auf in je 10 Szenarien, je nahcdem was als 2. karte gezogen wird, usw.

Klar, normal könnte ich bei so eine Aufgabe, wenn ich sicher wäre dass die Lsitenelemente alle bspw. 8 Karten (5 Karten für Spieler, 3 für Bankier) lang sind, einfach Alles Mögliche durchgehen.

Aber wie erwähnt, abhängig von den ersten gezogenen Karten des Spielers kommen da noch 0, 1 oder manchmal auch 2 noch dazu.

und auch beim bankier gibt es Möglichkeiten wo der noch eine 4. Karte zieht
(Übrigens sind die Regeln gerade nicht zwingend richtig für baccarat, es geht mehr ums Prinzip)

Heißt ein „Endszenario“ ist 10 karten lang, ein anderes nur 8.

Und ich muss alle Endszenarien in einer einzigen Liste haben.

Nun frage ich mich wie ich das sinnvoll hinkriegen kann?

Welche Datentypen benutzen, welcher Algorithmus?
Wie vorgehen?

Ich habe einfach keine gute Idee :-/

TL;DR: um das Problem auf ein vll. greifbareres Beispiel runterzubrechen:
Spieler A und B spielen ein Würfelspiel.
A wirft 5 mal den Würfel.
B wirft 3 Mal den Würfel.
Falls A eine Augensumme <22 würfelt, muss er erneut würfeln.
Falls B eine Summe <10 würfelt UND As Augensumme >24 ist, würfelt B noch 2 mal.

Ich will eine Liste mit allen möglichen Spielendergebnissen basteln.
Wie am Sinnvollsten vorgehen, ist schwer da je nach den ersten Würfen die Gesamtwurfzahl pro Spiel variiert. Also Array ist da nicht :-/

[Marco13]

Wie schon beim letzten Thread muss ich die Frage stellen, ob es denn wirklich notwendig ist, ~„alles gleichzeitig im Speicher“ zu haben. Oft reicht es ja, wenn man über irgendwas drüberiterieren kann - sei es nun mit einem Iterator oder etwas moderner mit einem Stream.

Ansonsten ist mir nicht klar, warum die unterschiedlichen Längen ein Problem sein sollten. Man kann ja machen

List<List<Integer>> lists = new ArrayList<List<Integer>>();
lists.add(Arrays.asList(2,4,5,8,9));
lists.add(Arrays.asList(8,9,10));

und hat dann halt einfach zwei unterschiedlich lange Listen da drin…!?

[bernd1]

Frage ist halt, wie baue ich mir die Listen?

Gehen wir mal von einem einfachen Fall aus:
es werden 2 sechsseitige Würfel geworfen, wenn die Summe <4 ist, wird noch ein Würfel geworfen.

Klar kann ich händisch die Listte aufschreiben da kommen dann viele 2stellige Elemente vor und ein paar 3stellige.

Aber wie mahce ich das programmiertechnishc?

Ich meine, ganz naiv, könnte ich alle 6^3 Möglichkeiten für was 3stelliges durchgehen und halt die kombinationen nicht aufnehmen die unmöglich sind.
funktioniert hier noch recht gut.
Aber wenn man wie oben dann eher so 10^10 Kombinationen bestimmt von denen viele gar nciht vorkommen, ist das ineffizient.
Um nciht zu erwähnen dass rein das Erzeugen dieser viel zu vielen Kombinationen viel performance und so braucht, nur um dann snngemäß die meisten daovn wieder zu verwerfen.

Kann man da nicht irgendwie nur die auch wirklich vorkommenden kombis erzeugen?

ich stelle mir das so vor, wie bei einem baumdiagramm in der stochastik, wo man sowas wie eine tiefensuche macht.

erst den obersten pfad:
ziehe 5 als 1. karte, ziehe 3 als 2. karte, etc.

jeden pfad mal durchspielen und das ergebnis abspeichern oder so.

Klar, in meinem beispiel geht es mir um die bestimmung von gewinnwahrscheinlichkeiten bzw. des grundsätzlichen erwartungswert (wie wahrscheinlich gewinnt der spieler oder bankier, letztlich), da kann ich auch eins nach dem anderen erzeugen und verwerten (wobei auch da die Frage ist, wie ich nur zutreffende kombinationen erzeuge).

Aber bspw. in einem anderen Spiel Blackjack hängt es teilweise vom spieler ab was passiert, wird noch eine weitere karte gezogen, zieht er keine, splittet er womöglich die hand, etc.
Da kann ich nicht einfahc so alles vorerzeugen sozusagen :-/

[bernd1]

Ich habe gerade nachgedacht und vll. wäre sowas rekursives vll. sinnvoll:

public class Test{
  List<String> kartenwerte= new List<String>;
  int spielergewinne=0;
  int bankiergewinne=0;

  public void rectest(){
  if(!validateresult().equals("unresolved")){
    //abhängig vom rückgabewert von validateresult()
   //spielergewinne oder bankiergewinne um 1 erhöhen
  return;
  }
else{
  
for(int i=2;10;i++){//hier eine neue Karte ziehen, i gibt den gezogenen Kartenwert an
  list.add(i);
  rectest();
  list.remove(i);
/*es wird also zur bisherigen liste eine karte hinzugefügt, in der aufgerufenen methode dann mit der um die karte erweiterten liste weitergewerkelt (und notfalls weiter kram hinzugefügt)
und dann beim "eine ebene hochkommen" die letzte karte wieder entfernt*/
//real wäre es umständlicher weil für spieler und bankier zu gucken ist ob nnoch karten zu ziehen sind
}
}

  }

public String validateresult(){
//Methode die das aktuelle Kartenwerte Attribut nimmt und guckt
//ob dieses "zu Ende gespielt" ist und gibt entweder den gewinner an oder
//false falls noch kein Ergebnis vorliegt 
}

}

So eine sehr groß umfasste Skizze, kurzum gehe ich durch rekursion jedes mögliche spiel durch.
rekursionstiefe dürfte kein problem sein, werden die kartenlisten maximal 10 karten lang, haben wir rekursionstiefe 10, was locker verkraftbar sein müsste.
gut, halt im worstcase 10 verschachtelte for schleifen aus i´untershciedlichen rekursionsebenen.
Aber so vpm grundprinzip her müsste es gehen, oder?

mir fiele zumindest auf anhieb keine explizite lösungsmöglichkeit ohne rekursion ein :-/

[bernd1]

Ich habe es gerade mal an einem sehr primitiven Beispiel getestet (Alle Zahlen mit Ziffern 1-3 auszugeben, deren Quersumme >5 ist), das Prinzip scheint zu funktionieren

[Marco13]

Ja, etwas, was im wesentlichen einem Suchbaum entspricht wäre da der nahe liegende Vorschlag gewesen. Wenn man eine genauere Idee davon hat, was dort eigentlich ausgerechnet werden soll, sollte man die Suche an sich auch recht leicht implementieren können: Im wesentlichen macht man dann ja nichts anderes als eine Breitensuche oder Tiefensuche durch den Zustandsraum.

• Fange an mit dem „leeren“ Anfangszustand
• Solange noch unbearbeitete Zustände existieren:
  • Nimm einen unbearbeiteten Zustand
    • Wenn es ein „Endzustand“ ist, packe ihn in die Ergebnismenge
    • Andernfalls berechne alle möglichen Nachfolgezustände, und merke sie dir als ‚unbearbeitet‘

Hier mal schnell implementiert, mit einer Breitensuche, und einer recht willkürlichen isFinal-Funktion. (Ich nehme an, ein Zustand ist „final“, wenn man mehr als 2 Karten oder mehr als 15 Punkte hat … was auch immer)

package bytewelt;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class NotBaccarat
{
    public static void main(String[] args)
    {
        Set<List<Integer>> finalStates = new LinkedHashSet<List<Integer>>();

        Deque<List<Integer>> stack = new LinkedList<List<Integer>>();
        List<Integer> initialState = Collections.emptyList();
        stack.push(initialState);
        
        while (!stack.isEmpty())
        {
            List<Integer> state = stack.removeLast();
            if (isFinal(state))
            {
                System.out.println("Found final state: "+state);
                finalStates.add(state);
            }
            else
            {
                System.out.println("Current state: " + state + ", sucessors:");
                List<List<Integer>> successors = computeSuccessors(state);
                for (List<Integer> successor : successors)
                {
                    System.out.println("  " + successor);
                    stack.push(successor);
                }
            }
        }
        System.out.println("Final states: " + finalStates);
    }

    private static List<List<Integer>> computeSuccessors(List<Integer> state)
    {
        List<Integer> possibleNextCards =
            Arrays.asList(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14);
        List<List<Integer>> successors = new ArrayList<List<Integer>>();
        for (int i = 0; i < possibleNextCards.size(); i++)
        {
            int nextCard = possibleNextCards.get(i);
            List<Integer> successor = new ArrayList<Integer>(state);
            successor.add(nextCard);
            successors.add(successor);
        }
        return successors;
    }

    private static boolean isFinal(List<Integer> state)
    {
        // Whatever that condition is...
        if (state.size() > 2)
        {
            return true;
        }
        int sum = state.stream().mapToInt(i -> i).sum();
        return sum > 15;
    }
}