CS 410/510 Games: Openings and Endgames

Openings and Endgames

PSU CS410/510GAMES Lecture 6
May 8, 2002

  • Openings
    • Sometimes a good-looking early move goes bad way later
    • In clocked games, want to not waste clock on known positions
    • Human players have (often vast) opening books
    • Computer opening book problems:
      • Human-generated books have bugs: opening traps or ``cooks'' [no learning = repeatable cooks]
      • Human-generated books have commentary and analysis: ``sympathy'' problem of dumping program into not-understood position
      • Strictly ``by the book'' deals poorly with transpositions, falling out of and back into book, irrelevant moves, etc.
        • Transposition table helps: implementation technique is to store book positions irremovably in t-table
          • Would prefer position classes, but...
          • Can explicitly indicate successor, or try to "rig" things by giving bonus in evaluation function for staying in book
      • Sympathy problem means transition to middle game not smooth (why am I here? What's in the t-table?)
    • When are we in middle game?
      • When out of book
      • When significant event happens (e.g. castling, material exchange)
      • When eff. branching factor goes up
  • Endgames
    • When are we in the endgame?
      • When material is small
      • When branching factor becomes large
      • When terminal nodes are reached
    • Traditional endgame approach: programmed knowledge
      • Trades human work for generality
      • ``Theorem Proving'' approach
      • Problem: pattern matching
    • Which endgame positions are reachable? Who knows?
      • Idea: if game is monotonic in material, work backward = ``Retrograde analysis''
      • Dynamic programming technique: explore until conversion
      • Requires huge database (chess 5-piece = 150M positions)
      • Can profitably be calculated in parallel
    • Endgame oddities: chess
      • Discoveries: certain endgames are nonintuitive. Effective consequences?
      • Transition from middle game not always smooth: sacrifice to known (database or heuristic) win