Workshop Presentation No

Introduksjon til kunstig intelligens og sjakkprogrammering

Hvem er vi og agenda

Hvem er Teodor og Simen?

• Det har dere allerede hørt om.

Agenda

• Kort presentasjon: Introduksjon til kunstig intelligens og sjakkprogrammering
• Litt programmering
• Pizza kommer om 1 time (17:15)
• Mer programmering!
• Uformell turnering og kåring av vinner (19:15)
• Ferdig! (19:45-ish)

En sjakkcomputers anatomi

Hvilke deler finner man i en typisk sjakkcomputer?

• Noe som holder på brettet, noe som beregner et flytt
• Vi konsentrer oss om det som gjør flytt

ai.move = function (board) {
  var chess = new Chess(board),
      moves = chess.moves(),
      move = moves[Math.floor(Math.random() * moves.length)];

  return move;
};

Gjør et trekk

Hvordan gjøre et godt trekk

• Hvordan representere et sjakkspill som et beslutningstre
• Vi regner ut på forhånd! Skalerer ikke, men funker som sluttspilldatabase
• Man kan ikke se på hele treet på en gang

ai.move = function (board) {
    var chess = new Chess(board);

    if(chess.numberOfPieces() <= 5) {
        return Modules.endgame(board);
    } else {
        return SamplePlayers.RndJesus.move(board);
    }
};

Bruk endgame

Heuristikk hele veien hjem

MinMax

• Gå gjennom hvordan MinMax fungerer for et eksempel hvor man kan se på alle muligheter.
• Nevn at det finnes en smart optimalisering som heter Alfa-Beta pruning.
• Hva gjør vi hvis man ikke kan finne alle løsninger? Bruk Heuristikk!

ai.move = function (board) {
    var depth = 2,
        score = function (chess) {
            var playingAsColor = chess.turn();
            return chess.numberOfPieces(playingAsColor);
        };

    return Modules.minmax(board, depth, score);
};

Minmax eksempel

Iterative deepening

• Hva om det er for dyrt å kjøre MinMax på alle "barn"?
• Evaluere og velge ut noen barn som man regner videre på.

ai.move = function (board) {
    var depth = 2,
      score = function (chess) {
          var playingAsColor = chess.turn();
          return chess.numberOfPieces(playingAsColor);
      },
      span = 1;

      return Modules.deepening(board, depth, score, span);
};

Iterative deepening eksempel

Kort om Konkurransen

• Uformell turnering om heder og ære.
• Deadline er ca. 15-20 min før workshopen slutter.
• Her er reglene