Next match, our victory awaits.

How about a gaming spree?

Go fish can be moddeled non-determinastically
But it is not the best strategy because it is not actually random. The outcome of a turn is not determined by randomness but because of partial observability(you do not see oponnent hands (unless cheating??!?!?😲😲😲🤯))

Techinically for the same reason drawing from the pile is also deterministic but it is not useful in to model that way in the game, partially because it means having a huge amount of belief states (factorial in the number of cards in the pile) but also because the only way to get information about the positions is to draw them (and then the information is no longer useful)

---Online search---
Searches where you don’t know the transistion system
It can be very useful to use heuristic
It is not guarenteed to find a solution if backtracking is not possible

lets do it again

Uninformed search
Breadth-first search
Examine tree layer by layer
Quality
It is complete
We go systematically through the tree
If there is a solution, we find it
Finds the shortest solution
The one using fewest actions
Good if we don't care about cost
Very bad for memory
Needs a lot of memory
Need an exponential number of states (the last layer)
The more choices per layer, the worse it gets
Slow
As a consequence of the memory
One needs time to use memory
If one needs a lot of memory, one will need more time working with that memory

Uninformed search
1. Breadth-first search
- Complete
- Finds the shallowest solution
- Uses a lot of memory
- Slow
2. Uniform cost search (Dijkstra)
- Expands the node with the lowest total cost
- Always finds the cost-optimal solution
- If the cost of each node is the same it behaves like breadth-first
- Has the same problems as breadth-first
3. Depth-first search
- Check for duplicate states
- Checking duplicate states is not always very easy
- Is way more memory eficient than breadth-first
- Incomplete if the state space is infinite
- Solution may not be cost-optimal
4. Iterative deepening
- Same as depth-first, but with a bound on the max depth that increases at each iteration
- Is complete even if the state space is infinite
- Finds the shallowest solution
- Repeats a lot of work but the repeated work each iteration is very small compared to the new work that has to be done
5. Bidirectional search
Useful when there is only one solution