Was sind einige Spiele mit ziemlich einfachen Heuristiken, um Positionen zu bewerten?

Question

Ich unterrichte ein Kind Programmierung, und ich führe derzeit einige grundlegende Konzepte für künstliche Intelligenz ein. Zu Beginn werden wir ein Tic-Tac-Toe-Spiel implementieren, das den gesamten Spielbaum durchsucht und somit perfekt spielt. Sobald wir fertig sind, möchte ich die gleichen Konzepte auf ein Spiel anwenden, das zu viele Positionen hat, um jeden einzelnen zu bewerten, so dass wir eine Heuristik implementieren müssen, um Zwischenpositionen zu bewerten.

Das beste, was ich mir vorstellen konnte, war Dots and Boxes. Es hat den Vorteil, dass ich die Boardgröße beliebig groß einstellen kann, um ihn vom Suchen des gesamten Baumes abzuhalten, und ich kann eine sehr einfache Scoring-Funktion machen, nämlich die Anzahl meiner Boxen minus der Anzahl der gegnerischen Boxen. Unglücklicherweise bedeutet dies, dass für den größten Teil des Beginns des Spiels jede Position gleichwertig mit einer Punktzahl von 0 bewertet wird, da es ziemlich viele Züge dauert, bevor die Spieler anfangen, Boxen zu machen.

Hat jemand bessere Ideen für Spiele? (Oder eine bessere Scoring-Funktion für Punkte und Boxen)?

Answer 1

Wie wäre es mit Reversi? Es hat einen ziemlich schönen Raum von Heuristiken basierend auf Anzahl der Stücke, Anzahl der Kantenstücke und Anzahl der Eckstücke.

Answer 2

Wie wäre es mit dem Start Ihres Dots and Boxes-Spiels mit zufälligen Zeilen, die bereits hinzugefügt wurden. Dies kann Sie schnell in die Action bringen. Du musst nur sicherstellen, dass du das Spiel nicht mit irgendwelchen Boxen startest.

Answer 3

Eine andere Spielwahl könnte Reversi alias Othello sein.

Eine naive Heuristik wäre, einfach die Anzahl der Kacheln zu zählen, die bei jeder gültigen Bewegung gewonnen wurde, und die größte zu wählen. Von dort aus können Sie die Position des Boards bestimmen und für den Gegner gefährlich werden.

Answer 4

Werfen Sie einen Blick auf Go.

• Einfach genug für Kind auf sehr kleinen Brettern.
• Komplexität skaliert unendlich.
• Verfügt über viele verfügbare Dokumente, Algorithmen und Programme, die entweder als Maßstab oder Basis verwendet werden können.

Update: reversi wurde erwähnt, die eine vereinfachte Variante von Go ist. Könnte eine bessere Wahl sein.

Answer 5

Ein Spiel, das Sie in Betracht ziehen können, ist Connect Four. Einfaches Spiel mit einfachen Regeln, aber komplizierter als Tic-Tac-Toe.

Answer 6

Four in a line Hart genug, aber leicht genug, um mit einer einfachen Arbeitsbewertungsfunktion zu kommen, zum Beispiel (Abstand zu vier von meinem längsten Linie - Abstand zu vier von meinem Gegner des längsten Linie)

Answer 7

Wie wäre es Mancala? Nur 6 mögliche Züge pro Runde, und es ist einfach, die resultierende Punktzahl für jeden zu berechnen, aber es ist wichtig, die Antwort des Gegners zu berücksichtigen, und der Spielbaum wird ziemlich schnell groß.

Answer 8

Gomoku ist ein nettes, einfaches Spiel, und Spaß ein AI für zu schreiben.

Answer 9

Checker können Sie mehrere Methoden lehren. Einfache Vorausschau, gründliche Suche nach Best-Case-Worst-Case-Entscheidungen, Unterschiede zwischen kurz- und langfristigen Gewinnen und etwas, woran sie weiterarbeiten könnten, nachdem Sie gelernt haben, was Sie ihnen beibringen wollen.

Persönlich denke ich, dass das letzte Bit das kritischste ist - es gibt natürliche Punkte in der KI-Entwicklung, die gut sind, um zu stoppen, zu sehen, wenn Sie es schlagen können, und dann vertiefen in tiefere KI-Mechanismen. Es hält Ihre Schüler interessiert, ohne fürchterlich frustriert zu sein, und gibt ihnen mehr zu tun, wenn sie das Projekt fortsetzen wollen.

Answer 10

Rubik's Infinity ist ziemlich lustig, es ist ein bisschen wie Connect Four, aber subtil anders. Evauluating eine Position ist ziemlich einfach.

Ich habe ein Perl-Skript zusammengefügt, um es vor einer Weile zu spielen, und musste tatsächlich die Anzahl der Züge verringern, die es aussah, oder es hat mich jedes Mal geschlagen, normalerweise mit ziemlich überraschender Taktik.

Answer 11

In Bezug auf eine bessere Heuristik für Punkte und Boxen, schlage ich vor, Online-Strategie-Anleitungen für das Spiel zu suchen. Die first result auf Google für "Punkte und Boxen-Strategie" ist sehr hilfreich.

Das Wissen, wie man die Kettenregel verwendet, trennt einen OK-Spieler von einem Guten. Zu wissen, wann die Kettenregel gegen Sie wirkt, unterscheidet die besten von den guten.

Answer 12

Ich mag Connect Four wirklich. Sehr einfach mit einem Minimax-Algorithmus zu programmieren. Eine gute Bewertungsfunktion könnte sein:

eval_score = 0 
for all possible rows/lines/diagonals of length 4 on the board: 
    if (#player_pieces = 0) // possible to connect four here? 
     if (#computer_pieces = 4) 
      eval_score = 10000 
      break for loop 
     else 
      eval_score = eval_score + #computer_pieces 
      (less pieces to go -> higher score) 
     end if 
    else if (#player_pieces = 4) 
     eval_score = -10000 
     break for loop 
    end if 
end for 

das Programm verbessern Sie hinzufügen können:

1. Wenn Computer zuerst bewegt, in der mittleren Spalte spielen (dies optimal erwiesen hat)
2. Alpha-Beta Pruning
3. verschieben Bestellung
4. Zobrist Hashes