Skip to content
/ AI Public

Artificial Intelligence. A* Algorithm. Minimax Algorithm and Alpha-Beta pruning

Notifications You must be signed in to change notification settings

AndraRaco/AI

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

33 Commits
 
 
 
 
 
 

Repository files navigation

AI

I. A* Algorithm

1. Search problem

The students are placed in benches in the classroom. One of the students wants to send a written message to other student who is placed somewhere else in the class. Some benches are empty and some children are angry with each other. The message can be passed to the next column only through last two rows. Links: Problem requirement(first problem), Github

2. 8-puzzle

8-Puzzle is a popular puzzle that consists of N tiles where N can be 8, 15, 24 and so on. In our example N = 8. The puzzle is divided into sqrt(N+1) rows and sqrt(N+1) columns. The puzzle can be solved by moving the tiles one by one in the single empty space and thus achieving the Goal configuration. Links: Problem requirement, Github

3. The Missionaries and Cannibals Problem

In the missionaries and cannibals problem, N missionaries and N cannibals must cross a river using a boat which can carry at most M people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board. Links: Problem requirement, Github

4. The Problem with Cubes

We are given M cubes that are put in N stacks. We have the initial configuration and have to apply the A* algorithm to reach the Goal configuration. We can move only the cubes that are placed on top. Links: Problem requirement, Github

II. Minimax Algorithm and Alpha-Beta pruning

1. Draughts/ Checkers

Draughts is played by two opponents, on opposite sides of the gameboard. One player has the dark pieces; the other has the light pieces. Players alternate turns. A player may not move an opponent's piece. A move consists of moving a piece diagonally to an adjacent unoccupied square. If the adjacent square contains an opponent's piece, and the square immediately beyond it is vacant, the piece may be captured (and removed from the game) by jumping over it. Only the dark squares of the checkered board are used. A piece may move only diagonally into an unoccupied square. When presented, capturing is mandatory in most official rules, although some rule variations make capturing optional. In almost all variants, the player without pieces remaining, or who cannot move due to being blocked, loses the game. When a man reaches the kings row, it becomes a king, and is marked by placing an additional piece on top of the first man, and acquires additional powers including the ability to move backwards and capture backwards. Like men, a king can make successive jumps in a single turn provided that each jump captures an enemy man or king. Links: Problem requirement, Github.

2. Connect 4

Connect Four is a two-player board game in which the players first choose a symbol (X or 0) and then take turns dropping one disc from the top into a seven-column, six-row vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one's own discs. Links: Problem requirement, Github.

3. Reversi/ Othello

Reversi is a strategy board game for two players, played on an 8×8 uncheckered board. There are sixty-four identical game pieces called disks (often spelled "discs"), which are light on one side and dark on the other. Players take turns placing disks on the board with their assigned color facing up. During a play, any disks of the opponent's color that are in a straight line and bounded by the disk just placed and another disk of the current player's color are turned over to the current player's color. The object of the game is to have the majority of disks turned to display your color when the last playable empty square is filled. Links: Problem requirement, Github.

4. Tic-Tac-Toe

This is an implementation of a Tic-Tac-Toe solver using the Minimax Algorithm and also Alpha-Beta pruning to help the AI to make decisions. Tic-tac-toe is a paper-and-pencil game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row is the winner. Links: Problem requirement, Github.