Condition Akinator

Java-Forum Spiele- und Multimedia-Programmierung
1

Hey leute.

Da ich gerade keinen pc habe, mach ich pause mit opengl und brauche ein projekt, welches sich im laufe der info-stunden entwickeln kann ^^

Vielleicht kennt ihr das spiel, akinator. Es ist quasi ein “wer ist das”. Der computer stellt einem fragen, und man muss antworten mit ja oder nein, ob das gefragre auf due person zutrifft, die man sich vorher ausgedacht hat.

Mein ansatz war jetzt folgender. Ein enum attributes, enthaelt halt punkte wie gender, name und so weiter.
Dann die klasse anobject welche eine map<attribute, value> hat.

Das spiel hat nun zugriff auf alle diese daten, Beispielsweise in einer array list. (Kommen die daten nun von ner datenbank oder einfach als ordner mit file pro objekt, ist ja egal).

Eine methode nextCondition wuerde nun alle objekte von diesem datenhaufen entfernen, die diese condition nicht erfüllen. Das heisst jedesmal iteration durch alle daten. Das so lange bis daten laenge = 1 oder halt 0. (Nix gefunden).
Ein Algorithmus waehlt passende fragen und somit conditions aus, der user beantwortet und legt den inhalt der condition aller fragen fest. Sprich sowas wie nextQuestion gibt mir die naechste frage.

Erst einmal: ist der ansatz so sinnvoll? Ich meine, angenommen man hat 100000 objekte, alle gleichzeitig im speicher, bei jeder neuen condition iteration durch alles, ergibt das sinn?

Wuerd mich ueber rueckmeldungen freuen.

Ah und, wie wuerdet ihr die fragen auswaehlen, damit es nicht "zu einfach " fuer den computer wird? ZB kann man mit “ist der anfangsbuchstabe …” schon ganz viel ausschließen, aber das ist ja nicht sinn der sache…

2

Enum mit Atributen gefällt mir garnicht. Das ist ja sehr beschränkt. Abgesehen davon müsste jedes Mal der Quellcode angepasst werden, wenn ein neues Merkmal hinzu kommt.

Da die Fragen immer dem Schema folgen: Ist die Person (ein/e) (Mann, Europäer, Schauspieler, tot, Cartoonfigur…) würde ich mir diese Merkmale wie (String-)Tags der jeweiligen Person vorstellen. Also “Set tags” als Attribut einer Klasse Person. Die Suche dann in erster Näherung -wie von Dir beschrieben- durch alle iterieren, schauen, ob tags.contains(“gefrages_Merkmal”). Dies auf jeden Fall Funktional mit Predicates und (Parallel-)Streams. Das lässt sich nämlich schön paralellisieren. Erst, wenn Du hier Engpässe bemerkst, Optimierung einbauen. Z.B. einen “Index” für bevorzugt und meist am Anfang abgefragte Merkmale (tot/lebendig, mann/frau,…).

Edit: Wenn Du eine Typisierung von Attributen brauchst (das war wohl Dein Hintergedanke bei der Enum-Idee), dann Map<String,String>

3

Die Speicherung und Indizierung ist eine Sache. Da könnte irgendwo ein https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html vorkommen, aber mit wie großen Kanonen man da auf wie kleine Vögel schießen will, muss man sich halt überlegen.

Interessanter ist da schon fast die Frage, wie man die nächste Frage auswählt. Das hängt natürlich mit der Indizierung (bzw. dem Mapping zwischen Bits und Fragen) zusammen. Ob’s da “irgendein” Diversity index - Wikipedia, the free encyclopedia schon tut? Man würde ja versuchen, den Informationsgewinn zu maximieren, also z.B. die Frage auswählen, durch die man die noch in Frage kommende Menge genau in der Mitte aufschneidet…

4

@nillehammer : ich dachte es bleibt damit ueberschaubar, da ich dann ins enum schaue und sehe welche attribute es alles gibt. Denn manche attribute koennen die selben werte haben, (zB haarfarbe und… ka… hautfarbe oder so). Dann waeren die attributnamen ja mit typ gespeichert, was irgendwie sinnfrei waere, oder? ZB attribut “haircolor_red”
Deshalb idee mit der map. Stimmt aber, string string ist besser.
Zu den streams… hm… das klingt so toll… aber ich hab mich noch (glaube ich) nicht damit beschäftigt. Wie benutze ich denn streams und predicates zum iterieren und warum muss das sein?
@Marco13 : hast recht, so einfach wird das nicht.
Der ansatz “maximaler infornationsgewinn” impliziert ja das jederzeit bekannt sein muss, welche frage wie viel % “wegmachen” wuerde. Also dauerhafte iteration oder was? Mehrere threads?

@keineahnungwer: titel passt nichts. Hat null mit opengl zu tun

5

Bietet es sich nicht an, die Informationen in einer Datenbank zu halten und die schon bekannten Parameter einfach als Bedingung der Abfrage zu formulieren?

So nach dem Motto

[sql]select * from Leute
where haircolor = “red”
and living = 0
and artist = 1;
[/sql]

6

Ja und dann muss die db jedesmall alle eintraege durchlaufen? Das waere ja zieemlich sehr uneffizient.

7

die ersten n Fragen kann man ganz allgemein stellen wie sie auch jeder Mensch überlegt,
Mann/ Frau usw. da denkt keiner an Aussortieren bestimmter Gruppen, nur erstmal Finden einer Grundgruppe

ob ein Computer als Fragesteller immer gnadenlos die einmal analysiert 5 wichtigsten Fragen in gleicher Reihenfolge stellt (je nach Antwort geringfügige Abweichung für Folgefragen)
oder einfach beliebige 5 wichtige Fragen, das sei dahingestellt,
vielleicht auch nicht nur wichtige am Anfang sonder immer mal Sonder-Fragen ins Blaue einbauen,
ist das mathematische Optimum das Ziel oder ein interessantes Spiel?

ein wenig Analyse ist aber auch nicht falsch, 5 Fragen kann schon auf eine einzelne Person führen,
oder, wenn immer die allgemeinste Antwort, vielleicht immer noch 10% des Bestandes ausmachen und weitere allgemeine Fragen lohnend,

also der Computer könnte für die wichtigen Kategorien grob hinterlegt haben:
Mann=30%/ Frau=70%, tot=40%/ lebend=60% und aus Antworten auf wichtige Fragen eine Schäzung multiplizieren,

erst wenn man bei einer kleinen Gruppe ist, 1000 von den angenommenten 100.000,
dann die DB-Abfrage oder jedenfalls erster Durchlauf des Datenbestandes, in welcher Form auch immer,

danach sollte es nicht mehr große Rolle spielen, diese kleine Menge nun bei jeder Frage einzeln im Speicher zu durchlaufen und zu filtern,

wobei das bei 100.000 auch kein wirkliches Thema ist, nicht bei einem Programm mit User-Interaktion,
100.000 sind schneller durchlaufen als die Hand deutlich von der Enter-Taste entfernt

wie die Werte abgelegt sind macht auch nicht viel aus,
bei Ja/ Nein fragen lohnt sich durchaus das simple Taggen,
aus ‘rote Haarfarbe? -> nein’ auf das Attribut Haarfarbe und Ausschluss des bestimmten Wertes rot zu kommen ist evtl. aufwendig,
jedenfalls aufwendiger als einen bestimmten Tag wie beliebige andere zu behandeln,

kann Index-Möglichkeiten, Wahrscheinlichkeiten-Multiplikation usw. betreffen, einheitliche Liste von 100 beliebigen Tags reizvoll

andersrum muss man dann aber auf zusammengehörige Fragen achten:
wenn ‘rote Haarfarbe? -> ja’ bekannt ist, lohnt es sich nicht mehr nach schwarzer Haarfarbe zu fragen,

wer entsprechendes schon mal umgesetzt hat könnte bestimmt etwas beitragen zu den Varianten,
aber das Glück zeigt sich hier wohl nicht, dann einfach was aussuchen…

8

Ich werds eben mal ausprobieren.
Abgesehen davon; dass ich sowieso nieas auf 100.000 eintraege kommen werde ^^

Ich hab aber eben immer diesen tick, zu denken, “jaa und was mach ich bei 100000000 datensaetzen? Da geht das so nicht mehr…”
Manchmal ist das hilfreich,anchmal nur ein schuss in die eigenen beine… naja

Danke euch fuer die Denkansaetze ^^

9

Datenbanken (zumindest gute) sind dahingehend aber hochgradig optimiert. Ich bezweifle, dass das so einfach besser nachzuprogrammieren ist.

10

naja, paar tausend Elemente sind in jeder Programmiersprache schon mehr als ein paar Mal zu durchlaufen
eh eine DB-Nachricht zusammengestellt und überhaupt von Java an das Betriebssystem übermittelt ist,
von Netzwerk-Übertragung, DB-Reaktion darauf, Ausführung und Datenzusammenstellung, Rückantwort usw. ganz abgesehen :wink:

(alles nur behauptet)