Tác giả: JasonTM17
Ứng dụng Streamlit để học và bảo vệ đồ án Trí tuệ nhân tạo qua 15-puzzle. Repo không chỉ in ra đáp án; nó trình bày state, action, frontier, reached, heuristic, trace, certificate, GIF chạy thật và ranh giới học thuật của từng nhóm thuật toán.
GIF hero ở trên được chụp từ live Streamlit browser capture bằng agent-browser screenshot: A* Search, Manhattan Distance, f(n)=g(n)+h(n), legal blank moves và image tiles đi theo cùng trajectory. Không dùng mockup renderer.
- Chạy Nhanh
- Kết Quả Quét Lại 24 Thuật Toán
- Bản Đồ 6 Nhóm
- Cách Đọc Từng Nhóm
- So Sánh Thuật Toán Trong Nhóm
- Atlas 24 Thuật Toán Có GIF Chạy Thật
- Cách Đọc Evidence
- Tài Liệu
python -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt
streamlit run app.pyWindows PowerShell:
python -m venv .venv
.\.venv\Scripts\Activate.ps1
pip install -r requirements.txt
streamlit run app.pyKiểm tra phát triển:
pip install -r requirements-dev.txt
python -m compileall -q app.py core algorithms ui scripts
python scripts/generate-readme-gifs.py --check --check-readability
python -m pytest tests -q --cov=core --cov=algorithms --cov-report=term-missing --cov-fail-under=65Quét trực tiếp toàn bộ demo specs bằng cùng runner dùng để tạo GIF. Kết quả hiện tại: 24/24 mục thực thi không phát sinh exception. Không tới goal không đồng nghĩa không chạy được; README tách riêng crash, run dừng chưa giải xong, model evidence và solution path.
- Solver chuẩn, demo tới goal và có chứng chỉ tối ưu (5): BFS, UCS, IDS, A*, IDA*.
- Demo tới goal nhưng không có chứng chỉ tối ưu (7): DFS, Greedy Best-First, Local Beam Search, Backtracking, Backtracking + Forward Checking, AC-3, Min-Conflicts.
- Chạy được nhưng demo không tới goal (5): Simple Hill Climbing, Steepest-Ascent Hill Climbing, Stochastic Hill Climbing, Random-Restart Hill Climbing, Simulated Annealing.
- Chỉ tạo model evidence/conditional plan, không tạo goal path (3): AND-OR Search, Searching with no observation, Searching for partially observable problems.
- Decision-policy demo, output chính là root decision / policy evidence (3): Minimax, Alpha-Beta Pruning, Expectimax.
- Chỉ chạy lớp chấm điểm tournament (1): AI-vs-AI Tournament.
Chỉ nhóm đầu được README gọi là solver chuẩn có chứng chỉ tối ưu cho cấu hình demo. Các mục còn lại vẫn có giá trị học thuật, nhưng phải đọc đúng output và caveat ghi ngay tại từng thuật toán.
ALGORITHM_GROUPS là contract chính: 6 nhóm, 24 thuật toán. Mỗi GIF dưới đây là live Streamlit browser capture, không phải mockup.
- Vai trò: Duyet state-space without heuristic; evidence focuses on frontier/reached and legal path.
- Câu hỏi học thuật: If every move costs 1 and no domain estimate is used, how does queue discipline change behavior?
- Thuật toán: BFS, DFS, UCS, IDS
- Vai trò: Add h(n), then combine with g(n) for optimal informed search.
- Câu hỏi học thuật: When is a heuristic only fast, and when does it justify an optimality certificate?
- Thuật toán: Greedy Best-First, A*, IDA*
- Vai trò: Show candidate-level choices without treating the run as guaranteed path search.
- Câu hỏi học thuật: Which neighbor was considered, chosen, rejected or accepted probabilistically?
- Thuật toán: Simple Hill Climbing, Steepest-Ascent Hill Climbing, Stochastic Hill Climbing, Random-Restart Hill Climbing, Local Beam Search, Simulated Annealing
- Vai trò: Model conditional, conformant and contingent planning over explicit belief states.
- Câu hỏi học thuật: What does the agent know, and is the output a conditional plan, conformant sequence or observation policy?
- Thuật toán: AND-OR Search, Searching with no observation, Searching for partially observable problems
- Vai trò: Reframe puzzle planning as variables, domains and constraints.
- Câu hỏi học thuật: Which variable/domain/constraint evidence is being shown instead of a shortest path claim?
- Thuật toán: Backtracking, Backtracking + Forward Checking, AC-3, Min-Conflicts
- Vai trò: Decision / Policy Lab: scored benchmark, policy comparison, robustness game variant and chance outcome lab without pretending standard 15-puzzle has a natural opponent.
- Câu hỏi học thuật: Is this a scored benchmark, a worst-case branch or an expected-value model?
- Thuật toán: AI-vs-AI Tournament, Minimax, Alpha-Beta Pruning, Expectimax
Trong Play, Group 6 được tách khỏi Solver Replay:
- Policy Comparison: hai puzzle ảnh độc lập, cùng Start/Goal, so Minimax / Alpha-Beta / Expectimax theo runtime, expanded/generated, pruned, root value và Manhattan.
- Robustness Game Variant: một puzzle ảnh chung, MAX cố tiến về goal, MIN là worst-case environment branch. Đây là game biến thể để học Minimax/Alpha-Beta, không phải 15-puzzle chuẩn.
- Chance Outcome Lab: Expectimax không có MIN; MAX chọn intended action, CHANCE sample outcome theo probability model và seed.
| Nhóm | Cách đọc đúng | Sai lầm cần tránh |
|---|---|---|
| Uninformed Search | So sánh FIFO, LIFO, cost queue và iterative deepening khi không có h(n). | Gọi DFS là optimal hoặc quên memory của BFS. |
| Informed Search | Đọc h(n), g(n), f(n), admissible/consistent và certificate. | Gọi Greedy là optimal chỉ vì một run tình cờ ngắn. |
| Local Search | Xem candidate được xét/chọn/từ chối và lý do dừng. | Nhầm legal trajectory thành solution path. |
| Complex Environments | Đọc conditional, conformant và contingent policy theo đúng belief-state model. | Ép policy thành đường đi tuyến tính giả hoặc để hidden state điều khiển agent. |
| CSP | Đọc variables, domains, constraints, propagation và horizon. | Gọi CSP model definition là shortest-path solver. |
| AI-vs-AI Tournament | Đọc scoring, robustness, pruning và expected value. | Gọi MIN là đối thủ thật của 15-puzzle. |
| Thuật toán | Frontier/decision rule | Evidence cần nhìn | Guarantee đúng | Caveat |
|---|---|---|---|---|
| BFS | FIFO queue, mở theo tầng. | frontier/reached, path cost, depth. | Complete, optimal với unit step cost. | Memory tăng rất nhanh. |
| DFS | LIFO stack, đi sâu trước. | depth, expanded, legal trajectory. | Không có shortest-path guarantee. | Có thể đi nhánh sâu và bỏ lỡ đường ngắn. |
| UCS | Priority queue theo g(n). |
cumulative cost, frontier/reached. | Complete, optimal với non-negative cost. | Với 15-puzzle unit cost gần giống BFS nhưng nêu rõ cost model. |
| IDS | DFS giới hạn độ sâu, tăng limit. | cutoff/exhausted theo từng limit. | Complete, optimal với unit step cost khi limit đủ. | Lặp lại work qua nhiều iteration. |
| Thuật toán | Evaluation rule | Evidence cần nhìn | Guarantee đúng | Caveat |
|---|---|---|---|---|
| Greedy Best-First | Ưu tiên h(n) nhỏ nhất. |
selected h, frontier, goal flag. | Không optimality certificate. | Nhanh nhưng có thể bị heuristic đánh lừa. |
| A* | Ưu tiên f(n)=g(n)+h(n). |
g/h/f, expanded/generated/frontier. | Optimal nếu h admissible/consistent và không bị limit. | Certificate chỉ đúng cho goal/heuristic đã chọn. |
| IDA* | DFS bounded bởi threshold f. |
threshold, best_g/reached, path. | Optimal với admissible heuristic và threshold đủ. | Tiết kiệm memory nhưng revisit nhiều state. |
| Thuật toán | Candidate rule | Evidence cần nhìn | Output đúng | Caveat |
|---|---|---|---|---|
| Simple Hill Climbing | Chọn candidate cải thiện đầu tiên. | candidate được xét, selected action. | Legal local trajectory nếu có action. | Dễ kẹt local optimum. |
| Steepest-Ascent HC | Xét toàn bộ neighbor rồi chọn tốt nhất. | evaluated candidates, best candidate. | Local improvement trace. | Tốn xét neighbor nhưng vẫn local. |
| Stochastic HC | Random trong nhóm candidate cải thiện. | seed, candidate pool, chosen action. | Reproducible khi seed cố định. | Kết quả phụ thuộc seed. |
| Random-Restart HC | Nhiều lần start lại rồi hill climb. | restart index, best h. | So sánh nhiều basin cục bộ. | Không biến thành shortest-path solver. |
| Local Beam Search | Giữ k state tốt nhất mỗi vòng. |
beam states, selected successors. | Population-based local evidence. | Beam nhỏ có thể mất nhánh tốt. |
| Simulated Annealing | Có thể accept bước xấu theo temperature. | temperature, delta h, accept/reject. | Legal trajectory, đôi khi thoát local optimum. | Không claim solved nếu chưa tới goal. |
| Thuật toán | Mô hình output | Evidence cần nhìn | Guarantee đúng | Caveat |
|---|---|---|---|---|
| AND-OR Search | Conditional plan/policy. | AND node, OR action, deflection support. | Plan hợp lệ trong depth/support đã chọn. | Không phải linear path giả; support switch không phải probability weight. |
| Searching with no observation | Conformant graph search trên belief state. | Predict(B,a), belief frontier/reached, duplicate rejection, goal coverage. | Một action sequence phải đúng cho mọi state được biểu diễn. | Belief hữu hạn là approximation; bounded failure không chứng minh impossible toàn cục. |
| Partially observable search | Contingent belief-state AND-OR. | predicted belief, observation partitions, updated beliefs, branch coverage. | Mọi observation branch phải có subpolicy. | Hidden actual state chỉ để audit, không xây policy. |
Complete assignment = {S[0]=Start, ..., S[T]=Goal} với mọi cạnh S[t] -> S[t+1] là một legal blank move.
| Thuật toán | CSP concept | Evidence cần nhìn | Output đúng | Caveat |
|---|---|---|---|---|
| Backtracking | Chronological state-chain assignment. | assignments, consistency checks, backtracks. | Exact-T legal chain khi thành công. | Failure chỉ đúng trong horizon/resource bound. |
| Backtracking + Forward Checking | Assignment kèm prune domain kế tiếp. | values pruned, domain wipe-out, backtracks. | Cùng ordering để so sánh công bằng với Backtracking. | Worst case vẫn exponential. |
| AC-3 | Arc-consistency propagation trên state chain. | arc queue, REVISE, values removed, domain sizes. | Sound propagation; replay chỉ từ exact legal chain. | Arc-consistent không tự động nghĩa unique solution. |
| Min-Conflicts | Seeded local repair của complete state-chain assignment. | conflicted variable, conflict count, iteration. | Replay chỉ khi zero conflict và mọi move legal. | Không complete, không optimal. |
| Thuật toán | Decision model | Evidence cần nhìn | Output đúng | Caveat |
|---|---|---|---|---|
| AI-vs-AI Tournament | Scored benchmark against A* reference. | score, optimal cost, verified trajectory. | Fair score if reference certificate exists. | Không phải một đối thủ tự nhiên trong 15-puzzle. |
| Minimax | MAX vs worst-case MIN branch. | utility, depth, selected root action. | Depth-limited worst-case decision. | MIN không phải người chơi thật; cả hai dùng legal blank moves. |
| Alpha-Beta Pruning | Minimax with branch-and-bound pruning. | alpha, beta, cutoff events. | Same root value as full Minimax under same searched tree. | Pruning tiết kiệm node, không đổi PEAS thành game thật. |
| Expectimax | Expected value with CHANCE nodes. | probability model, expected utility. | Depth-limited expected-value policy. | Probability model là giáo dục và phải nêu rõ. |
Mỗi mục dưới đây có GIF riêng. GIF được tạo từ scripts/generate-readme-gifs.py, mở app thật, chụp frame thật từ route ?capture_demo=..., dùng start/goal/seed/resource limit cố định và được khóa bằng manifest semantic. Dòng Kết luận chạy / độ phù hợp nói rõ demo có tới goal hay không và thuật toán có được dùng làm solver chuẩn hay chỉ là mô hình giáo dục.
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Uninformed Search |
| Vai trò | Standard solver |
| Learning goal | Understand level-order expansion and why unit-cost BFS can certify shortest paths. |
| Cơ chế | FIFO frontier over puzzle states. |
| Evidence trong GIF | frontier size, reached set, legal path and path cost. |
| Guarantee | Complete and optimal for unit step cost if resources suffice. |
| Caveat | Memory grows quickly; good for shallow teaching cases, not deep 15-puzzle production search. |
| Phù hợp với 15-puzzle chuẩn | Solver chuẩn cho ca nông: complete và optimal với unit step cost, nhưng frontier/reached tăng rất nhanh nên không hợp cho 15-puzzle sâu. |
| Kết luận chạy / độ phù hợp | PHÙ HỢP LÀM SOLVER CHUẨN — Demo thật đã tới goal bằng legal path và có chứng chỉ tối ưu cho cấu hình đã chạy. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_optimal - reached goal with an optimality certificate |
| Demo input | seed 42, termination goal, default demo parameters |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=True |
| Result message | Solution found |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Uninformed Search |
| Vai trò | Contrast demo |
| Learning goal | See how depth-first commitment differs from optimal state-space search. |
| Cơ chế | LIFO stack with depth-aware duplicate handling. |
| Evidence trong GIF | expanded nodes, depth limit and legal trajectory when present. |
| Guarantee | No shortest-path guarantee in this app setting. |
| Caveat | Can chase a deep branch and miss a shorter path. |
| Phù hợp với 15-puzzle chuẩn | Không dùng làm solver chuẩn: có thể tìm được một path hợp lệ nhưng không bảo đảm ngắn nhất và dễ đi sâu vào nhánh kém. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC, DEMO TỚI GOAL NHƯNG KHÔNG CÓ CHỨNG CHỈ TỐI ƯU — Không dùng run này để claim shortest path hoặc solver chuẩn tối ưu. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_not_optimal - reached goal without an optimality certificate |
| Demo input | seed 42, termination goal, max_depth=12 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Solution found |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Uninformed Search |
| Vai trò | Standard solver |
| Learning goal | Connect path cost g(n) to optimal search. |
| Cơ chế | Priority queue ordered by cumulative path cost. |
| Evidence trong GIF | g(n), frontier, reached and cost certificate. |
| Guarantee | Complete and optimal for non-negative costs. |
| Caveat | On unit-cost 15-puzzle it behaves like BFS but keeps the general cost model explicit. |
| Phù hợp với 15-puzzle chuẩn | Solver chuẩn khi chi phí bước không âm. Với 15-puzzle unit cost, UCS gần tương đương BFS nhưng giữ rõ mô hình path cost g(n). |
| Kết luận chạy / độ phù hợp | PHÙ HỢP LÀM SOLVER CHUẨN — Demo thật đã tới goal bằng legal path và có chứng chỉ tối ưu cho cấu hình đã chạy. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_optimal - reached goal with an optimality certificate |
| Demo input | seed 42, termination goal, default demo parameters |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=True |
| Result message | Solution found |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Uninformed Search |
| Vai trò | Standard solver |
| Learning goal | Trade BFS optimality for DFS-like memory by increasing the depth limit. |
| Cơ chế | Repeated depth-limited DFS with cutoff tracking. |
| Evidence trong GIF | depth limit, cutoff/exhausted reason and legal path. |
| Guarantee | Complete and optimal for unit step cost if the limit reaches the solution depth. |
| Caveat | Repeats work across iterations; the trace should be read by limit, not as one queue. |
| Phù hợp với 15-puzzle chuẩn | Solver chuẩn cho unit-cost khi depth limit đủ lớn: tiết kiệm bộ nhớ hơn BFS nhưng lặp lại nhiều lần qua các giới hạn độ sâu. |
| Kết luận chạy / độ phù hợp | PHÙ HỢP LÀM SOLVER CHUẨN — Demo thật đã tới goal bằng legal path và có chứng chỉ tối ưu cho cấu hình đã chạy. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_optimal - reached goal with an optimality certificate |
| Demo input | seed 42, termination goal, max_depth=12 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=True |
| Result message | Found at depth 5, limit=5 |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Informed Search |
| Vai trò | Contrast demo |
| Learning goal | Show why h(n) alone is fast but not a certificate. |
| Cơ chế | Priority queue ordered only by heuristic h(n). |
| Evidence trong GIF | selected h(n), frontier and whether the final path reaches goal. |
| Guarantee | No optimality guarantee. |
| Caveat | May find a longer path or get misled by a locally attractive state. |
| Phù hợp với 15-puzzle chuẩn | Không dùng để chứng minh tối ưu: h(n) giúp chạy nhanh hơn nhưng bỏ qua g(n), nên path có thể dài hơn A*. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC, DEMO TỚI GOAL NHƯNG KHÔNG CÓ CHỨNG CHỈ TỐI ƯU — Không dùng run này để claim shortest path hoặc solver chuẩn tối ưu. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_not_optimal - reached goal without an optimality certificate |
| Demo input | seed 42, termination goal, default demo parameters |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Solution found |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Informed Search |
| Vai trò | Standard solver |
| Learning goal | Read f(n)=g(n)+h(n) and the Manhattan optimality condition. |
| Cơ chế | Priority queue ordered by g(n)+h(n). |
| Evidence trong GIF | g/h/f, expanded/generated/frontier, legal path and optimality flag. |
| Guarantee | Optimal with admissible and consistent heuristic when resources do not stop the run. |
| Caveat | The certificate is valid only for the selected goal and heuristic contract. |
| Phù hợp với 15-puzzle chuẩn | Solver chuẩn chính của app: với Manhattan Distance admissible/consistent và unit step cost, có thể bật optimality_proven khi tới goal. |
| Kết luận chạy / độ phù hợp | PHÙ HỢP LÀM SOLVER CHUẨN — Demo thật đã tới goal bằng legal path và có chứng chỉ tối ưu cho cấu hình đã chạy. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_optimal - reached goal with an optimality certificate |
| Demo input | seed 42, termination goal, default demo parameters |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=True |
| Result message | Solution found |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Informed Search |
| Vai trò | Standard solver |
| Learning goal | Combine A* evaluation with memory-bounded iterative thresholds. |
| Cơ chế | Depth-first search bounded by increasing f-threshold. |
| Evidence trong GIF | threshold, reached metric, legal path and optimality flag. |
| Guarantee | Optimal with admissible heuristic and sufficient threshold iterations. |
| Caveat | May revisit many states; trace is threshold-based, not a single frontier queue. |
| Phù hợp với 15-puzzle chuẩn | Solver chuẩn memory-bounded: hợp với 15-puzzle sâu hơn A* về bộ nhớ, đổi lại có thể revisit nhiều state theo threshold. |
| Kết luận chạy / độ phù hợp | PHÙ HỢP LÀM SOLVER CHUẨN — Demo thật đã tới goal bằng legal path và có chứng chỉ tối ưu cho cấu hình đã chạy. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_optimal - reached goal with an optimality certificate |
| Demo input | seed 42, termination goal, default demo parameters |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=True |
| Result message | Found with threshold=4 |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Local Search |
| Vai trò | Contrast demo |
| Learning goal | Watch the first improving candidate win or the search stop. |
| Cơ chế | Scan neighbors and move to the first lower h(n). |
| Evidence trong GIF | candidate h, selected action and stop reason. |
| Guarantee | No completeness or optimality guarantee. |
| Caveat | Local optimum can stop the run far from the goal. |
| Phù hợp với 15-puzzle chuẩn | Không ổn làm solver chuẩn: chỉ đi theo cải thiện cục bộ và có thể dừng ở local optimum dù goal chưa đạt. GIF ghi trung thực rằng demo không tạo solution claim. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC NHƯNG DEMO KHÔNG TỚI GOAL — Run dừng có kiểm soát (termination=stopped), không phải crash; trajectory/evidence không được gọi là lời giải. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | not_solved_in_demo - web demo completed without a solution claim |
| Demo input | seed 42, termination stopped, max_iterations=40 |
| Certificate flags | path_verified=True, goal_reached=False, optimality_proven=False |
| Result message | Stuck at local optimum h=4.0 |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Local Search |
| Vai trò | Contrast demo |
| Learning goal | Compare all local neighbors before moving. |
| Cơ chế | Choose the neighbor with best h(n) decrease. |
| Evidence trong GIF | evaluated candidates, best candidate and reject/accept reason. |
| Guarantee | No completeness or optimality guarantee. |
| Caveat | Still local; evaluating every neighbor does not solve plateaus. |
| Phù hợp với 15-puzzle chuẩn | Không ổn làm solver chuẩn: xét hết neighbor cục bộ tốt hơn Simple HC nhưng vẫn kẹt plateau/local optimum. GIF ghi trung thực rằng demo không tạo solution claim. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC NHƯNG DEMO KHÔNG TỚI GOAL — Run dừng có kiểm soát (termination=stopped), không phải crash; trajectory/evidence không được gọi là lời giải. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | not_solved_in_demo - web demo completed without a solution claim |
| Demo input | seed 42, termination stopped, max_iterations=40 |
| Certificate flags | path_verified=True, goal_reached=False, optimality_proven=False |
| Result message | Stuck at local optimum h=4.0 |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Local Search |
| Vai trò | Contrast demo |
| Learning goal | See randomness among improving candidates. |
| Cơ chế | Sample one improving move using a fixed seed. |
| Evidence trong GIF | candidate pool, chosen action, seed and legal trajectory. |
| Guarantee | No deterministic optimality guarantee. |
| Caveat | Different seeds can produce different partial trajectories. |
| Phù hợp với 15-puzzle chuẩn | Không ổn làm solver chuẩn: seed khác có thể cho trajectory khác, không có completeness hay optimality certificate. GIF ghi trung thực rằng demo không tạo solution claim. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC NHƯNG DEMO KHÔNG TỚI GOAL — Run dừng có kiểm soát (termination=stopped), không phải crash; trajectory/evidence không được gọi là lời giải. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | not_solved_in_demo - web demo completed without a solution claim |
| Demo input | seed 42, termination stopped, max_iterations=40, seed=7 |
| Certificate flags | path_verified=True, goal_reached=False, optimality_proven=False |
| Result message | Stuck at local optimum h=4.0 |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Local Search |
| Vai trò | Contrast demo |
| Learning goal | Use restarts to escape one bad local basin. |
| Cơ chế | Run multiple hill climbs from deterministic restart states. |
| Evidence trong GIF | restart index, best h(n) and selected trajectory. |
| Guarantee | Still not a complete 15-puzzle solver here. |
| Caveat | More restarts improve chances but do not prove optimality. |
| Phù hợp với 15-puzzle chuẩn | Không ổn làm solver chuẩn: restart tăng cơ hội thoát basin xấu nhưng vẫn không chứng minh được shortest path. GIF ghi trung thực rằng demo không tạo solution claim. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC NHƯNG DEMO KHÔNG TỚI GOAL — Run dừng có kiểm soát (termination=stopped), không phải crash; trajectory/evidence không được gọi là lời giải. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | not_solved_in_demo - web demo completed without a solution claim |
| Demo input | seed 42, termination stopped, max_iterations=40, seed=7, max_restarts=3 |
| Certificate flags | path_verified=True, goal_reached=False, optimality_proven=False |
| Result message | Best h=4.0 after 3 restarts |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Local Search |
| Vai trò | Contrast demo |
| Learning goal | Track several local candidates at once. |
| Cơ chế | Keep k best states per iteration. |
| Evidence trong GIF | beam width, candidate scores and selected beam states. |
| Guarantee | No optimality guarantee. |
| Caveat | The beam can collapse to similar states and miss the global route. |
| Phù hợp với 15-puzzle chuẩn | Không ổn làm solver chuẩn: giữ nhiều candidate giúp minh họa tìm kiếm cục bộ, nhưng beam nhỏ có thể bỏ mất route tốt. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC, DEMO TỚI GOAL NHƯNG KHÔNG CÓ CHỨNG CHỈ TỐI ƯU — Không dùng run này để claim shortest path hoặc solver chuẩn tối ưu. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_not_optimal - reached goal without an optimality certificate |
| Demo input | seed 42, termination goal, max_iterations=40, beam_width=3 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Goal reached |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Local Search |
| Vai trò | Contrast demo |
| Learning goal | Understand probabilistic acceptance of worse moves. |
| Cơ chế | Temperature-controlled accept/reject over neighbors. |
| Evidence trong GIF | temperature, probability, accepted flag and legal trajectory. |
| Guarantee | No certificate of reaching or optimizing the goal. |
| Caveat | A legal trajectory is not automatically a solution. |
| Phù hợp với 15-puzzle chuẩn | Không ổn làm solver chuẩn: có thể nhận bước xấu để thoát local optimum, nhưng legal trajectory không đồng nghĩa solved hoặc optimal. GIF ghi trung thực rằng demo không tạo solution claim. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC NHƯNG DEMO KHÔNG TỚI GOAL — Run dừng có kiểm soát (termination=stopped), không phải crash; trajectory/evidence không được gọi là lời giải. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | not_solved_in_demo - web demo completed without a solution claim |
| Demo input | seed 42, termination stopped, max_iterations=40, seed=7 |
| Certificate flags | path_verified=True, goal_reached=False, optimality_proven=False |
| Result message | Best h=5.0, temp=98.0684 |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Complex Environments |
| Vai trò | Extension |
| Learning goal | Read a conditional plan under possible outcome deflections. |
| Cơ chế | OR chooses action; AND requires subplans for supported outcomes. |
| Evidence trong GIF | conditional branches, depth limit and deflection support mode. |
| Guarantee | Returns a policy-like conditional plan, not a linear shortest path. |
| Caveat | The support switch is not probability weighting. |
| Phù hợp với 15-puzzle chuẩn | Không phải solver tuyến tính của 15-puzzle deterministic: dùng để minh họa conditional plan khi môi trường có outcome lệch. GIF là model evidence, không phải path tới goal. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC VÀ TRẢ CONDITIONAL PLAN — Output đúng là kế hoạch có nhánh, không phải một linear path tới goal của 15-puzzle deterministic. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | ran_model_not_goal_path - ran successfully as model evidence, not a solved path |
| Demo input | seed 42, termination model_success, max_depth=2, nondet_prob=0.0 |
| Certificate flags | path_verified=False, goal_reached=False, optimality_proven=False |
| Result message | Conditional plan found (depth limit=2). AND-OR requires every supported outcome to succeed. Deflection support=intended outcome only; nondet_prob>0 adds all legal deflections, not probability-weighted branches. OR: choose action R (h=1.0) |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Complex Environments |
| Vai trò | Extension |
| Learning goal | Find one conformant action sequence without reading the hidden state. |
| Cơ chế | Graph-search finite belief states using Predict(B,a), with illegal actions defined as no-op. |
| Evidence trong GIF | belief frontier/reached, duplicate rejection, action sequence and goal coverage. |
| Guarantee | Success means every represented initial state reaches the goal under one sequence. |
| Caveat | The finite reconstructed belief is an approximation, and bounded failure is not a global impossibility proof. |
| Phù hợp với 15-puzzle chuẩn | Không phải solver chuẩn full-observation: conformant sequence phải đúng cho mọi state trong belief hữu hạn và không được đọc hidden state. GIF là model evidence, không phải path tới goal. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC Ở CHẾ ĐỘ MÔ HÌNH/EVIDENCE — Không sinh legal solution path tới goal; mục này dùng để minh họa khái niệm, không phải solver 15-puzzle chuẩn. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | ran_model_not_goal_path - ran successfully as model evidence, not a solved path |
| Demo input | seed 42, termination model_success, max_steps=2, num_belief_states=1, known_positions={'0': 1, '1': 2, '2': 3, '3': 4, '4': 5, '5': 6, '6': 7, '7': 8, '8': 9, '9': 10, '10': 11, '11': 12, '12': 13, '13': 14, '14': 0, '15': 15}, seed=42 |
| Certificate flags | path_verified=False, goal_reached=False, optimality_proven=False |
| Result message | Conformant belief-state search found one fixed action sequence that sends every represented state to the goal. |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | Complex Environments |
| Vai trò | Extension |
| Learning goal | Build a contingent policy that covers every possible local observation. |
| Cơ chế | Predict a belief, partition by blank-and-neighbor percept, then recurse on each updated belief. |
| Evidence trong GIF | predicted belief, observation partitions, branch coverage and policy depth. |
| Guarantee | Success requires a subpolicy for every represented observation branch. |
| Caveat | The sensor and finite belief approximation are explicit; hidden state never builds the policy. |
| Phù hợp với 15-puzzle chuẩn | Không phải linear solver chuẩn: output là contingent policy phân nhánh theo observation của blank và tile kề. GIF là model evidence, không phải path tới goal. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC Ở CHẾ ĐỘ MÔ HÌNH/EVIDENCE — Không sinh legal solution path tới goal; mục này dùng để minh họa khái niệm, không phải solver 15-puzzle chuẩn. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | ran_model_not_goal_path - ran successfully as model evidence, not a solved path |
| Demo input | seed 42, termination model_success, max_steps=2, num_belief_states=1, known_positions={'0': 1, '1': 2, '2': 3, '3': 4, '4': 5, '5': 6, '6': 7, '7': 8, '8': 9, '9': 10, '10': 11, '11': 12, '12': 13, '13': 14, '14': 0, '15': 15}, seed=42 |
| Certificate flags | path_verified=False, goal_reached=False, optimality_proven=False |
| Result message | Contingent belief-state AND-OR search found a policy covering every represented observation branch. |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | CSP |
| Vai trò | Extension |
| Learning goal | Assign an exact-horizon state chain chronologically. |
| Cơ chế | Backtrack when a neighboring state violates the legal blank-move constraint. |
| Evidence trong GIF | assignments, checks, backtracks and verified path when found. |
| Guarantee | Sound within the represented horizon and resource bounds. |
| Caveat | Horizon failure is not global unsolvability or a shortest-path certificate. |
| Phù hợp với 15-puzzle chuẩn | CSP assignment search theo exact horizon: chỉ replay verified legal chain; không claim shortest path hoặc unsolvable toàn cục. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC, DEMO TỚI GOAL NHƯNG KHÔNG CÓ CHỨNG CHỈ TỐI ƯU — Không dùng run này để claim shortest path hoặc solver chuẩn tối ưu. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_not_optimal - reached goal without an optimality certificate |
| Demo input | seed 42, termination goal, time_horizon=1, max_steps=600 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Backtracking found an exact-horizon CSP assignment for T=1. checks=0, backtracks=0, values_pruned=0. |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | CSP |
| Vai trò | Extension |
| Learning goal | Compare early domain pruning with plain backtracking. |
| Cơ chế | After assignment, remove unsupported values from the next state domain. |
| Evidence trong GIF | assignments, values pruned, domain wipe-out and backtracks. |
| Guarantee | Uses the same ordering as Backtracking for a fair empirical comparison. |
| Caveat | Worst-case complexity remains exponential and failure is horizon-bounded. |
| Phù hợp với 15-puzzle chuẩn | CSP assignment search có domain pruning; dùng cùng ordering với Backtracking để so sánh, nhưng worst case vẫn exponential. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC, DEMO TỚI GOAL NHƯNG KHÔNG CÓ CHỨNG CHỈ TỐI ƯU — Không dùng run này để claim shortest path hoặc solver chuẩn tối ưu. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_not_optimal - reached goal without an optimality certificate |
| Demo input | seed 42, termination goal, time_horizon=1, max_steps=600 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Backtracking + Forward Checking found an exact-horizon CSP assignment for T=1. checks=0, backtracks=0, values_pruned=0. |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | CSP |
| Vai trò | Extension |
| Learning goal | Read arc consistency without confusing propagation with a solved path. |
| Cơ chế | REVISE directed arcs between adjacent state variables. |
| Evidence trong GIF | arc queue, revisions, values removed and domain sizes. |
| Guarantee | Sound propagation; replay appears only after extracting an exact legal chain. |
| Caveat | Arc-consistent non-singleton domains are not by themselves a unique solution. |
| Phù hợp với 15-puzzle chuẩn | Propagation trên exact-horizon state chain; arc consistency là evidence, chỉ replay khi trích được exact legal chain. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC, DEMO TỚI GOAL NHƯNG KHÔNG CÓ CHỨNG CHỈ TỐI ƯU — Không dùng run này để claim shortest path hoặc solver chuẩn tối ưu. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_not_optimal - reached goal without an optimality certificate |
| Demo input | seed 42, termination goal, time_horizon=1 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | AC-3 State-Chain CSP completed: revisions=0, values_removed=0, arc_checks=2. Arc-consistent domains contain an extracted verified goal path. |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | CSP |
| Vai trò | Extension |
| Learning goal | Repair a complete state-chain assignment by reducing violated transitions. |
| Cơ chế | Select a conflicted variable and a value with lower total conflict. |
| Evidence trong GIF | iteration, conflicted variable, conflict count and fixed seed. |
| Guarantee | A zero-conflict verified chain is replayable. |
| Caveat | Not complete or optimal; iteration failure returns repair evidence only. |
| Phù hợp với 15-puzzle chuẩn | Local repair trên complete state-chain assignment; chỉ gọi thành công khi conflict bằng 0 và mọi transition là legal blank move. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC, DEMO TỚI GOAL NHƯNG KHÔNG CÓ CHỨNG CHỈ TỐI ƯU — Không dùng run này để claim shortest path hoặc solver chuẩn tối ưu. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | solved_not_optimal - reached goal without an optimality certificate |
| Demo input | seed 42, termination goal, time_horizon=1, max_iterations=80 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Min-Conflicts found a zero-conflict chain at iteration 0. |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | AI-vs-AI Tournament |
| Vai trò | Scoring layer |
| Learning goal | Score two agents against the same A* reference. |
| Cơ chế | Run two solvers and classify verified trajectories. |
| Evidence trong GIF | points, optimal cost, excess cost and invalid-path penalties. |
| Guarantee | Fair benchmark when the reference certificate exists. |
| Caveat | Tournament is not a natural adversarial PEAS model. |
| Phù hợp với 15-puzzle chuẩn | Không phải thuật toán giải puzzle: là lớp chấm điểm hai solver bằng A* reference và verified trajectory. |
| Kết luận chạy / độ phù hợp | CHẠY ĐƯỢC Ở CHẾ ĐỘ CHẤM ĐIỂM — Đây là benchmark hai agent, không phải một thuật toán sinh solution path riêng. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | ran_tournament_model - scored tournament model, not one solution path |
| Demo input | seed 42, termination tournament_scored, default demo parameters |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Tournament scoring run |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | AI-vs-AI Tournament |
| Vai trò | Robustness demo |
| Learning goal | Interpret MIN as worst-case robustness, not a real puzzle opponent. |
| Cơ chế | Alternate MAX promising moves with MIN worst-case legal continuations. |
| Evidence trong GIF | MAX/MIN nodes, utility and selected root action. |
| Guarantee | Depth-limited worst-case decision rule. |
| Caveat | Both sides share legal blank moves because 15-puzzle has no natural adversary. |
| Phù hợp với 15-puzzle chuẩn | Không phải solver tự nhiên của 15-puzzle: MIN là nhánh worst-case robustness, không phải đối thủ thật. GIF là root decision / policy evidence; nếu variation tới goal thì đó vẫn không phải solver certificate. |
| Kết luận chạy / độ phù hợp | DECISION / POLICY EVIDENCE — Demo may move through legal puzzle states, but the output is root decision / policy evidence, not a shortest solver certificate. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | decision_policy_demo - root decision / policy evidence, not a shortest solver certificate |
| Demo input | seed 42, termination goal, depth=2 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Minimax (depth=2) Completed depth 2 Best utility: 1000.0 MAX selects the most promising legal move. MIN branch models worst-case legal continuations, not a real opponent. Standard 15-puzzle has no natural adversary; this is robustness analy |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | AI-vs-AI Tournament |
| Vai trò | Robustness demo |
| Learning goal | Learn branch-and-bound pruning over the same worst-case tree. |
| Cơ chế | Prune branches that cannot change the minimax root value. |
| Evidence trong GIF | alpha, beta, pruned branches and root utility. |
| Guarantee | Same root value as full Minimax for the searched tree. |
| Caveat | Pruning saves nodes; it does not turn the puzzle into a real two-player game. |
| Phù hợp với 15-puzzle chuẩn | Không phải solver tự nhiên của 15-puzzle: chỉ prune cây Minimax worst-case cùng root value, không đổi puzzle thành game hai người. GIF là root decision / policy evidence; nếu variation tới goal thì đó vẫn không phải solver certificate. |
| Kết luận chạy / độ phù hợp | DECISION / POLICY EVIDENCE — Demo may move through legal puzzle states, but the output is root decision / policy evidence, not a shortest solver certificate. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | decision_policy_demo - root decision / policy evidence, not a shortest solver certificate |
| Demo input | seed 42, termination goal, depth=2 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Alpha-Beta Pruning (depth=2) Completed depth 2 Best utility: 1000.0 Nodes expanded: 8 Cutoff events: 1 MIN branch models worst-case legal continuations, not a real opponent. With identical ordering, no timeout, and a completed depth, Alpha- |
| Trục đọc | Nội dung |
|---|---|
| Nhóm | AI-vs-AI Tournament |
| Vai trò | Chance demo |
| Learning goal | Compare expected value against worst-case reasoning. |
| Cơ chế | Replace MIN with CHANCE outcomes and success probability. |
| Evidence trong GIF | CHANCE nodes, probabilities and expected utility. |
| Guarantee | Depth-limited expected-value policy under the chosen probability model. |
| Caveat | Probability model is educational and must be stated before interpreting the result. |
| Phù hợp với 15-puzzle chuẩn | Không phải solver chuẩn: dùng CHANCE/probability model để so expected value, xác suất là mô hình giáo dục. GIF là root decision / policy evidence; nếu variation tới goal thì đó vẫn không phải solver certificate. |
| Kết luận chạy / độ phù hợp | DECISION / POLICY EVIDENCE — Demo may move through legal puzzle states, but the output is root decision / policy evidence, not a shortest solver certificate. |
| Web capture source | live_streamlit_browser_capture via agent-browser screenshot |
| web_run_status | decision_policy_demo - root decision / policy evidence, not a shortest solver certificate |
| Demo input | seed 42, termination goal, depth=2, success_prob=0.75, seed=11 |
| Certificate flags | path_verified=True, goal_reached=True, optimality_proven=False |
| Result message | Expectimax (depth=2, success_prob=0.75) Completed depth 2 Expected utility from start: 749.5 Nodes expanded: 4 Comparison with Minimax: Minimax: evaluates WORST-CASE legal continuations Expectimax: computes EXPECTED outcome with CHANCE |
| Trường | Nghĩa |
|---|---|
path_verified |
Chuỗi action là legal blank moves. |
goal_reached |
State cuối bằng goal đã chọn. |
optimality_proven |
Chỉ true khi thuật toán optimal, path hợp lệ, tới goal và termination là goal. |
frontier |
Node đang chờ xét. |
reached |
State/record đã biết trong reached, best_g hoặc best_depth. |
g(n) |
Path cost từ start tới node. |
h(n) |
Heuristic estimate tới goal. |
f(n) |
Priority của A*: g(n)+h(n). |
trace |
Bằng chứng từng bước: generate, expand, select, prune, accept/reject. |
web_run_status |
Trạng thái thật của browser capture: solved, partial/model, not solved hoặc tournament. |
source |
Phải là live_streamlit_browser_capture; nếu khác thì asset không được xem là GIF web thật. |
Ba tầng chứng minh phải đọc riêng:
Path legal != Goal reached
Goal reached != Optimal
Algorithm success != Solver chuẩn của 15-puzzle