ffsshhttiikk What I do
- Implement search algorithms
- Solve pathfinding problems
- Optimize search strategies
- Apply heuristic search
- Handle adversarial search
When to use me
Use me when:
- Finding optimal paths
- Game playing
- Puzzle solving
- Route planning
Key Concepts
Search Categories
- Uninformed: BFS, DFS, Uniform-cost
- Informed: A*, Greedy, IDA*
- Adversarial: Minimax, Alpha-beta
- Local: Hill climbing, Simulated annealing
A* Implementation
import heapq
def astar(start, goal, neighbors, heuristic):
frontier = [(0, start)]
came_from = {start: None}
cost_so_far = {start: 0}
while frontier:
_, current = heapq.heappop(frontier)
if current == goal:
return reconstruct_path(came_from, current)
for next_node in neighbors(current):
new_cost = cost_so_far[current] + cost(current, next_node)
if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
cost_so_far[next_node] = new_cost
priority = new_cost + heuristic(next_node, goal)
heapq.heappush(frontier, (priority, next_node))
came_from[next_node] = current
return None
Minimax for Games
def minimax(board, depth, is_maximizing):
if is_terminal(board) or depth == 0:
return evaluate(board)
if is_maximizing:
max_eval = -inf
for move in get_moves(board):
eval = minimax(make_move(board, move), depth - 1, False)
max_eval = max(max_eval, eval)
return max_eval
else:
min_eval = inf
for move in get_moves(board):
eval = minimax(make_move(board, move), depth - 1, True)
min_eval = min(min_eval, eval)
return min_eval
# Alpha-beta pruning
def alphabeta(board, depth, alpha, beta, is_maximizing):
if is_terminal(board) or depth == 0:
return evaluate(board)
if is_maximizing:
max_eval = -inf
for move in get_moves(board):
eval = alphabeta(make_move(board, move), depth - 1,
alpha, beta, False)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval
else:
min_eval = inf
for move in get_moves(board):
eval = alphabeta(make_move(board, move), depth - 1,
alpha, beta, True)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval