Deep Blue background chess: “the touchstone of the intellect”



Yüklə 447 b.
tarix16.11.2017
ölçüsü447 b.
#10670


Deep Blue


background

  • chess: “the touchstone of the intellect”

  • machine would model thinking, some say

  • chess problem “sharply defined”

  • First chess-playing machine: 1760’s Maezal Chess Automaton



minimax algoritm

  • generate all possible moves by player and opponent a number of steps ahead

  • outcomes generally reside in outermost leaves of trees

  • depth of search -> program rating



limits

  • initially tried to emulate humans

  • human skills: pattern recognition and associative memory

  • engineering approach, relies on computer’s strengths



Tuning Mechanisms

  • hill climbing perform a lookahead search then adjusts the parameter

  • best fit function of machine’s evaluation of positions and the true values



logistics

  • 6 move lookahead: 38^12 = 9 billion billion moves

  • each move lookahead worth about 400 rating points (world champions around 2,900)



Deep Blue features

  • Hsu’s single chip move generator

  • Anantharaman’s singular extension algorithm



Hsu’s “chess machines”



position evaluation

  • separate value for pieces on different squares

  • stored endgame positions

  • position features from grandmasters



alpha-beta search

  • eliminates bad moves from further consideration

  • move ‘refuted’ if opponent can force a worst outcome than the previous estimation



singular extensions

  • horizon problem

  • looks 30 or 60 moves in certain situations, checks or piece exchanges

  • fewer choices, deeper search



Kasparov 2.5 Deep Blue 3.5



Yüklə 447 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə