Logo

CS 188's Personal Meeting Room - Shared screen with speaker view
Tyler Umansky
27:55
yes
Jack Newsom
27:55
yep
Jonathan Kim
27:56
yes
Joshua Wu
27:57
yes
Luke Cheng
27:57
Ok for me
ssingh17
27:58
yes
Chenyue Cai
27:59
yes
Calvin Wong
28:00
y
Estea
31:52
could you go back to utility quickly?
Estea
32:01
just the last part of last slide
Jonathan Kim
32:26
Slides for today: https://drive.google.com/file/d/1fxTp0EeyDJizuDYc7jjHDRs0eXQaGqAC/view?usp=sharing
Jonathan Kim
32:32
this is the pdf for the slides
Estea
32:41
ty!
Amit Palekar
41:23
The states “utility” is the score associated with that state right?
Joshua Wu
43:04
we technically didnt need to explore the 4 and 6 nodes correct?
Calvin Wong
43:21
alpha beta pruning yee
Amit Palekar
43:25
does this algorithm depend on the fact that the opponent plays optimally
Estea
43:30
can you go over the successor functions?
Julius Tereck
44:34
But if you try to exploit imperfect play, doesn't that open you up to being exploited as well?
Andrew
45:02
yea but you're assuming they aren't good enough to play optimally
Danny Sallurday
45:28
I suppose there would be an extra component of the algorithm to weigh risk/reward against suboptimal opponents
Zackoric
46:31
I thought the ghosts were master minds
Rafael Flores
46:36
gopacman
Mengying Ju
46:54
What
Mengying Ju
47:09
What's the goal test? Eat all the dots? Eat a ghost?
Yewen Zhou
47:19
if the ghost is moving randomly, would the action of pacman be deterministic?
Abayjeet Singh
48:11
I think yeah based on movement of ghosts
Chenyue Cai
48:35
In the case when ghosts are not acting optimally, are we introducing probability in the evaluation?
Vishal Raman
49:10
You could compute expected values of moves to make a choice in that case
Julius Tereck
49:13
I think the policy would be deterministic, but the actual action would random, and depend on the movement of the ghost
Yewen Zhou
51:30
but since the movement of ghosts are random, how would the pacman act based on the actions of ghosts? By introducing probability?
Julius Tereck
52:59
Yeah I think then the policy would be to take the action with the best expected value
Abayjeet Singh
53:24
is it possible for movement of ghosts to complete random? it will be like pseudo random
Calvin Wong
53:55
That's the question of coming up with a function that generates random numbers basically, which is really hard
Calvin Wong
54:03
because how do you define random
Calvin Wong
55:26
but pseudo random yes, depending on what you mean by "random"
Julius Tereck
01:00:11
So how would you do that child ordering?
Carlos Calderon
01:00:37
can you clarify how the ordering improves the algorithm?
Chenyue Cai
01:01:29
why could the intermediate node be wrong when we use <=?
Abayjeet Singh
01:01:54
Can u give an example where ordering improves algo?
Julius Tereck
01:03:13
So if this is only for zero-sum games, where does it fail for non-zero-sum?
Estea
01:03:56
was the v <= 10 the wrong node
Estea
01:04:12
and 0 would've been right
Estea
01:04:13
?
Abayjeet Singh
01:04:58
Got it!!
Jonathan Kim
01:05:02
what if the value of 5 was 1?
Julius Tereck
01:06:19
Ahh okay. So they would have to maximize each others utilities instead of minimizing their own
Calvin Wong
01:06:24
I think ye Estea, but what he was getting at was if there was a smaller value on the right (eg: -1) then we still get 10 as the minimax root value
Jonathan Kim
01:06:26
scratch my question
Calvin Wong
01:06:42
i think
Estea
01:07:02
So intermediate nodes are wrong; wouldn't that make the root node also wrong?
Calvin Wong
01:07:03
but then the true value should've been -1 rathre than 0
Marco Gellecanao
01:07:03
Can you please explain again why the time complexity for minimax with pruning is O(b^(m/2))
Marco Gellecanao
01:07:29
oh ok nevermind then thanks
Calvin Wong
01:07:42
no since we pick the 10 either way
Danny Sallurday
01:07:44
Intermediate nodes would be wrong if they have a value already worse than the root node; the root node stays optimal
Danny Sallurday
01:07:53
Aka right
Estea
01:08:02
k..
Calvin Wong
01:08:10
^ Danny bump
Calvin Wong
01:09:35
So like no matter if we picked the 0 or the -1 as the right value, the top node maximizes so it would always choose the 10 @Estea
Joshua Wu
01:09:53
f
Estea
01:09:54
I see.. hence the pruning?
Danny Sallurday
01:10:02
yes
Estea
01:10:32
Ty @ Calvin & Danny!
Calvin Wong
01:10:44
Yee
Tyler Nunez
01:10:45
F
Calvin Wong
01:10:58
lol f in the chat
Chenyue Cai
01:20:02
are -2 and 9 heuristics? How do we know value if we don’t reach the terminal
Calvin Wong
01:20:38
Yep heuristic estimates
Estea
01:22:08
can't we limit actions using cost
Estea
01:23:19
k..
Yewen Zhou
01:25:25
in this case what if on the board both sides don't have queens anymore? Then the heuristic will stay at 0 right?
Amit Palekar
01:25:33
wait how did he fix the thrashing
Danny Sallurday
01:27:42
So what separates evaluation functions from heuristics ?
Yewen Zhou
01:28:03
how do we know the ghosts are DFS not BFS?
Carlos Calderon
01:28:17
what do you mean “the actual terminal utility comes into play”?
Calvin Wong
01:28:39
Think that means they find the actual value rather than heuristic
Calvin Wong
01:29:05
Fixed the thrashing with a better heuristic
Estea
01:31:03
better heuristic not evaluation function?
Ferdie Taruc
01:31:30
^ the evaluation of the utilities are based on proximity to the dots now, rather than seeing just the dots exist when depth = 2
Calvin Wong
01:31:33
from my understanding they're the same?
Ferdie Taruc
01:31:48
its pretty much the same, you use different heuristics to determine an evaluation function I think
Calvin Wong
01:31:48
not too sure
Estea
01:32:01
i see.. so they r similar
Tyler Umansky
01:33:26
Are lecture recordings posted somewhere yet?