FLIP WARS — DAA Project

A strategic tile-flipping game demonstrating Divide & Conquer, Dynamic Programming, and Backtracking algorithms.

Course: Design & Analysis of Algorithms (DAA)
Team: team-13
Status: Review 3 Complete (DP + Backtracking Implemented)

---

How to Play

1. Launch: Run FlipWarsApp.java or use run.bat.
2. Select Version:
   • R1 (Greedy): Basic AI from Review 1. Easy to beat.
   • R2 (D&C): Advanced AI with 5 Divide & Conquer algorithms.
   • R3 (DP + Backtracking): Advanced AI with Alpha-Beta Minimax, Zobrist DP, and a 4×4 Oracle.
3. Select Grid Size: 4x4, 5x5, or 6x6.
4. Gameplay: Click a tile to flip it and its 4 neighbors. Try to dominate with Yellow!
5. Solve Mode: Click SOLVE to let the AI auto-play the match.
6. Hint: Click Get Hint for the AI's suggested move.

---

Algorithms Implemented

Review 1: Greedy Approach

• Simple tile value counting (corners +25, edges +15, traps -5)
• 15% random blunder factor for imperfect play
• Merge Sort for move ranking

Review 2: Divide & Conquer (5 Algorithms)

#	Algorithm	Type	Complexity	Function
1	Merge Sort	Sorting D&C	O(n log n)	Ranks ALL moves for Player Hints
2	Spatial D&C	Geometric D&C	O(n)	Divides board into quadrants for regional control
3	DFS Clusters	Structural D&C	O(V+E)	Finds connected territories via recursive DFS
4	Tournament Selection	Search Space D&C	O(n)	Knockout bracket to find CPU's best move
5	Threat Detection	Scoring D&C	O(n)	Identifies exposed/vulnerable tiles per quadrant

Review 3: DP + Backtracking (4 Algorithms)

#	Algorithm	Type	Complexity	Owner
1	Pure Backtracking	In-place XOR do/undo	O(1) per call	SUHAS
2	Alpha-Beta Minimax	Pruned game-tree search	O(b^(d/2)) best	MANEESH
3	Zobrist Transposition Table	Top-Down Memoization (DP)	O(n) hash, O(1) lookup	GANESH
4	Bitmask DP Oracle (4×4)	Bottom-Up BFS over 2^16 states	O(1) query	BALAJI

R3 Scoring Formula (Leaf Evaluation)

FinalScore = (Strategic * 0.20) + (Quadrant * 0.25) + (Cluster * 0.25) + (Threat * 0.30)

R3 Dynamic Depth

Grid	MAX_DEPTH	Effective Nodes
4×4	6	~4K (+ Oracle fallback)
5×5	4	~19K
6×6	3	~2K

---

Project Structure

src/main/java/com/flipwars/
  FlipWarsApp.java    — JavaFX UI, game loop, Brain Scanner dashboard
  Engine.java         — AI logic (R1 Greedy + R2 D&C + R3 switching)
  R3Algorithms.java   — Alpha-Beta Minimax, Zobrist TT, Backtracking, 4×4 Oracle
  DACAlgorithms.java  — 4 D&C algorithms (Spatial, Cluster, Tournament, Threat)
  Graph.java          — Board as adjacency list graph (Black Hole aware)
  Rules.java          — Tabu lock mechanic + strategic tile values

Tech Stack

• Language: Java (JDK 17+)
• GUI: JavaFX (with Brain Scanner dashboard for live AI metrics)
• Architecture: Modular Engine with runtime-swappable AI versions (R1/R2/R3)

Running the Game

javac --module-path lib/javafx/lib --add-modules javafx.controls,javafx.fxml -d bin -sourcepath src/main/java src/main/java/com/flipwars/*.java
java --module-path lib/javafx/lib --add-modules javafx.controls,javafx.fxml -cp bin com.flipwars.FlipWarsApp

Or simply use the provided run.bat.

---

R1 vs R2 vs R3 Comparison

Feature	R1: Greedy	R2: Divide & Conquer	R3: DP + Backtracking
Traversal	Single-step iteration	Subgrid breakdown	State-space deep recursion
Time	O(N²)	O(N² log V)	O(1) Oracle / O(b^(d/2))
Memory	None	None	TT HashMap + 256KB Oracle
Backbone	Naive greedy heuristic	D&C tournament + DFS	α-β Minimax + Zobrist DP
Black Holes	Ignored	Skipped by quadrant split	True topology isolation via Graph
Move Hint	Best single-step tile	Best D&C tournament winner	Perfect O(1) oracle (4×4) or α-β