⚡ FLIP WARS — DAA Project

A Strategic Duel of Algorithms powered by Divide & Conquer, Dynamic Programming, Backtracking, and Alpha-Beta Pruning.

🎮 PLAY LIVE GAME ONLINE 🌐

---

Course: Design & Analysis of Algorithms (DAA)
Team: Team-13
Live Web Deployment: ganesh2006646.github.io/FLIP
Status: Review 3 Complete (Web Port + JavaFX Application)

---

🌟 Overview & Features

Flip Wars is a strategic tile-flipping game played on a grid ($4 \times 4$, $5 \times 5$, or $6 \times 6$). Each move flips the target tile along with all 4 orthogonal neighbors (up, down, left, right).

Key features include:

• Dual Platform: Native JavaFX desktop application + modern responsive Web App.
• Black Hole Voids: Irregular graph topology — black hole tiles have no adjacency and warp the graph.
• Tabu Search Lock Mechanic: Flipped tiles are locked for countdown turns to prevent infinite flip loops.
• Real-Time Brain Scanner Dashboard: Live algorithm diagnostics visualizing evaluated nodes ($N$), pruned branches ($P$), Transposition Table hits ($DP$), table size ($TT$), move candidate rankings, and the recursive search tree.

---

🎮 How to Play

1. Play Online: Visit https://ganesh2006646.github.io/FLIP/.
2. Select AI Version:
   • R1 (Greedy): Basic single-step AI with a 15% random blunder factor.
   • R2 (Divide & Conquer): Strategic AI leveraging 5 Divide & Conquer algorithms.
   • R3 (DP + Backtracking): Deep look-ahead AI using Alpha-Beta Minimax, Zobrist TT, and a 4x4 Exact DP Oracle.
3. Select Grid Size: Choose $4 \times 4$, $5 \times 5$, or $6 \times 6$.
4. Gameplay: Click a tile to flip it and its orthogonal neighbors. Secure corners (+25) and edges (+15) while avoiding trap tiles (-5).
5. Solve / Hint Mode: Click Solve for AI auto-play or Hint to get the optimal recommended move.

---

🧠 Algorithms Implemented

Review 1: Greedy Baseline

• Tile-Value Heuristic: Corners (+25), Edges (+15), Standard (+5), Traps (-5).
• Blunder Factor: 15% random blunder rate for balanced difficulty.
• Merge Sort: Moves ranked descending.

Review 2: Divide & Conquer (5 Algorithms)

#	Algorithm	Category	Complexity	Purpose
1	Merge Sort	Sorting D&C	$\mathcal{O}(n \log n)$	Ranks all candidate moves for player hints
2	Spatial D&C	Geometric D&C	$\mathcal{O}(n)$	Divides grid into quadrants for regional territory control
3	DFS Clusters	Structural D&C	$\mathcal{O}(V + E)$	Measures connected territory strength using recursive DFS
4	Tournament Selection	Search Space D&C	$\mathcal{O}(n)$	Bracket knockout tournament to pick CPU move
5	Threat Detection	Scoring D&C	$\mathcal{O}(n)$	Evaluates exposed friendly vs. enemy tiles per quadrant

Review 3: DP + Backtracking (4 Algorithms)

#	Algorithm	Type	Complexity	Contributor	Description
1	Pure Backtracking	In-place XOR	$\mathcal{O}(1)$ space	Suhas	In-place doMove / undoMove avoiding board clones
2	Alpha-Beta Minimax	Game Tree Search	$\mathcal{O}(b^{d/2})$	Maneesh	Branch & bound pruning with D&C move ordering
3	Zobrist Transposition Table	Top-Down DP	$\mathcal{O}(1)$ lookup	Ganesh	64-bit Zobrist hashing for board + lock state memoization
4	Bitmask DP Oracle (4x4)	Bottom-Up BFS	$\mathcal{O}(1)$ query	Balaji	Precomputed BFS over all 65,536 4x4 states for exact hints

Leaf Node Combined Evaluation Formula

$$\text{FinalScore} = (0.20 \times \text{Strategic}) + (0.25 \times \text{Quadrant}) + (0.25 \times \text{Cluster}) + (0.30 \times \text{Threat})$$

R3 Dynamic Search Depth

Grid Size	MAX_DEPTH	Evaluated Nodes (Alpha-Beta)
4x4	6	~4K nodes + O(1) Bitmask DP Oracle
5x5	4	~19K nodes
6x6	3	~2K nodes

---

📊 R1 vs R2 vs R3 Comparison

Feature	R1: Greedy	R2: Divide & Conquer	R3: DP + Backtracking
Traversal	Single-step iteration	Quadrant / Bracket breakdown	Deep state-space recursion
Time Complexity	$\mathcal{O}(n)$	$\mathcal{O}(n \log n)$	$\mathcal{O}(1)$ Oracle / $\mathcal{O}(b^{d/2})$
Space Complexity	$\mathcal{O}(1)$	$\mathcal{O}(n)$	Transposition Table + 256KB Oracle
Core Backbone	Greedy heuristic	D&C tournament + DFS	Alpha-Beta Minimax + Zobrist DP
Black Hole Handling	Ignored	Quadrant split skipping	Graph adjacency list exclusion
Hint Quality	Single-step local best	D&C tournament champion	Exact $\mathcal{O}(1)$ oracle (4x4) or Minimax

---

📁 Repository Structure

.
├── index.html              # Main Web App entry point
├── style.css               # Glassmorphic arcade design system & animations
├── game.js                 # Complete JavaScript game engine & AI algorithms
├── run.bat                 # Windows script to launch native JavaFX app
├── README.md               # Project documentation
├── lib/
│   └── javafx/             # JavaFX SDK dependencies
└── src/main/java/com/flipwars/
    ├── FlipWarsApp.java    # JavaFX UI, application loop & Brain Scanner
    ├── Engine.java         # AI Engine dispatcher (R1 / R2 / R3)
    ├── R3Algorithms.java   # Alpha-Beta Minimax, Zobrist TT & 4x4 Oracle
    ├── DACAlgorithms.java  # 4 D&C algorithms (Spatial, Cluster, Tournament, Threat)
    ├── Graph.java          # Adjacency list graph representation
    └── Rules.java          # Tabu search lock mechanic & strategic weights

---

🚀 Running Locally

Option 1: Web Version

Simply open index.html in any web browser, or host locally:

npx serve .

Then visit http://localhost:3000.

Option 2: Native JavaFX App (Desktop)

Ensure JDK 17+ is installed, then run:

run.bat

---

👥 Authors & Credits

Designed and developed for Design & Analysis of Algorithms (DAA) — Team-13.