中国象棋chinese-chess教材教学课件.ppt

References C. Szeto. Chinese Chess and Temporal Difference Learning J. Baxter. KnightCap: A chess program that learns by combining TD(λ) with minimax search T. Trinh. Temporal Difference Learning in Chinese Chess .tw/index.html How to Win a Chinese Chess Game Reinforcement Learning Cheng, Wen Ju Set Up RIVER General Guard Minister Rook Knight Cannon Why Temporal Difference Learning the average branching factor for the game tree is usually around 30 the average game lasts around 100 ply the size of a game tree is 30100 Searching alpha-beta search 3 ply search vs 4 ply search horizon effect quiescence cutoff search Horizon Effect t t+1 t+2 t+3 Evaluation Function feature property of the game feature evaluators Rook, Knight, Cannon , Minister, Guard, and Pawn weight: the value of a specific piece type feature function: f return the current player’s piece advantage on a scale from -1 to 1 evaluation function: Y Y = ∑k=1 to 7 wk * fk TD(λ) and Updating the Weights wi, t+1 = wi, t + a (Yt+1 – Yt)S k=1 to t l t-k? wiYk = wi, t + a (Yt+1 – Yt)(fi, t + l fi, t-1 + l 2fi, t-2 + … + l t-1fi, 1) = 0.01 learning rate –how quickly the weights can change = 0.01 feedback coefficient -how much to discount past values Features Table t f1 f2 f3 f4 f5 f6 ... 5 0 0 -0.5 0 0 0.4 6 0 0 0 0 0 -0.4 7 0 0 0 0 -0.5 0.4 8 0 0 -0.5 0 0.5 -0.4 ... Array of Weights 1.0000 1.0000 0.9987 1.0000 1.0000 1.0101 Example t=5 t=6 t=7 t-8 Final Reward loser if is a draw, the final reward is 0 if the board evaluation is negative, then the final reward is twice the board if the board evaluation is positive, then the final reward is -2 times the board evaluation winner if is a draw, the final reward is 0 if the board evaluation is negative, then the final reward is -2 times the board evaluation if the board evaluation is positive, then the final reward is twice the board evaluation Final Reward the weights are normalized by dividing by the greatest weight any negative weights are set to zer