لخّصلي

?Average branching factor of 35.Games are competitive environments, in which agents' goals conflict, giving rise to adversarial search problems.Calculating the optimal decision is infeasible ?Games often have time constraints, so efficiency has an important role Games Assoc.Multiagent environments, each agent must consider the actions of the other agents.Prof. Hanaa Salem Marie Spring 2023/2024 ?Prof. Hanaa Salem Marie Spring 2023/2024 ?At the end of the game, points are awarded to the winning player, and penalties are given to the loser.Prof. Hanaa Salem Marie Spring 2023/2024 ?So : initial state, which specifies how the game is set up at the start ?RESULT(s, a): transition model, which defines the result of a move ?A Assoc.Example: Chess ?Search tree has about 35100 or 10154 Nodes.We first consider games with two players, whom we call MAX and MIN.Games Assoc.Definition of a game as a search problem ?player (s): Defines which player has the move in a state ?ACTIONS(s): Returns the set of legal moves in a state ?TERMINAL -- TEST(s): terminal test or goal test.???????

❑ Multiagent
environments, each agent must
consider the actions of the other
agents.
❑ Games are competitive
environments, in which agents’
goals conflict, giving rise to
adversarial search problems.
A
Assoc. Prof. Hanaa Salem Marie Spring 2023/2024
❑ Games, unlike most of the toy problems, are interesting because
they are too hard to solve.
❑ Example: Chess
▪ Games are often too hard to solve, making them more interesting
▪ Average branching factor of 35.
▪ Games often go to 50 moves by each player.
▪ Search tree has about 35100 or 10154 Nodes.
▪ Calculating the optimal decision is infeasible
▪ Games often have time constraints, so efficiency has an important role
Games
Assoc. Prof. Hanaa Salem Marie Spring 2023/2024
❑ We first consider games with two players,
whom we call MAX and MIN.
❑ MAX moves first, and then they take
turns moving until the game is over.
❑ At the end of the game, points are
awarded to the winning player, and
penalties are given to the loser.
Games
Assoc. Prof. Hanaa Salem Marie Spring 2023/2024
❑ Definition of a game as a search problem
➢ So
: initial state, which specifies how the game is set up at the start
➢ player (s): Defines which player has the move in a state
➢ ACTIONS(s): Returns the set of legal moves in a state
➢ RESULT(s, a): transition model, which defines the result of a move
➢ TERMINAL — TEST(s): terminal test or goal test. States where the game
has ended are called terminal states
➢ UTILITY(s, p): utility function, defines the numeric value in a terminal state
s for player p=» Example: Loss is -1, draw is 0, and win is +1=" zero-sum:
Sum of utility of both players is zero
Games
Assoc. Prof. Hanaa Salem Marie Spring 2023/2024
❑ From the initial state, MAX has nine possible moves.
❑ Play alternates between MAX’s placing an X and MIN’s placing an
O until we reach leaf nodes corresponding to terminal states such
that the player has three in a row, or all the squares are filled.
❑ The number on each leaf node indicates the utility value of the
terminal state from the point of view of MAX; high values are
assumed to be good for MAX and bad for MIN.