---
# System prepended metadata

title: Untitled

---

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


