---
# System prepended metadata

title: AI Algos

---

# AI Algos


### Uninformed search (without Heuristic; Optimal; 1 unit cost)
- Breadth First Search: **BFS**/ Queue/FIFO
- Depth First Search: **DFS**/ Stack/LIFO
- **Bidirectional** Search 
    - time complexity reduces compared to BFS

### Informed search (with Heuristic; Non-Optimal; Fast; from NP to P)
- BFS + calc. **Heuristic**(dist. | misplaced no.)
- **Generate and Test** Search (DFS with backtracking; Easiest)
    - Generator (Complete, Non-redundant, Informed)
- **Best First Search** (Open and close queue; Global Search; Greedy: Heuristic only) 
    - Priority Queue (Exploring and selecting best from all)
- **Beam Search** (*Best First Search* + limit the priotity queue to best ***n*** nodes) 
    - Priority Queue (Exploring and selecting best from only n nodes)
    - Space complexity(constant)
    - Optimal solution chances decreases
- Simple **Hill Climbing** Algorithm (Local search Algo; Greedy; No backtrack)
    - *Beam Search* with beam breadth n = 1
    - Problems: Stops at Local maximum, Flat maximum
    - Usage: traveling salesman problem, 8 Queen problem
- **A*** (""**Optimal**""; Open and close queue)
    - *Best First Search* + (Greedy: (cost + Heuristic))

### 2 players Game
- **Min-Max** Algo |[Video](https://www.youtube.com/watch?v=l-hh51ncgDI)|[Article](https://stackabuse.com/minimax-and-alpha-beta-pruning-in-python/)|
    - **+ alpha beta pruning** *(speed-up)*
    - **+ Progressive Deepening** *(Anytime algo)*
    - Usage: Tic Tac Toe, Chess

### RNN 
-  | [Milanote](https://app.milanote.com/1LpGW91FMkD79O/ai-and-reinforcement-learning) | [GSheets](https://docs.google.com/spreadsheets/d/17KNgx5DkxvNNT4pCqJMq_xy2O81TGObkP7a1zalfg3E/edit?usp=sharing) |
- Proximal Policy Optimization ([PPO](https://openai.com/blog/openai-baselines-ppo/))
- Useful Links
    - [stable baselines: Doc](https://stable-baselines.readthedocs.io/en/master/guide/algos.html)
    - [stable baselines: Github](https://github.com/hill-a/stable-baselines)
    - [Self Play](https://openai.com/blog/competitive-self-play/)

### Image Prossesing
- opencv contour+ |[Link](https://www.pyimagesearch.com/2016/02/08/opencv-shape-detection/)|
    - usage: Shape Detector 

```
git clone https://github.com/openai/mujoco-py.git
cd mujoco-py
sudo apt-get update
sudo apt-get install libgl1-mesa-dev libgl1-mesa-glx libosmesa6-dev python3-pip python3-numpy python3-scipy
pip3 install -r requirements.txt
sudo python3 setup.py install
```

[Trees](/@jitesh/trees)

{%hackmd theme-dark %}
