Vier gewinnt – Künstliche Intelligenz


Ich denke, es ist höchste Zeit, endlich wieder etwas substanzielleres als Lebenszeichen und Hinweise auf Links abzuliefern. Wer sich noch daran erinnert: Ich hatte zwei Artikel über „Vier gewinnt“ geschrieben, und dabei angedeutet, dass ich auch noch einen Computerspieler abliefern wollte. Nun muss ich gestehen, dass mein Code etwas vermurkst ist, und ich selber nicht genau weiss, ob das nun ordentliches Alpha-Beta-Pruning ist. Das Bemerkenswerte ist aber, dass diese kurze, aber verwirrende Implementierung funktioniert, und zwar so gut, dass ich ziemliche Mühe habe zu gewinnen. Deshalb – und weil ich immer noch auf Geschäftsreise bin – poste ich einfach meinen Frankenstein-Code, hoffe auf ruhigere Zeiten und bete zu den isländischen Vulkangöttern, dass sie mich nächstes Wochenende wieder über den großen Teich nach hause lassen.

case class AI(override val toString: String) extends Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board] = {
    Some(board.move(bestMove(board, coin, 5)._1, coin))
  }

  def bestMove(board: Board, coin: Coin, depth: Int): (Int, Int) = {
    val moveList =  List(3,4,2,5,1,6,0).filter(board(_, 0) == None)
    moveList.foreach(m => if (board.move(m, coin).winner == Some(coin)) return (m,1000000))
    val moves = moveList.sortBy(m => -eval(board.move(m, coin), coin))
    if (moves.isEmpty) (-1,-1000000)
    else if (depth > 0) moves.take(3).map(m => (m, bestMove(board.move(m,coin),
       coin.opposite, depth-1)._2)).sortBy(_._2).head
    else (moves.head, eval(board.move(moves.head, coin), coin))
  }

  def eval(board: Board, coin: Coin):Int = if (coin == Cross) eval(board) else -eval(board)

  def eval(board: Board):Int =
    countPattern(board, Cross).map(evalTable(_)).sum -
    countPattern(board, Naught).map(evalTable(_)).sum

  def evalTable(value: Int) = value match {
    case 4 => 100000
    case 3 => 500
    case 2 => 1
    case _ => 0
  }

  def countPattern(board: Board, coin: Coin) = {
    val rows = for(y <- 0 to 5; x <- 0 to 3) yield List(board(x, y), board(x+1,y), board(x+2,y), board(x+3,y))
    val cols = for(x <- 0 to 6; y <- 0 to 2) yield List(board(x, y), board(x,y+1), board(x,y+2), board(x,y+3))
    val dia1 = for(x <- 0 to 3; y <- 0 to 2) yield List(board(x, y), board(x+1,y+1), board(x+2,y+2), board(x+3,y+3))
    val dia2 = for(x <- 3 to 6; y <- 0 to 2) yield List(board(x, y), board(x-1,y+1), board(x-2,y+2), board(x-3,y+3))
    (rows ++ cols ++ dia1 ++ dia2).map(
      list => if(list.contains(Some(coin.opposite))) 0
              else list.count(_ == Some(coin)))
  }
}

Alle gängigen Algorithmen für solche Spiele beinhalten zwei Funktionen: Eine zum Bewerten einer gegebenen Stellung, und eine zum Vorausberechnung des Stellungsbaums, die dabei auf die erste Funktion zurückgreift. Dabei unterscheiden sich die verschiedenen Versionen darin, welche Züge in welcher Reihenfolge und in welcher Tiefe weiterverfolgt werden, aber das Grundprinzip ist immer gleich: Suche deinen besten Zug unter der Annahme, dass auch dein Gegner immer seinen besten Zug macht.

Bei mir heißt die Bewertungsfunktion eval. Ich habe sie extrem simpel gehalten: Sie zählt einfach, wie oft Muster mit zwei bis vier Steinen eines Spielers (natürlich ohne störende Steine des Gegners) vorkommen und bewertet sie dann. Ein Dreier-Muster ist viel mehr wert als ein Zweier-Muster, und ein Vierer hat einen astronomisch hohen Wert, schließlich gewinnt dieser das Spiel. Das Zählen der Muster wird in countPattern vorgenommen. Natürlich könnten bessere Bewertungs-Faktoren oder eine Einbeziehung der Position des Musters das Programm sicher stark verbessern. Aber gie Güte der Bewertungsfunktion ist eigentlich gar nicht so furchtbar entscheidend, sondern ihre Schnelligkeit: Je schneller eine Stellung bewertet werden kann, um so mehr Züge kann ich untersuchen.

Die Methode bestMove übernimmt die Suche. Zuerst suche ich alle gültigen Züge. Die seltsame Folge 3,4,2… soll dabei bewirken, dass ganz am Anfang die mittleren Felder ein wenig bevorzugt werden. Dann schaue ich nach, ob ich mit einem Zug gewinnen kann. Falls nicht, ordne ich alle Züge mit der Bewertungsfunktion und untersuche nur die „vorläufig besten“ drei (nach Meinung von eval) weiter, und nehme den, der dann beim „Tieferbohren“ durch rekursiven Aufruf von bestMove den besten Wert erhält. Natürlich muss die Rekursion irgenwann abbrechen: In diesem Fall nehme ich einfach den vorläufig besten. Alle Werte habe ich pi-mal-Daumen genommen, schließlich soll man auch eine Gewinn-Chance haben.

An den anderen Dateien habe ich auch etwas gebastelt. Dummerweise kann ich hier keine Archiv-Dateien anhängen, deshalb poste ich den gesamten Code am Stück. Ich weiß, dass das keine so tolle Lösung ist, aber anders geht es momentan leider nicht.

package connectfour

sealed abstract class Coin(override val toString: String) {
   def opposite = this match {
     case Naught => Cross
     case Cross => Naught
   }
}
case object Naught extends Coin("O")
case object Cross extends Coin("X")

class Board private(data: Map[(Int, Int), Coin]) {

  //HashMap wirft in SwingIO völlig unerklärlich eine Exception, 
  //deshalb habe ich hier eine TreeMap genommen
  def this() = this(scala.collection.immutable.TreeMap[(Int,Int), Coin]())

  def move(x: Int, coin: Coin) = {
    val y = (5 to 0 by -1).find(apply(x, _) == None).getOrElse(error("full"))
    new Board(data + ((x,y) -> coin))
  }

  def apply(x: Int, y: Int): Option[Coin] = data.get((x,y))

  override def toString = {
    val sb = new StringBuilder
    for(y <- 0 to 5; x <- 0 to 6)
      sb.append(apply(x, y).getOrElse(".")).append(if (x == 6) "\n" else "|")
    sb.append("0 1 2 3 4 5 6\n").toString
  }

  lazy val isFull = (0 to 6).forall(apply(_, 0) != None)

  lazy val winner: Option[Coin] = {
    val rows = for(y <- 0 to 5) yield for(x <- 0 to 6) yield apply(x, y)
    val cols = for(x <- 0 to 6) yield for(y <- 0 to 5) yield apply(x, y)
    val dia1 = for(x <- -2 to 3) yield for(y <- 0 to 5) yield apply(x+y, y)
    val dia2 = for(x <- 3 to 8 ) yield for(y <- 0 to 5) yield apply(x-y, y)
    val list = rows ++ cols ++ dia1 ++ dia2
    List(Cross, Naught).find{ c =>
      val slice = List.fill(4)(Some(c))
      list.exists(_.containsSlice(slice))
    }
  }
}

object ConnectFour {

  def apply(io:IO) {
    def loop(players: Option[(Player, Player)]) {
      val (player1, player2) = players.getOrElse(io.askForPlayers)
      round(player1, player2, io)
      if(io.askKeepPlaying) {
        loop(if (io.askKeepPlayers) Some(player2, player1) else None)
      } else {
        io.exit()
      }
    }
    loop(None)
  }

  def round(player1: Player, player2: Player, io:IO) {

    def play(board: Board, player: Player) {
      val coin = if (player == player1) Cross else Naught
      io.showBoard(board)
      if(board.winner != None) io.announceWinner(
        if (board.winner.get == Cross) player1 else player2, board.winner.get)
      else if (board.isFull) io.announceDraw()
      else {
        io.announceMove(player, coin)
        player.move(board, coin, io) match {
          case None => io.announceResign(player, coin)
          case Some(b) => play(b, if(player == player1) player2 else player1)
        }
      }
    }

    play(new Board(), player1)
  }
}

trait IO {
  def showBoard(board: Board): Unit
  def announceWinner(player: Player, coin: Coin): Unit
  def announceDraw(): Unit
  def announceResign(player: Player, coin: Coin): Unit
  def announceMove(player: Player, coin: Coin): Unit
  def askForHumanMove(board: Board): Option[Int]
  def askForPlayers: (Player, Player)
  def askKeepPlaying: Boolean
  def askKeepPlayers: Boolean
  def exit(): Unit
}

case object ConsoleIO extends IO {

  import Console._

  def showBoard(board: Board) {
    println(board)
    println
  }
  def announceWinner(player: Player, coin: Coin) {
    println("The winner is " + player + " (" + coin + ")")
  }
  def announceDraw() {
    println("Board is full, draw.")
  }
  def announceResign(player: Player, coin: Coin) {
    println("Player " + player + " (" + coin + ") gives up.")
  }
  def announceMove(player: Player, coin: Coin) {
    println(player + "'s move (" + coin + ")")
  }

  private val scanner = new java.util.Scanner(System.in)

  def askForHumanMove(board: Board): Option[Int] = {
    var m = -1
    var giveup = false
    do {
      println("Your move ('q' for resign)?")
      try {
        val s = scanner.next
        if(s == "q") giveup = true else m = Integer.parseInt(s)
      } catch {
        case _ =>
      }
    } while(!giveup && (m < 0 || m >= 7 || board(m, 0) != None))
    if(giveup) None else Some(m)
  }

  def askKeepPlaying = {
    var s = ""
    do {
      println("Play again (y/n)?")
      s = scanner.next.toLowerCase
    } while(s != "y" && s != "n")
    s == "y"
  }

  def askKeepPlayers = {
    var s = ""
    do {
      println("Keep players (y/n)?")
      s = scanner.next.toLowerCase
    } while(s != "y" && s != "n")
    s == "y"
  }

  def askForPlayers: (Player, Player) = {
    def ask(number: String): Player = {
      var s = ""
      do {
        println("Is the " + number + " player human or computer (h/c)?")
        s = scanner.next.toLowerCase
      } while(s != "h" && s != "c")
      if(s == "c") {
        println("Please enter the name of the " + number + " player:")
        AI(scanner.next)
      } else {
        println("Please enter the name of the " + number + " player:")
        Human(scanner.next)
      }
    }
    return (ask("first"), ask("second"))
  }

  def exit() { /* do nothing */ }
}

case object SwingIO extends IO {

  import scala.swing._
  import scala.swing.event._
  import scala.swing.Swing._

  val frame = new MainFrame {
    title = "Connect Four"
    size = new java.awt.Dimension(500, 400)
    location = new java.awt.Point(50, 50)
    visible = true

    val messageLabel = new Label("Welcome to Connect Four!")
    val connectFourPanel =   new GridPanel(6,7) {
      var board = new Board()
      for(y <- 0 to 5; x <- 0 to 6) contents += new CoinComp(x, y)

      class CoinComp(x: Int, y: Int) extends Component {
        preferredSize = new Dimension(80, 80)

        import java.awt.Color._
        border = LineBorder(BLACK)
        override def paintComponent(g: Graphics2D) {
          g.setRenderingHint(java.awt.RenderingHints.KEY_ANTIALIASING,
                             java.awt.RenderingHints.VALUE_ANTIALIAS_ON)
          g.setColor(GRAY)
          g.fillRect(0, 0, size.width - 1, size.height - 1)
          g.setColor{board(x, y) match {
              case None => WHITE.darker
              case Some(Naught) => ORANGE
              case Some(Cross) => RED.darker
            }}
          val delta = size.width / 7
          g.fillOval(delta, delta, size.width - 2*delta, size.height - 2*delta)
          g.setColor(BLACK)
          g.drawOval(delta, delta, size.width - 2*delta, size.height - 2*delta)
        }
      }
    }
    val moveButtons = (1 to 7).map(n => new Button(n.toString){ enabled = false }).toList
    moveButtons.foreach(listenTo(_))
    val resignButton = new Button("Resign"){ enabled = false }
    listenTo(resignButton)

    val mainPanel = new BorderPanel {
      import BorderPanel.Position._
      layout += new BoxPanel(scala.swing.Orientation.Horizontal){
        contents += HStrut(5)
        contents += messageLabel
        contents += HGlue
        contents += resignButton
      } -> North
      layout += connectFourPanel -> Center
      layout += new GridPanel(1,7) { moveButtons.foreach(contents += _) } ->  South
    }
    contents = mainPanel

    val clickedButton = new scala.concurrent.SyncVar[AbstractButton]

    reactions += {
      case ButtonClicked(b) => clickedButton.set(b)
    }

    def updateBoard(board :Board) {
      connectFourPanel.board = board
      connectFourPanel.repaint
    }

    def setButtonsEnabled(value: Boolean):Unit = {
      moveButtons.foreach(_.enabled = value)
      resignButton.enabled = value
    }
  }

  private def coinToColor(coin: Coin) = if(coin == Cross) "red" else "yellow"

  def showBoard(board: Board) { frame.updateBoard(board) }

  def announceWinner(player: Player, coin: Coin) {
    frame.messageLabel.text = "The winner is " + player
    Dialog.showMessage(frame.mainPanel , "The winner is " + player + " (" +
                       coinToColor(coin) + ")!", "Congratulations", Dialog.Message.Info)
  }
  def announceDraw() {
    frame.messageLabel.text = "Board is full, draw."
  }
  def announceResign(player: Player, coin: Coin) {
    frame.messageLabel.text = "Player " + player + " gives up."
    Dialog.showMessage(frame.mainPanel , "Player " + player + " (" +
                       coinToColor(coin) + ") gives up.", "Resign", Dialog.Message.Info)
  }
  def announceMove(player: Player, coin: Coin) {
    frame.messageLabel.text = player + "'s move (" + coinToColor(coin) + ")"
  }

  def askForHumanMove(board: Board): Option[Int] = {
    frame.setButtonsEnabled(true)
    var r = Int.MinValue
    do {
      val button = frame.clickedButton.take
      if(button == frame.resignButton) r = Int.MaxValue else {
        val i = frame.moveButtons.indexOf(button)
        if (board(i, 0) == None) r = i
      }
    } while (r == Int.MinValue)
    frame.setButtonsEnabled(false)
    if(r == Int.MaxValue) None else Some(r)
  }

  def askKeepPlaying = Dialog.Result.Yes == Dialog.showConfirmation(
    frame.mainPanel, "Play again?", "Question", Dialog.Options.YesNo, Dialog.Message.Question)

  def askKeepPlayers = Dialog.Result.Yes == Dialog.showConfirmation(
    frame.mainPanel, "Keep players?", "Question", Dialog.Options.YesNo, Dialog.Message.Question)

  def askForPlayers: (Player, Player) = {
    val panel = new BoxPanel(Orientation.Vertical) {
      val name1 = new TextField("Adam")
      val human1 = new CheckBox("human")
      human1.selected = true
      val name2 = new TextField("Eve")
      val human2 = new CheckBox("human")
      human2.selected = true
      contents += new Label("Player 1:")
      contents += name1
      contents += human1
      contents += VStrut(10)
      contents += new Label("Player 2:")
      contents += name2
      contents += human2
    }
    Dialog.showMessage(frame.mainPanel , panel.peer, "Select Players", Dialog.Message.Plain)
    val player1 = if(panel.human1.selected) Human(if(panel.name1.text == "") "Adam" else panel.name1.text)
    else AI((if(panel.name1.text == "") "HAL" else panel.name1.text))
    val player2 = if(panel.human2.selected) Human(if(panel.name2.text == "") "Eve" else panel.name2.text)
    else AI((if(panel.name2.text == "") "R2D2" else panel.name2.text))
    return (player1, player2)
  }

  def exit() {
    frame.close()
    System.exit(0)
  }
}

trait Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board]
}

case class Human(override val toString: String) extends Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board] = 
    io.askForHumanMove(board).map(board.move(_, coin))
}

case class AI(override val toString: String) extends Player {
  def move(board: Board, coin: Coin, io: IO): Option[Board] = {
    Some(board.move(bestMove(board, coin, 5)._1, coin))
  }

  def bestMove(board: Board, coin: Coin, depth: Int): (Int, Int) = {
    val moveList =  List(3,4,2,5,1,6,0).filter(board(_, 0) == None)
    moveList.foreach(m => if (board.move(m, coin).winner == Some(coin)) return (m,1000000))
    val moves = moveList.sortBy(m => -eval(board.move(m, coin), coin))
    if (moves.isEmpty) (-1,-1000000)
    else if (depth > 0) moves.take(3).map(m => (m, bestMove(board.move(m,coin),
       coin.opposite, depth-1)._2)).sortBy(_._2).head
    else (moves.head, eval(board.move(moves.head, coin), coin))
  }

  def eval(board: Board, coin: Coin):Int = if (coin == Cross) eval(board) else -eval(board)

  def eval(board: Board):Int =
    countPattern(board, Cross).map(evalTable(_)).sum -
    countPattern(board, Naught).map(evalTable(_)).sum

  def evalTable(value: Int) = value match {
    case 4 => 100000
    case 3 => 500
    case 2 => 1
    case _ => 0
  }

  def countPattern(board: Board, coin: Coin) = {
    val rows = for(y <- 0 to 5; x <- 0 to 3) yield List(board(x, y), board(x+1,y), board(x+2,y), board(x+3,y))
    val cols = for(x <- 0 to 6; y <- 0 to 2) yield List(board(x, y), board(x,y+1), board(x,y+2), board(x,y+3))
    val dia1 = for(x <- 0 to 3; y <- 0 to 2) yield List(board(x, y), board(x+1,y+1), board(x+2,y+2), board(x+3,y+3))
    val dia2 = for(x <- 3 to 6; y <- 0 to 2) yield List(board(x, y), board(x-1,y+1), board(x-2,y+2), board(x-3,y+3))
    (rows ++ cols ++ dia1 ++ dia2).map(
      list => if(list.contains(Some(coin.opposite))) 0
              else list.count(_ == Some(coin)))
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    ConnectFour(SwingIO)
  }
}

So, das wars für heute. Drückt mir bitte die Daumen für einen vulkanaschewolkenverzögerungsfreien Rückflug!

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s