 |
| chess team |
Thursday, May 1, 2014
How to reach us
Facebook
üBlogger
üSource forage
üDr.el-dosuky
project
presentation (power point)
project description(word)
P E A S
üPerformance
winning the Game
üEnvironment
Chess pieces in chess board
Adversary
üActuators
Screen
üSensor
Camera
mouse
Wednesday, April 30, 2014
O D E S A D
üObservable
Fully observable
üDeterministic
Strategic
üEpisodic
Sequential
üStatic
Semi dynamic
üAgent
Multi agent
üDiscrete
discrete
Formulation
üState
Move chess parts to eat computer parts untle Besieging king
üintial
state
Any
state
üSuccessor function
Top ,
Down , Left , Right , diagonal
üGoal
King
die
üPath cost
Time
, each step cost 1
Alpha–beta pruning algorithm
nAlpha–beta pruning algorithm
nAlpha-Beta Heuristic is a significant enhancement to the minimax search algorithm that eliminates the need to search large portions of thegame tree applying a branch-and- bound technique. Remarkably, it does this without any potential of overlooking a better move . If one already has found a quite good move and search for alternatives, onerefutation is enough to avoid it. No need to look for even stronger refutations. The algorithm maintains two values, alpha and beta . They represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively.
function alphabeta(node, depth, α, β, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
for each child of node
α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
if β ≤ α
break (* β cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
if β ≤ α
break (* α cut-off *)
return β
(* Initial call *) alphabeta(origin, depth, -∞ , +∞ , TRUE)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
for each child of node
α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
if β ≤ α
break (* β cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
if β ≤ α
break (* α cut-off *)
return β
(* Initial call *) alphabeta(origin, depth, -
minmax Searching algorithm
n
nMinmax algorithm
Minimax is an algorithm used to determine thescore in a zero- sum game after a certain number of moves, with best play according to an evaluation function.
The algorithm can be explained like this: In aone-ply search, where only move sequences with length one are examined, the side to move (max player) can simply look at the evaluation after playing all possible moves . The move with the best evaluation is chosen. But for a two-ply search, when the opponent also moves, things become more complicated. The opponent (min player) also chooses the move that gets the best score. Therefore, the score of each move is now the score of the worst that the opponent can do.
Minimax is an algorithm used to determine the
The algorithm can be explained like this: In a
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE)
bestValue := min(bestValue, val);
return bestValue
(* Initial call for maximizing player *) minimax(origin, depth, TRUE)
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE)
bestValue := min(bestValue, val);
return bestValue
(* Initial call for maximizing player *) minimax(origin, depth, TRUE)
Subscribe to:
Posts (Atom)