Logo
Unionpedia
Kommunikation
Jetzt bei Google Play
Neu! Laden Sie Unionpedia auf Ihrem Android™-Gerät herunter!
Frei
Schneller Zugriff als Browser!
 

Spiel-Komplexität

Index Spiel-Komplexität

In der kombinatorischen Spieltheorie gibt es mehrere Möglichkeiten die Spiel-Komplexität zu messen.

45 Beziehungen: Amazonen (Spiel), Arimaa, Asymptotische Analyse, Aviezri Fraenkel, Backgammon, Claude Shannon, Connect6, Dame (Spiel), David Eppstein, DSPACE, Endlicher Automat, EXPTIME, Extensivform eines Spiels, Fanorona, Fünf in eine Reihe, Go (Spiel), Halma, Hex (Spiel), Infimum und Supremum, International Computer Games Association, Janggi, Kombinatorische Spieltheorie, Komplexitätsklasse, Komplexitätstheorie, Landau-Symbole, Lines of Action, Liste von Komplexitätsklassen, Logarithmus, Mühle (Spiel), Minesweeper, Minimax-Algorithmus, Othello (Spiel), Oware, Pentomino, PSPACE, Qubic, Quoridor, Schach, Shōgi, Sim (Spiel), Tic-Tac-Toe, Victor Allis, Vier gewinnt, Xiangqi, 50-Züge-Regel.

Amazonen (Spiel)

Das Spiel der Amazonen (oftmals kurz Amazonen genannt) ist ein abstraktes strategisches Brettspiel für zwei Spieler, das der Argentinier Walter Zamkauskas 1988 erfunden hat.

Neu!!: Spiel-Komplexität und Amazonen (Spiel) · Mehr sehen »

Arimaa

Arimaa ist ein strategisches Brettspiel für 2 Spieler, entwickelt von Omar Syed, einem indisch-amerikanischen Informatiker mit Spezialisierung auf künstliche Intelligenz.

Neu!!: Spiel-Komplexität und Arimaa · Mehr sehen »

Asymptotische Analyse

In der Mathematik und ihren Anwendungen bezeichnet asymptotische Analyse (auch asymptotische Analysis) einerseits eine Methode, um das Grenzverhalten von Funktionen oder Folgen zu klassifizieren, indem man nur den wesentlichen Trend des Grenzverhaltens beschreibt, andererseits aber auch die zugrundeliegende Theorie als Ganzes.

Neu!!: Spiel-Komplexität und Asymptotische Analyse · Mehr sehen »

Aviezri Fraenkel

Aviezri Siegmund Fraenkel (* 7. Juni 1929 in München) ist ein israelischer Mathematiker, der sich insbesondere mit kombinatorischer Spieltheorie befasst.

Neu!!: Spiel-Komplexität und Aviezri Fraenkel · Mehr sehen »

Backgammon

Modernes Backgammonbrett Moderner Backgammontisch Transparente Präzisionswürfel aus Celluloseacetat mit abgerundeten Kanten (''ball cornered'') Backgammon ist ein Brettspiel und eine Mischung aus Strategie- und Glücksspiel, es gehört zu den Wurfzabel-Spielen, einer der ältesten Brettspielefamilien der Welt.

Neu!!: Spiel-Komplexität und Backgammon · Mehr sehen »

Claude Shannon

Claude Shannon (um 1963) Claude Elwood Shannon (* 30. April 1916 in Petoskey, Michigan; † 24. Februar 2001 in Medford, Massachusetts) war ein US-amerikanischer Mathematiker und Elektrotechniker.

Neu!!: Spiel-Komplexität und Claude Shannon · Mehr sehen »

Connect6

Connect6 ist ein modernes abstraktes strategisches Brettspiel für zwei Personen.

Neu!!: Spiel-Komplexität und Connect6 · Mehr sehen »

Dame (Spiel)

Startposition für Dame auf dem 8×8-Spielbrett Startposition für Dame auf dem 10×10-Spielbrett Dame ist ein strategisches Brettspiel für zwei Spieler und wird auf einem Schachbrett mit 8×8 oder international 10×10 Feldern gespielt.

Neu!!: Spiel-Komplexität und Dame (Spiel) · Mehr sehen »

David Eppstein

David Eppstein (* 1963) ist ein US-amerikanischer Informatiker und Mathematiker.

Neu!!: Spiel-Komplexität und David Eppstein · Mehr sehen »

DSPACE

Der Begriff DSPACE stammt aus der Komplexitätstheorie in der theoretischen Informatik.

Neu!!: Spiel-Komplexität und DSPACE · Mehr sehen »

Endlicher Automat

Abbildung 1: Beispiel eines EA, der eine Tür beschreibt Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat;, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.

Neu!!: Spiel-Komplexität und Endlicher Automat · Mehr sehen »

EXPTIME

Zusammenhang mit anderen Komplexitätsklassen In der Komplexitätstheorie steht EXPTIME (manchmal auch nur EXP) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine (DTM) in durch \mathcal O\left(2^\right) beschränkter Zeit entschieden werden können.

Neu!!: Spiel-Komplexität und EXPTIME · Mehr sehen »

Extensivform eines Spiels

Spielbaum mit zwei einelementigen Informationsmengen Die Extensivform eines Spiels, kurz Extensivform, ist in der Spieltheorie eine Darstellungsform von Spielen, die im Gegensatz zur Normalform eines Spiels die zeitliche Abfolge von Entscheidungen berücksichtigt und hierzu eine Spielbaum genannte Baumdarstellung verwendet.

Neu!!: Spiel-Komplexität und Extensivform eines Spiels · Mehr sehen »

Fanorona

Fanorona ist ein Brettspiel aus Madagaskar und wurde von Alquerque abgeleitet.

Neu!!: Spiel-Komplexität und Fanorona · Mehr sehen »

Fünf in eine Reihe

Fünf in eine Reihe ist ein klassisches Strategiespiel, das in vielen Ländern der Erde bekannt ist.

Neu!!: Spiel-Komplexität und Fünf in eine Reihe · Mehr sehen »

Go (Spiel)

ごばん) genannt. Go (japanisch igo; koreanisch baduk; wörtlich „Umzingelungsspiel“) ist ein Brettspiel für zwei Spieler und gilt als das komplexeste aller weltweit bekannten Strategiespiele.

Neu!!: Spiel-Komplexität und Go (Spiel) · Mehr sehen »

Halma

Quadratisches Spielbrett für 2 und 4 Spieler Halma-Brettspiel um 1900 Zwei Kinder mit einem Sternhalma-Spiel (1942) Halma ist ein Brettspiel für bis zu sechs Personen.

Neu!!: Spiel-Komplexität und Halma · Mehr sehen »

Hex (Spiel)

Hex-Brett mit 11 mal 11 Feldern Hex ist ein strategisches Brettspiel, das von Piet Hein, einem dänischen Dichter und Mathematiker, erfunden wurde.

Neu!!: Spiel-Komplexität und Hex (Spiel) · Mehr sehen »

Infimum und Supremum

Die Bildmenge der abgebildeten Funktion ist beschränkt, damit ist auch die Funktion beschränkt. In der Mathematik treten die Begriffe Supremum und Infimum sowie kleinste obere Schranke bzw.

Neu!!: Spiel-Komplexität und Infimum und Supremum · Mehr sehen »

International Computer Games Association

Die International Computer Games Association (kurz: ICGA) ist eine internationale Vereinigung, die sich mit unterschiedlichen Aspekten der Künstlichen Intelligenz befasst.

Neu!!: Spiel-Komplexität und International Computer Games Association · Mehr sehen »

Janggi

Janggi-Partie in Seoul Janggi (auch Changgi) ist die nationale Schachvariante Koreas.

Neu!!: Spiel-Komplexität und Janggi · Mehr sehen »

Kombinatorische Spieltheorie

Kombinatorische Spieltheorie ist ein von John Horton Conway ca.

Neu!!: Spiel-Komplexität und Kombinatorische Spieltheorie · Mehr sehen »

Komplexitätsklasse

Komplexitätsklassen In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands.

Neu!!: Spiel-Komplexität und Komplexitätsklasse · Mehr sehen »

Komplexitätstheorie

Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen.

Neu!!: Spiel-Komplexität und Komplexitätstheorie · Mehr sehen »

Landau-Symbole

Landau-Symbole (auch O-Notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben.

Neu!!: Spiel-Komplexität und Landau-Symbole · Mehr sehen »

Lines of Action

LOA-Brett Lines of Action (LOA) ist ein Brettspiel in der Rubrik abstraktes Strategiespiel für zwei Spieler vom Spieleautor Claude Soucie.

Neu!!: Spiel-Komplexität und Lines of Action · Mehr sehen »

Liste von Komplexitätsklassen

Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden.

Neu!!: Spiel-Komplexität und Liste von Komplexitätsklassen · Mehr sehen »

Logarithmus

Logarithmische Skaleneinteilung eines Rechenschiebers (Detail) e (rot) und 1/2 (blau) Logarithmus zur Basis 10. Als Logarithmus (Plural: Logarithmen; von, „Verständnis, Lehre, Verhältnis“, und ἀριθμός, arithmós, „Zahl“) einer Zahl bezeichnet man den Exponenten, mit dem eine vorher festgelegte Zahl, die Basis, potenziert werden muss, um die gegebene Zahl, den Numerus, zu erhalten.

Neu!!: Spiel-Komplexität und Logarithmus · Mehr sehen »

Mühle (Spiel)

Spielbrett Mühle, in der Schweiz auch Nünistei („neun Steine“) genannt, ist ein Brettspiel für zwei Spieler.

Neu!!: Spiel-Komplexität und Mühle (Spiel) · Mehr sehen »

Minesweeper

Bildschirmfoto des Minesweeper-Klons KMines Minesweeper (englisch mine sweeper: „Minenräumer“) ist ein simples, dem Betriebssystem Microsoft Windows bis einschließlich der Version Windows 7 beigelegtes Computerspiel, bei dem Spieler durch eine Kombination aus logischem Denken und (bisweilen) zufälligem Raten herausfinden sollen, unter welchen Feldern Minen versteckt sind.

Neu!!: Spiel-Komplexität und Minesweeper · Mehr sehen »

Minimax-Algorithmus

Der Minimax-Algorithmus ist ein Algorithmus, der im Bereich der künstlichen Intelligenz und der Spieltheorie verwendet wird.

Neu!!: Spiel-Komplexität und Minimax-Algorithmus · Mehr sehen »

Othello (Spiel)

Othello und Reversi sind zwei eng verwandte strategische Brettspiele für zwei Personen.

Neu!!: Spiel-Komplexität und Othello (Spiel) · Mehr sehen »

Oware

Owarebrett aus Osese-Holz (''Holarrhena floribunda'') mit Samen der Molukkenbohne (''Caesalpinia bonduc'') Akan-Gewicht zum Wiegen von Goldstaub – Awele/Awari-Spiel Oware ist ein abstraktes Strategiespiel der Mancala-Familie, das in Westafrika und auf manchen karibischen Inseln gespielt wird.

Neu!!: Spiel-Komplexität und Oware · Mehr sehen »

Pentomino

Die 12 Pentominos Pentomino (auch Pentamino) ist ein Polyomino der Ordnung 5, d. h.

Neu!!: Spiel-Komplexität und Pentomino · Mehr sehen »

PSPACE

In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können.

Neu!!: Spiel-Komplexität und PSPACE · Mehr sehen »

Qubic

Qubic ist ein Brettspiel für zwei Spieler.

Neu!!: Spiel-Komplexität und Qubic · Mehr sehen »

Quoridor

Quoridor ist ein Strategiespiel für zwei oder vier Personen von Mirko Marchesi.

Neu!!: Spiel-Komplexität und Quoridor · Mehr sehen »

Schach

Schachspiel in der Grundstellung Eine mögliche Matt­stellung (Unsterbliche Partie) Schach (von – daher die Bezeichnung „das königliche Spiel“) oder Schachspiel ist ein strategisches Brettspiel, bei dem zwei Spieler abwechselnd Spielsteine (die Schachfiguren) auf einem Spielbrett (dem Schachbrett) bewegen.

Neu!!: Spiel-Komplexität und Schach · Mehr sehen »

Shōgi

Kleines Shōgibrett koma) Großes Shōgibrett in Tokio, 2018 Shōgi (japanisch 将棋, veraltet auch: 象戯/象棋/象棊) ist die japanische Variante des Schachspiels.

Neu!!: Spiel-Komplexität und Shōgi · Mehr sehen »

Sim (Spiel)

Spielbrett von Sim Sim ist ein Spiel für zwei Personen.

Neu!!: Spiel-Komplexität und Sim (Spiel) · Mehr sehen »

Tic-Tac-Toe

Tic-Tac-Toe Tic-Tac-Toe oder Drei gewinnt (auch Kreis und Kreuz, Dodelschach) ist ein klassisches, einfaches Zweipersonen-Strategiespiel, dessen Geschichte sich bis ins 12. Jahrhundert v. Chr.

Neu!!: Spiel-Komplexität und Tic-Tac-Toe · Mehr sehen »

Victor Allis

Louis Victor Allis (* 19. Mai 1965 in Gemert) ist ein niederländischer Informatiker, der im Bereich künstliche Intelligenz (KI) tätig ist.

Neu!!: Spiel-Komplexität und Victor Allis · Mehr sehen »

Vier gewinnt

Vier gewinnt (englisch: Connect Four oder Captain's mistress) ist ein Zweipersonen-Strategiespiel mit dem Ziel, als Erster vier der eigenen Spielsteine in eine Linie zu bringen.

Neu!!: Spiel-Komplexität und Vier gewinnt · Mehr sehen »

Xiangqi

Xiangqi-Brett mit Startaufstellung der Figuren Xiangqi, das chinesische Schach, ist eine in Ostasien, vor allem in China, Taiwan und Vietnam verbreitete Form des Schachspiels, die seit dem 9. Jahrhundert existiert.

Neu!!: Spiel-Komplexität und Xiangqi · Mehr sehen »

50-Züge-Regel

Die 50-Züge-Regel beim Schach besagt, dass eine Partie als remis (unentschieden) zu werten ist, wenn einer der beiden Spieler nachweist, dass in den letzten 50 aufeinanderfolgenden Zügen eines Spielers, das heißt 100 Halbzügen, weder ein Stein geschlagen noch ein Bauer gezogen wurde.

Neu!!: Spiel-Komplexität und 50-Züge-Regel · Mehr sehen »

Leitet hier um:

Zustandsraum-Komplexität.

AusgehendeEingehende
Hallo! Wir sind auf Facebook! »