CSC D84 - Artificial Intelligence

Assignment 2 - MiniMax and Game Trees

This assignment is worth:

10 AIUs (Artificial Intelligence Units)
toward the assignment component of your final
mark.

________________________________________________

Student Name 1 (last, first): Hongming, Li

Student Name 2 (last, first): Diego, He

Student number 1: 1004135624

Student number 2: 1004264547

UTORid 1: lihongm2

UTORid 2: hediego

READ THIS AND SIGN YOUR NAME AT THE END:

I certify that I have read the UTSC code on academic
honesty and plaguarism. All work submitted as part
of this assignment is my own.

Signed: _Hongming Li__ _Diego He__

(-5 marks for failing to provide the identifying
information requested above)
________________________________________________

Answer the following questions. Be concise and clear
but explain carefully when needed.

1 .- (5 marks) Explain the design of your utility function.
Describe all the factors that influence its value, and
how their influence was evaluated and integrated into
a single, meaningful value. Convince us that your utility
makes sense!

Factors:
- Closest cheese location
* BFS when distance to the cheese location is close
(e.g. when manhattan distance <8).
* Otherwise, use manhanttan distance.

* WHY: BFS search is used when Manhattan distance is short to calculate for
the actual path to the cheese has obvious advantage, it allows the mouse to
avoid getting tricked by the manhanttan distance and choose a path that is
short in manhanttan distance but long in actual path distance(e.g. blocked
by a long wall). However, when the Manhanttan distance is far, we just take the
Manhanttan distance. There is no obvious difference, because the general direction
that Manhanttan distance give is correct for most cases. Using Manhanttan distance
reduces the computational cost.

- Cat total distance
* calcuated the formula cat_total_distance = sum((size_Y + size_X) / dist[i]),
where i is the id of the cat.

* WHY: Cat total distance takes all cat's distance into consideration, by summing up
all the cat's distance to the mouse. However, each cat's impact on the utility funciton is
weighted based on how close it is to the mouse. The closer the cat is to the mouse the
more impactful the cat is to the utility function. This avoids the situation,
when only one cat is very close, but threat of the close cat is averaged down
by the other far-away cats. We achieve the weighted utility by dividing the distance.

- Default value for utility for the following cases:
* Any cat location is equal to mouse location. Default value set to -#cats*64 (negative max)
* Any cheese location is equal to mouse location. Default value set to #cats*64 (positive max)
* If mouse run into a deadend(i.e. srounded by three walls).Default value set to -#cats*64(negative Max)
Note:64 here is actually SIZE_X + SIZE_Y

*WHY: The default values positive or negative max corresponds to the ultimate
winning utility value of mouse and cats. This allows the mouse to avoid these
extreme cases or go for the cheese when the cheese is nearby

- Depth
* If Minimax value are equal, we priorities the one with
the lower depth.

WHY: It reduces the chance that our algorithm gets stuck that it goes
back and forth between two positions that have the same utility values.

We use the following final utility function:
((((size_X + size_Y)*cats)/(min_dist)) - cat_total_dist) / depth;
Where size_Y + size_X = 64

The former part of the equation (size_X + size_Y)*cats)/(min_dist) calculates
the positive utility of the mouse, it gets very close to positive max(i.e. #cats*64)
when. Similarly, on the cat's side, cat_total_dist approaches to negative max,
when cats get close to mouse(close cats dominate, but also minorly consider far-away cats).

When the mouse is in between a cheese and cats, the two parts of the utility function
is likely to cancel out. Also, designed range of our utility function to be between
-#cats * 64 and #cats * 64 (equal max and min magnitutde). Therefore, our utility function
does not favor either mouse or cats, because we don't want to overesitmate or
underrestimate our opponents. The reason we don't want bias is that if we overrestimate,
we might get stuck in some place and never get to the cheese, and if we underrestimate,
we might easily get caught by the cats with high smartness, we want the mosue to be somewhere
in between.

2 .- (2 marks) Ignoring computation time, what is the effect of
search depth (number of turns) on the chances of the mouse
winning the game.

As the search depth increases, the partial game configuration
that we pass in to the utility function is closer and closer
to the terminal node, thus utility function is able to make
more accurate prediction of value ofthe terminal node. This allows
the mouse to see the future more accurately, and avoid danger
more correctly. Therefore it increases the mouse's chance to
wint the game.

3 .- (2 marks) What situations will cause your mouse to lose?
can these be fixed either with the utility function, or
by changing the search depth? if so, how?

Situation in which the best move for the current mouse to
take is the previous step, so it will go back and forth
with the cat since after moving to the previous step, the
mouse will also move causing the mouse to steek to those
two steps for ever.

4 .- (2 marks) Compare cats with smartness=.8 against cats with
smartness=1 - which are harder for your mouse to beat?
why do you think that is?

The mouse is equally likely to win for these two smartness levels.
However, the difference I notice is that if it is winnable
for smartness=1, it is also winnable for smartness=.8, but it
sometimes take longer time for mouse to win with smartness .8.
Due to the nature of Minimax, it sometimes gets stuck in a circle
of area back and forth to wait for the cats a bit because of the
similar utilities of the area. It is even more obvious when the
smartness level drop even lower. So in conclusion, they are the same
in terms of survivability, but the mouse usually wins faster with
higher smartness level.

5 .- (2 marks) Can the mouse be made unbeatable by having an
optimal utility function?

Having an optimal utility function means that the utility
function is able to make 100% correct prediction of the value
best possible terminal state value that is obtainable based on CSC D84 - Artificial Intelligence

Assignment 2 - MiniMax and Game Trees

This assignment is worth:

10 AIUs (Artificial Intelligence Units)
toward the assignment component of your final
mark.

________________________________________________

Student Name 1 (last, first): Hongming, Li

Student Name 2 (last, first): Diego, He

Student number 1: 1004135624

Student number 2: 1004264547

UTORid 1: lihongm2

UTORid 2: hediego

READ THIS AND SIGN YOUR NAME AT THE END:

I certify that I have read the UTSC code on academic
honesty and plaguarism. All work submitted as part
of this assignment is my own.

Signed: _Hongming Li__ _Diego He__

(-5 marks for failing to provide the identifying
information requested above)
________________________________________________

Answer the following questions. Be concise and clear
but explain carefully when needed.

1 .- (5 marks) Explain the design of your utility function.
Describe all the factors that influence its value, and
how their influence was evaluated and integrated into
a single, meaningful value. Convince us that your utility
makes sense!

Factors:
- Closest cheese location
* BFS when distance to the cheese location is close
(e.g. when manhattan distance <8).
* Otherwise, use manhanttan distance.

* WHY: BFS search is used when Manhattan distance is short to calculate for
the actual path to the cheese has obvious advantage, it allows the mouse to
avoid getting tricked by the manhanttan distance and choose a path that is
short in manhanttan distance but long in actual path distance(e.g. blocked
by a long wall). However, when the Manhanttan distance is far, we just take the
Manhanttan distance. There is no obvious difference, because the general direction
that Manhanttan distance give is correct for most cases. Using Manhanttan distance
reduces the computational cost.

- Cat total distance
* calcuated the formula cat_total_distance = sum((size_Y + size_X) / dist[i]),
where i is the id of the cat.

* WHY: Cat total distance takes all cat's distance into consideration, by summing up
all the cat's distance to the mouse. However, each cat's impact on the utility funciton is
weighted based on how close it is to the mouse. The closer the cat is to the mouse the
more impactful the cat is to the utility function. This avoids the situation,
when only one cat is very close, but threat of the close cat is averaged down
by the other far-away cats. We achieve the weighted utility by dividing the distance.

- Default value for utility for the following cases:
* Any cat location is equal to mouse location. Default value set to -#cats*64 (negative max)
* Any cheese location is equal to mouse location. Default value set to #cats*64 (positive max)
* If mouse run into a deadend(i.e. srounded by three walls).Default value set to -#cats*64(negative Max)
Note:64 here is actually SIZE_X + SIZE_Y

*WHY: The default values positive or negative max corresponds to the ultimate
winning utility value of mouse and cats. This allows the mouse to avoid these
extreme cases or go for the cheese when the cheese is nearby

- Depth
* If Minimax value are equal, we priorities the one with
the lower depth.

WHY: It reduces the chance that our algorithm gets stuck that it goes
back and forth between two positions that have the same utility values.

We use the following final utility function:
((((size_X + size_Y)*cats)/(min_dist)) - cat_total_dist) / depth;
Where size_Y + size_X = 64

The former part of the equation (size_X + size_Y)*cats)/(min_dist) calculates
the positive utility of the mouse, it gets very close to positive max(i.e. #cats*64)
when. Similarly, on the cat's side, cat_total_dist approaches to negative max,
when cats get close to mouse(close cats dominate, but also minorly consider far-away cats).

When the mouse is in between a cheese and cats, the two parts of the utility function
is likely to cancel out. Also, designed range of our utility function to be between
-#cats * 64 and #cats * 64 (equal max and min magnitutde). Therefore, our utility function
does not favor either mouse or cats, because we don't want to overesitmate or
underrestimate our opponents. The reason we don't want bias is that if we overrestimate,
we might get stuck in some place and never get to the cheese, and if we underrestimate,
we might easily get caught by the cats with high smartness, we want the mosue to be somewhere
in between.

2 .- (2 marks) Ignoring computation time, what is the effect of
search depth (number of turns) on the chances of the mouse
winning the game.

As the search depth increases, the partial game configuration
that we pass in to the utility function is closer and closer
to the terminal node, thus utility function is able to make
more accurate prediction of value ofthe terminal node. This allows
the mouse to see the future more accurately, and avoid danger
more correctly. Therefore it increases the mouse's chance to
wint the game.

3 .- (2 marks) What situations will cause your mouse to lose?
can these be fixed either with the utility function, or
by changing the search depth? if so, how?

Situation in which the best move for the current mouse to
take is the previous step, so it will go back and forth
with the cat since after moving to the previous step, the
mouse will also move causing the mouse to steek to those
two steps for ever.

4 .- (2 marks) Compare cats with smartness=.8 against cats with
smartness=1 - which are harder for your mouse to beat?
why do you think that is?

The mouse is equally likely to win for these two smartness levels.
However, the difference I notice is that if it is winnable
for smartness=1, it is also winnable for smartness=.8, but it
sometimes take longer time for mouse to win with smartness .8.
Due to the nature of Minimax, it sometimes gets stuck in a circle
of area back and forth to wait for the cats a bit because of the
similar utilities of the area. It is even more obvious when the
smartness level drop even lower. So in conclusion, they are the same
in terms of survivability, but the mouse usually wins faster with
higher smartness level.

5 .- (2 marks) Can the mouse be made unbeatable by having an
optimal utility function?

Having an optimal utility function means that the utility
function is able to make 100% correct prediction of the value
best possible terminal state value that is obtainable based on
the current partial game configuration. Therefore, it is possible
that the game configuration is just unwinnable from the start
(i.e. the utility function returns negative value at the
root of the game tree) In this situation, the mouse is not unbeatable
even with an optimal utility function.

6 .- (2 bonus marks) Could a human playing the game in place
of the mouse do better than your code? (yes, no, and
a reasonable explanation of why)

Yes, assuming the human is a professional gamer at this
game with exceptional reaction speed, then the human is
very likely to perform better than our mouse. The reson
is simple since a human is able to see the whole maze
and able to avoid steps such that will make the mouse to
be reached by the cats. A human is able to see the steps
taken by each cat so it will actually see the patten that
the cats are taking, in which our MIN/MAX is not doing.

_____________________________________________________

Mark with an 'x' where appropriate. If something is only
working partially, briefly describe what works, what
doesn't work, or what problems exist.

Complete/Working Partial Not done

Utility x
function

MiniMax x

Alpha/Beta x
pruning
_____________________________________________________

Marking:

(10 marks) Implemented a non-trivial, clever, and
effective utility function. It allows the
mouse to win the game often.

(10 marks) Correctly implementing MiniMax. The algorithm
should produce the expected behaviour. The
mouse should take a reasonable path to the
cheese and avoid cats. The cats will try to
catch the mouse. Mouse is not easy to catch.

(10 marks) Implemented alpha-beta pruning. The algorithm
significantly reduces the amount of search
while producing identical results as those
from standard MiniMax

(15 marks) Competitive (TA assigned) based on how smart
your mouse is (this is related to your
utility function above!)

(15 marks) Answers in this report file

(2 bonus) Bonus!

Total for A2: / out of 60

the current partial game configuration. Therefore, it is possible
that the game configuration is just unwinnable from the start
(i.e. the utility function returns negative value at the
root of the game tree) In this situation, the mouse is not unbeatable
even with an optimal utility function.

6 .- (2 bonus marks) Could a human playing the game in place
of the mouse do better than your code? (yes, no, and
a reasonable explanation of why)

Yes, assuming the human is a professional gamer at this
game with exceptional reaction speed, then the human is
very likely to perform better than our mouse. The reson
is simple since a human is able to see the whole maze
and able to avoid steps such that will make the mouse to
be reached by the cats. A human is able to see the steps
taken by each cat so it will actually see the patten that
the cats are taking, in which our MIN/MAX is not doing.

_____________________________________________________

Mark with an 'x' where appropriate. If something is only
working partially, briefly describe what works, what
doesn't work, or what problems exist.

Complete/Working Partial Not done

Utility x
function

MiniMax x

Alpha/Beta x
pruning
_____________________________________________________

Marking:

(10 marks) Implemented a non-trivial, clever, and
effective utility function. It allows the
mouse to win the game often.

(10 marks) Correctly implementing MiniMax. The algorithm
should produce the expected behaviour. The
mouse should take a reasonable path to the
cheese and avoid cats. The cats will try to
catch the mouse. Mouse is not easy to catch.

(10 marks) Implemented alpha-beta pruning. The algorithm
significantly reduces the amount of search
while producing identical results as those
from standard MiniMax

(15 marks) Competitive (TA assigned) based on how smart
your mouse is (this is related to your
utility function above!)

(15 marks) Answers in this report file

(2 bonus) Bonus!

Total for A2: / out of 60