AI Algorithms and Prolog Examples — BFS, A*, Minimax
AI Algorithms and Prolog Examples
This document contains:
- Prolog family facts and queries
- Python implementations of BFS, DFS, A*, Minimax, Alpha-Beta
- 8-puzzle A* solver, Tic-Tac-Toe minimax, a simple reflex agent, and a Chess AI
Prolog Family Facts and Queries
Prolog
parent(john, mary).
parent(john, david).
parent(susan, mary).
parent(susan, david).
parent(david, emily).
parent(david, james).
parent(mary, ann).
male(john).
male(david).
male(james).
female(susan).
female(mary).
female(ann).
female(emily).
father(X, Y) :- parent(X, Y), male(X).
mother(X, Y) :- parent(X, Y), female(X).
grandparent(X, Z) :- parent(X, Y), parent(Y,Z).
grandmother(X, Y) :- grandparent(X, Y), female(X).
grandfather(X, Y) :- grandparent(X, Y), male(X).
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \== Y.
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z,Y).
QUERIES:
?- father(john, mary). % Check if John is father of Mary
?- mother(susan, david). % Check if Susan is mother of David
?- grandparent(john, emily). % Find if John is a grandparent of Emily
?- grandfather(john, james). % Check if John is grandfather of James
?- grandmother(susan, ann). % Check if Susan is grandmother of Ann
?- sibling(mary, david). % Verify sibling relationship between Mary and David
?- ancestor(john, ann). % Check if John is an ancestor of Ann
?- ancestor(susan, emily). % Check if Susan is ancestor of Emily
?- ancestor(david, james). % Check if David is ancestor of James
?- ancestor(X, emily). % Find all ancestors of Emily
?- parent(X, Y). % Display all parent-child pairs
Python: BFS (Breadth-First Search)
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=" ")
visited.add(node)
queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print("\nBFS Traversal:")
bfs(graph, 'A')
Python: DFS (Depth-First Search)
# 2. DFS (Depth First Search)
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print("\n\nDFS Traversal:")
dfs(graph, 'A')
Python: Basic A* Search
# 3. Basic A* Search
def a_star(graph, start, goal, heuristic):
open_list = [(start, [start], 0)] # (current_node, path, cost_so_far)
while open_list:
open_list.sort(key=lambda x: x[2] + heuristic[x[0]]) # Sort by f = g + h
node, path, cost = open_list.pop(0)
if node == goal:
return path
for neighbor, step_cost in graph[node]:
new_cost = cost + step_cost
open_list.append((neighbor, path + [neighbor], new_cost))
return None
graph = {
'A': [('B', 1), ('C', 3)],
'B': [('D', 1), ('E', 5)],
'C': [('F', 2)],
'D': [],
'E': [('F', 1)],
'F': []
}
heuristic = {'A': 7, 'B': 6, 'C': 2, 'D': 1, 'E': 1, 'F': 0}
path = a_star(graph, 'A', 'F', heuristic)
print("\n\nA* Path:", path)
Python: Basic Minimax Algorithm
# 4. Basic Minimax Algorithm
def minimax(depth, nodeIndex, maximizingPlayer, values):
if depth == 3:
return values[nodeIndex]
if maximizingPlayer:
best = float('-inf')
for i in range(2):
val = minimax(depth + 1, nodeIndex * 2 + i, False, values)
best = max(best, val)
return best
else:
best = float('inf')
for i in range(2):
val = minimax(depth + 1, nodeIndex * 2 + i, True, values)
best = min(best, val)
return best
values = [3, 5, 6, 9, 1, 2, 0, -1]
print("\n\nMinimax Optimal Value:", minimax(0, 0, True, values))
Python: Alpha-Beta Pruning
# 5. Alpha-Beta Pruning
def minimax_ab(depth, nodeIndex, maximizingPlayer, values, alpha, beta):
if depth == 3:
return values[nodeIndex]
if maximizingPlayer:
best = float('-inf')
for i in range(2):
val = minimax_ab(depth + 1, nodeIndex * 2 + i, False, values, alpha, beta)
best = max(best, val)
alpha = max(alpha, best)
if beta <= alpha:
break
return best
else:
best = float('inf')
for i in range(2):
val = minimax_ab(depth + 1, nodeIndex * 2 + i, True, values, alpha, beta)
best = min(best, val)
beta = min(beta, best)
if beta <= alpha:
break
return best
values = [3, 5, 6, 9, 1, 2, 0, -1]
print("Alpha-Beta Optimal Value:", minimax_ab(0, 0, True, values, float('-inf'), float('inf')))
A* for the 8-Puzzle
# 6. 8 Puzzle using A*
from heapq import heappush, heappop
def heuristic_puzzle(state, goal):
return sum(s != g and s != 0 for s, g in zip(state, goal))
def get_neighbors(state):
neighbors = []
idx = state.index(0)
moves = []
if idx not in [0, 1, 2]: moves.append(-3)
if idx not in [6, 7, 8]: moves.append(3)
if idx not in [0, 3, 6]: moves.append(-1)
if idx not in [2, 5, 8]: moves.append(1)
for move in moves:
new_state = list(state)
new_state[idx], new_state[idx + move] = new_state[idx + move], new_state[idx]
neighbors.append(tuple(new_state))
return neighbors
def a_star_8_puzzle(start, goal):
pq = []
heappush(pq, (heuristic_puzzle(start, goal), 0, start, [start]))
visited = set()
while pq:
f, g, state, path = heappop(pq)
if state == goal:
return path
visited.add(state)
for neighbor in get_neighbors(state):
if neighbor not in visited:
heappush(pq, (g + 1 + heuristic_puzzle(neighbor, goal), g + 1, neighbor, path + [neighbor]))
return None
start = (1, 2, 3,
4, 0, 6,
7, 5, 8)
goal = (1, 2, 3,
4, 5, 6,
7, 8, 0)
path = a_star_8_puzzle(start, goal)
print("\n8-Puzzle Steps to Goal:")
for step in path:
print(step[0:3])
print(step[3:6])
print(step[6:9])
print()
Tic-Tac-Toe Using Minimax
7. Tic Tac Toe using Minimax
def print_board(b):
print(b[0], b[1], b[2])
print(b[3], b[4], b[5])
print(b[6], b[7], b[8])
print()
def check_winner(b):
win = [(0,1,2),(3,4,5),(6,7,8),
(0,3,6),(1,4,7),(2,5,8),
(0,4,8),(2,4,6)]
for x,y,z in win:
if b[x] == b[y] == b[z] and b[x] != ' ':
return b[x]
return None
def minimax(b, is_max):
winner = check_winner(b)
if winner == 'X': return 1
if winner == 'O': return -1
if ' ' not in b: return 0
if is_max: # AI's turn
best = -10
for i in range(9):
if b[i] == ' ':
b[i] = 'X'
best = max(best, minimax(b, False))
b[i] = ' '
return best
else: # Human's turn
best = 10
for i in range(9):
if b[i] == ' ':
b[i] = 'O'
best = min(best, minimax(b, True))
b[i] = ' '
return best
def ai_move(b):
best = -10
move = 0
for i in range(9):
if b[i] == ' ':
b[i] = 'X'
score = minimax(b, False)
b[i] = ' '
if score > best:
best = score
move = i
b[move] = 'X'
def play():
b = [' '] * 9
print("Positions: 0 1 2 | 3 4 5 | 6 7 8")
print_board(b)
while True:
m = int(input("Your move (0-8): "))
if b[m] != ' ':
print("Invalid move.")
continue
b[m] = 'O'
if check_winner(b) or ' ' not in b: break
ai_move(b)
print_board(b)
if check_winner(b) or ' ' not in b: break
print_board(b)
w = check_winner(b)
if w: print(w, "wins!")
else: print("It's a draw!")
play()
Simple Reflex Agent
SIMPLE REFLEX AGENT
import random
import time
sensor_inputs = ["Detected", "Not Detected"]
def automatic_door_agent(sensor_input):
if sensor_input == "Detected":
return "Open Door"
else:
return "Keep Door Closed"
def run_simulation():
print("Automatic Door System Simulation:\n")
for step in range(1, 6):
sensor = random.choice(sensor_inputs)
action = automatic_door_agent(sensor)
print(f"Step {step}:")
print(f" Sensor Input : {sensor}")
print(f" Agent's Action : {action}\n")
time.sleep(1)
if __name__ == "__main__":
run_simulation()
Chess AI
CHESS AI
import chess
import math
# Evaluate based on material balance
def evaluate_board(board):
piece_values = {
chess.PAWN: 1,
chess.KNIGHT: 3,
chess.BISHOP: 3,
chess.ROOK: 5,
chess.QUEEN: 9,
chess.KING: 0
}
eval_score = 0
for piece_type in piece_values:
eval_score += len(board.pieces(piece_type, chess.WHITE)) * piece_values[piece_type]
eval_score -= len(board.pieces(piece_type, chess.BLACK)) * piece_values[piece_type]
return eval_score
def minimax(board, depth, alpha, beta, maximizing):
if depth == 0 or board.is_game_over():
return evaluate_board(board), None
legal_moves = list(board.legal_moves)
best_move = None
if maximizing:
max_eval = -math.inf
for move in legal_moves:
board.push(move)
eval, _ = minimax(board, depth - 1, alpha, beta, False)
board.pop()
if eval > max_eval:
max_eval = eval
best_move = move
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval, best_move
else:
min_eval = math.inf
for move in legal_moves:
board.push(move)
eval, _ = minimax(board, depth - 1, alpha, beta, True)
board.pop()
if eval < min_eval:
min_eval = eval
best_move = move
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval, best_move
def play_game():
board = chess.Board()
print("Welcome to Mini Chess AI!")
print("You play as White. Enter moves in UCI format (e.g., e2e4)\n")
while not board.is_game_over():
print(board)
user_move = input("Your move: ")
try:
move = chess.Move.from_uci(user_move)
if move in board.legal_moves:
board.push(move)
else:
print("Illegal move. Try again.")
continue
except:
print("Invalid input. Try again.")
continue
if board.is_game_over():
break
print("\nAI is thinking...")
_, ai_move = minimax(board, 3, -math.inf, math.inf, False)
if ai_move:
board.push(ai_move)
print(f"AI plays: {ai_move}")
else:
print("AI has no valid moves.")
break
print("\nFinal Board:\n", board)
result = board.result()
if result == "1-0":
print("You win!")
elif result == "0-1":
print("AI wins!")
else:
print("It's a draw!")
if __name__ == "__main__":
play_game()
How to Run
How to run
pip install python-chess
python chess_ai.py