car_multi/patterns/
tournament.rs

1//! Tournament — rank competitors by pairwise comparative judgment.
2//!
3//! Each competitor produces one candidate answer to the task, then a fresh judge
4//! agent compares candidates **two at a time** and picks the better one. Unlike
5//! [`Vote`](crate::Vote) (single-shot majority over independent answers) or
6//! [`AdversarialReview`](crate::AdversarialReview) (pass/fail against a spec), a
7//! tournament produces a *relative ordering* — the blog-style "sort a large set
8//! by comparative judgment / run a bracket until a winner emerges" idiom.
9//!
10//! Single-elimination: competitors are paired each round, the judge picks a
11//! winner per pair, winners advance, and an odd one out gets a bye. After
12//! `ceil(log2(n))` rounds one winner remains. The round at which a competitor is
13//! eliminated yields a coarse ranking (later elimination = higher rank).
14//!
15//! Pairwise comparison is more reliable than asking a model to score N items on
16//! an absolute scale: a judge comparing exactly two answers has a much easier,
17//! lower-variance decision.
18
19use crate::budget::budget_skipped_output;
20use crate::error::MultiError;
21use crate::mailbox::Mailbox;
22use crate::runner::AgentRunner;
23use crate::shared::SharedInfra;
24use crate::types::{AgentOutput, AgentSpec};
25use serde::{Deserialize, Serialize};
26use std::sync::Arc;
27use tracing::instrument;
28
29/// One pairwise judgment in the bracket.
30#[derive(Debug, Clone, Serialize, Deserialize)]
31pub struct MatchResult {
32    /// 1-based round number.
33    pub round: u32,
34    /// Competitor name on side A.
35    pub a: String,
36    /// Competitor name on side B.
37    pub b: String,
38    /// The name that advanced (either `a` or `b`).
39    pub winner: String,
40    /// The judge's stated reason (best-effort; empty if unparseable).
41    pub rationale: String,
42}
43
44/// Result of a tournament.
45#[derive(Debug, Clone, Serialize, Deserialize)]
46pub struct TournamentResult {
47    pub task: String,
48    /// The competitors' initial candidate answers.
49    pub candidates: Vec<AgentOutput>,
50    /// Every pairwise judgment, in bracket order.
51    pub matches: Vec<MatchResult>,
52    /// The winning competitor's name (empty if no competitor produced an answer).
53    pub winner_name: String,
54    /// The winning competitor's answer.
55    pub winner_answer: String,
56    /// Competitor names from best to worst, by elimination round (the winner
57    /// first, then those eliminated in later rounds before earlier ones).
58    pub ranking: Vec<String>,
59}
60
61/// Rank competitors by single-elimination pairwise judgment.
62pub struct Tournament {
63    /// The competitors; each produces one candidate answer to the task.
64    pub competitors: Vec<AgentSpec>,
65    /// The judge agent: compares two candidates and picks the better. Always a
66    /// fresh agent per match (no carried context), like [`AdversarialReview`](crate::patterns::adversarial_review::AdversarialReview).
67    pub judge: AgentSpec,
68}
69
70impl Tournament {
71    pub fn new(competitors: Vec<AgentSpec>, judge: AgentSpec) -> Self {
72        Self { competitors, judge }
73    }
74
75    #[instrument(name = "multi.tournament", skip_all)]
76    pub async fn run(
77        &self,
78        task: &str,
79        runner: &Arc<dyn AgentRunner>,
80        infra: &SharedInfra,
81    ) -> Result<TournamentResult, MultiError> {
82        // Phase 1: each competitor produces a candidate answer (budget-gated).
83        let candidates = self.gather_candidates(task, runner, infra).await;
84
85        // Seed the bracket with competitors that actually produced an answer.
86        let mut alive: Vec<(String, String)> = candidates
87            .iter()
88            .filter(|o| o.succeeded())
89            .map(|o| (o.name.clone(), o.answer.clone()))
90            .collect();
91
92        let mut matches = Vec::new();
93        // Ranking accumulates losers in reverse: those eliminated later are
94        // better, so we push eliminations and reverse at the end.
95        let mut elimination_order: Vec<String> = Vec::new();
96
97        if alive.is_empty() {
98            return Ok(TournamentResult {
99                task: task.to_string(),
100                candidates,
101                matches,
102                winner_name: String::new(),
103                winner_answer: String::new(),
104                ranking: Vec::new(),
105            });
106        }
107
108        let mut round = 1;
109        while alive.len() > 1 {
110            let mut next: Vec<(String, String)> = Vec::new();
111            let mut i = 0;
112            while i + 1 < alive.len() {
113                let (name_a, ans_a) = alive[i].clone();
114                let (name_b, ans_b) = alive[i + 1].clone();
115
116                let (winner_side, rationale) = self
117                    .judge_pair(task, &name_a, &ans_a, &name_b, &ans_b, runner, infra)
118                    .await;
119
120                let (winner_name, winner_ans, loser_name) = match winner_side {
121                    Side::A => (name_a.clone(), ans_a.clone(), name_b.clone()),
122                    Side::B => (name_b.clone(), ans_b.clone(), name_a.clone()),
123                };
124                matches.push(MatchResult {
125                    round,
126                    a: name_a,
127                    b: name_b,
128                    winner: winner_name.clone(),
129                    rationale,
130                });
131                elimination_order.push(loser_name);
132                next.push((winner_name, winner_ans));
133                i += 2;
134            }
135            // Odd competitor out gets a bye to the next round.
136            if i < alive.len() {
137                next.push(alive[i].clone());
138            }
139            alive = next;
140            round += 1;
141        }
142
143        let (winner_name, winner_answer) = alive
144            .into_iter()
145            .next()
146            .unwrap_or_else(|| (String::new(), String::new()));
147
148        // Ranking: winner first, then losers from latest elimination to earliest.
149        let mut ranking = vec![winner_name.clone()];
150        ranking.extend(elimination_order.into_iter().rev());
151
152        Ok(TournamentResult {
153            task: task.to_string(),
154            candidates,
155            matches,
156            winner_name,
157            winner_answer,
158            ranking,
159        })
160    }
161
162    /// Run every competitor on the task, gated and recorded against the budget.
163    async fn gather_candidates(
164        &self,
165        task: &str,
166        runner: &Arc<dyn AgentRunner>,
167        infra: &SharedInfra,
168    ) -> Vec<AgentOutput> {
169        let mailbox = Arc::new(Mailbox::default());
170        enum Slot {
171            Spawned(usize),
172            Skipped(AgentOutput),
173        }
174        let mut handles: Vec<tokio::task::JoinHandle<Result<AgentOutput, MultiError>>> = Vec::new();
175        let mut slots: Vec<Slot> = Vec::new();
176
177        for spec in &self.competitors {
178            if let Err(e) = infra.begin_agent() {
179                slots.push(Slot::Skipped(budget_skipped_output(&spec.name, &e)));
180                continue;
181            }
182            let runner = Arc::clone(runner);
183            let spec = spec.clone();
184            let task = task.to_string();
185            let mailbox = Arc::clone(&mailbox);
186            // Provision the runtime before spawning (matches swarm), so the
187            // agent task never observes a half-registered tool set.
188            let rt = infra.make_runtime();
189            for tool in &spec.tools {
190                rt.register_tool(tool).await;
191            }
192            handles.push(tokio::spawn(async move {
193                runner.run(&spec, &task, &rt, &mailbox).await
194            }));
195            slots.push(Slot::Spawned(handles.len() - 1));
196        }
197
198        let mut results: Vec<Option<_>> = futures::future::join_all(handles)
199            .await
200            .into_iter()
201            .map(Some)
202            .collect();
203        let mut outputs = Vec::new();
204        for (i, slot) in slots.into_iter().enumerate() {
205            let idx = match slot {
206                Slot::Skipped(out) => {
207                    outputs.push(out);
208                    continue;
209                }
210                Slot::Spawned(idx) => idx,
211            };
212            match results.get_mut(idx).and_then(Option::take) {
213                Some(Ok(Ok(out))) => {
214                    infra.record_output(&out);
215                    outputs.push(out);
216                }
217                Some(Ok(Err(e))) => {
218                    outputs.push(failed_output(&self.competitors[i].name, e.to_string()))
219                }
220                Some(Err(e)) => outputs.push(failed_output(
221                    &self.competitors[i].name,
222                    format!("join error: {e}"),
223                )),
224                None => outputs.push(failed_output(
225                    &self.competitors[i].name,
226                    "internal: missing join result".into(),
227                )),
228            }
229        }
230        outputs
231    }
232
233    /// Ask the judge to pick the better of two candidates. Defaults to side A on
234    /// a budget denial, judge error, or unparseable verdict (deterministic).
235    async fn judge_pair(
236        &self,
237        task: &str,
238        name_a: &str,
239        ans_a: &str,
240        name_b: &str,
241        ans_b: &str,
242        runner: &Arc<dyn AgentRunner>,
243        infra: &SharedInfra,
244    ) -> (Side, String) {
245        if infra.begin_agent().is_err() {
246            return (
247                Side::A,
248                "budget exhausted: defaulted to first candidate".into(),
249            );
250        }
251
252        let judge_task = format!(
253            r#"You are judging a head-to-head comparison for this task:
254
255## Task
256{task}
257
258## Candidate A
259{ans_a}
260
261## Candidate B
262{ans_b}
263
264Decide which candidate better accomplishes the task. Be decisive.
265Respond with a JSON object:
266```json
267{{"winner": "A", "rationale": "one sentence why"}}
268```
269`winner` must be exactly "A" or "B"."#,
270        );
271
272        let mut judge_spec = self.judge.clone();
273        // Make the judge fresh per match so prior matches can't bias it.
274        judge_spec.name = format!("{}_{}_vs_{}", self.judge.name, name_a, name_b);
275
276        let mailbox = Mailbox::default();
277        let rt = infra.make_runtime();
278        match runner.run(&judge_spec, &judge_task, &rt, &mailbox).await {
279            Ok(out) => {
280                infra.record_output(&out);
281                parse_verdict(&out.answer)
282            }
283            Err(e) => (Side::A, format!("judge failed, defaulted to A: {e}")),
284        }
285    }
286}
287
288#[derive(Clone, Copy)]
289enum Side {
290    A,
291    B,
292}
293
294fn failed_output(name: &str, error: String) -> AgentOutput {
295    AgentOutput {
296        name: name.to_string(),
297        answer: String::new(),
298        turns: 0,
299        tool_calls: 0,
300        duration_ms: 0.0,
301        error: Some(error),
302        outcome: None,
303        tokens: None,
304        tools_used: Vec::new(),
305    }
306}
307
308/// Parse the judge's verdict: prefer a JSON `{"winner": "A"|"B", "rationale"}`,
309/// else look for an explicit "Candidate A/B" / "winner: A/B" phrase, else the
310/// first *standalone* A/B token. Defaults to A only when nothing matches.
311///
312/// The fallback deliberately does NOT do a naive `find('A')`/`find('B')` over the
313/// whole string — almost any prose contains an 'A' inside a common word before
314/// the meaningful verdict, which would silently bias every match to A.
315fn parse_verdict(answer: &str) -> (Side, String) {
316    if let Some(json) = car_ir::json_extract::extract_json_object(answer) {
317        if let Ok(v) = serde_json::from_str::<serde_json::Value>(&json) {
318            let rationale = v
319                .get("rationale")
320                .and_then(|r| r.as_str())
321                .unwrap_or("")
322                .to_string();
323            if let Some(w) = v.get("winner").and_then(|w| w.as_str()) {
324                let side = if w.trim().eq_ignore_ascii_case("b") {
325                    Side::B
326                } else {
327                    Side::A
328                };
329                return (side, rationale);
330            }
331        }
332    }
333
334    // Fallback: never echo the full (possibly huge) answer into rationale.
335    const FALLBACK_RATIONALE: &str = "verdict parsed heuristically (no JSON winner field)";
336    let upper = answer.to_uppercase();
337
338    // 1. Explicit phrases, earliest one wins.
339    let phrase_a = ["CANDIDATE A", "WINNER: A", "WINNER A", "\"A\"", "ANSWER A"]
340        .iter()
341        .filter_map(|p| upper.find(p))
342        .min();
343    let phrase_b = ["CANDIDATE B", "WINNER: B", "WINNER B", "\"B\"", "ANSWER B"]
344        .iter()
345        .filter_map(|p| upper.find(p))
346        .min();
347    match (phrase_a, phrase_b) {
348        (Some(a), Some(b)) => {
349            return (
350                if b < a { Side::B } else { Side::A },
351                FALLBACK_RATIONALE.into(),
352            )
353        }
354        (Some(_), None) => return (Side::A, FALLBACK_RATIONALE.into()),
355        (None, Some(_)) => return (Side::B, FALLBACK_RATIONALE.into()),
356        (None, None) => {}
357    }
358
359    // 2. First standalone 'A' or 'B' token (non-alphanumeric on both sides).
360    if let Some(side) = first_standalone_ab(&upper) {
361        return (side, FALLBACK_RATIONALE.into());
362    }
363
364    // 3. Nothing decisive — deterministic default.
365    (Side::A, FALLBACK_RATIONALE.into())
366}
367
368/// First standalone `A`/`B` (surrounded by non-alphanumerics, so not the 'a' in
369/// "candidate" or the 'b' in "because"). `None` if there is no isolated token.
370fn first_standalone_ab(upper: &str) -> Option<Side> {
371    let bytes = upper.as_bytes();
372    for (i, &c) in bytes.iter().enumerate() {
373        if c == b'A' || c == b'B' {
374            let prev_alnum = i > 0 && bytes[i - 1].is_ascii_alphanumeric();
375            let next_alnum = i + 1 < bytes.len() && bytes[i + 1].is_ascii_alphanumeric();
376            if !prev_alnum && !next_alnum {
377                return Some(if c == b'B' { Side::B } else { Side::A });
378            }
379        }
380    }
381    None
382}
383
384#[cfg(test)]
385mod tests {
386    use super::*;
387    use car_engine::Runtime;
388
389    /// A competitor echoes its name; the judge always picks the candidate whose
390    /// answer sorts later alphabetically (deterministic, so we can assert).
391    struct ScriptedRunner;
392
393    #[async_trait::async_trait]
394    impl AgentRunner for ScriptedRunner {
395        async fn run(
396            &self,
397            spec: &AgentSpec,
398            task: &str,
399            _runtime: &Runtime,
400            _mailbox: &Mailbox,
401        ) -> Result<AgentOutput, MultiError> {
402            // Judge specs carry the rendered candidates in the task; pick the
403            // one whose block sorts later by comparing the two answer blocks.
404            let answer = if spec.name.contains("_vs_") {
405                let a = extract_block(task, "## Candidate A");
406                let b = extract_block(task, "## Candidate B");
407                let winner = if b > a { "B" } else { "A" };
408                format!("{{\"winner\": \"{winner}\", \"rationale\": \"later sorts higher\"}}")
409            } else {
410                spec.name.clone()
411            };
412            Ok(AgentOutput {
413                name: spec.name.clone(),
414                answer,
415                turns: 1,
416                tool_calls: 0,
417                duration_ms: 1.0,
418                error: None,
419                outcome: None,
420                tokens: None,
421                tools_used: Vec::new(),
422            })
423        }
424    }
425
426    fn extract_block<'a>(task: &'a str, header: &str) -> &'a str {
427        task.split(header)
428            .nth(1)
429            .map(|s| s.split("##").next().unwrap_or("").trim())
430            .unwrap_or("")
431    }
432
433    #[tokio::test]
434    async fn single_elimination_picks_alphabetical_max() {
435        let competitors = vec![
436            AgentSpec::new("alpha", ""),
437            AgentSpec::new("bravo", ""),
438            AgentSpec::new("charlie", ""),
439            AgentSpec::new("delta", ""),
440        ];
441        let judge = AgentSpec::new("judge", "pick the better answer");
442        let runner: Arc<dyn AgentRunner> = Arc::new(ScriptedRunner);
443        let infra = SharedInfra::new();
444
445        let r = Tournament::new(competitors, judge)
446            .run("rank these", &runner, &infra)
447            .await
448            .unwrap();
449
450        // Each competitor's answer is its name; judge prefers later-sorting, so
451        // "delta" wins the whole bracket.
452        assert_eq!(r.winner_name, "delta");
453        assert_eq!(r.winner_answer, "delta");
454        // 4 competitors -> 2 + 1 = 3 matches.
455        assert_eq!(r.matches.len(), 3);
456        assert_eq!(r.ranking.first().unwrap(), "delta");
457        assert_eq!(r.ranking.len(), 4);
458    }
459
460    #[tokio::test]
461    async fn odd_competitor_gets_a_bye() {
462        let competitors = vec![
463            AgentSpec::new("alpha", ""),
464            AgentSpec::new("bravo", ""),
465            AgentSpec::new("charlie", ""),
466        ];
467        let judge = AgentSpec::new("judge", "");
468        let runner: Arc<dyn AgentRunner> = Arc::new(ScriptedRunner);
469        let infra = SharedInfra::new();
470
471        let r = Tournament::new(competitors, judge)
472            .run("rank", &runner, &infra)
473            .await
474            .unwrap();
475
476        // 3 competitors: round 1 has one match (alpha vs bravo) + charlie bye;
477        // round 2 matches the winner vs charlie => 2 matches total.
478        assert_eq!(r.matches.len(), 2);
479        assert_eq!(r.winner_name, "charlie"); // sorts latest of {bravo, charlie}
480    }
481
482    #[test]
483    fn parse_verdict_handles_prose_not_just_json() {
484        // The old naive find('A')/find('B') mis-judged all of these to A.
485        let (s, _) = parse_verdict("Candidate B is clearly better, it covers more cases.");
486        assert!(matches!(s, Side::B), "phrase 'Candidate B' should win");
487        let (s, _) = parse_verdict("After careful analysis, B.");
488        assert!(matches!(s, Side::B), "standalone trailing 'B' should win");
489        let (s, _) = parse_verdict("Answer A is the stronger submission.");
490        assert!(matches!(s, Side::A));
491        // JSON path still authoritative even with prose around it.
492        let (s, r) = parse_verdict("I think... {\"winner\": \"B\", \"rationale\": \"x\"}");
493        assert!(matches!(s, Side::B));
494        assert_eq!(r, "x");
495    }
496
497    #[test]
498    fn parse_verdict_does_not_leak_full_answer_on_fallback() {
499        let huge = format!("Candidate B wins. {}", "blah ".repeat(500));
500        let (_, rationale) = parse_verdict(&huge);
501        assert!(
502            rationale.len() < 100,
503            "fallback rationale must not echo the whole answer"
504        );
505    }
506
507    #[tokio::test]
508    async fn budget_cap_limits_competitors() {
509        let competitors: Vec<AgentSpec> = (0..4)
510            .map(|i| AgentSpec::new(&format!("c{i}"), ""))
511            .collect();
512        let judge = AgentSpec::new("judge", "");
513        let runner: Arc<dyn AgentRunner> = Arc::new(ScriptedRunner);
514        // Allow only 2 competitor spawns (no budget for judges either).
515        let infra = SharedInfra::new().with_budget(crate::BudgetLimits {
516            max_agents: Some(2),
517            ..Default::default()
518        });
519
520        let r = Tournament::new(competitors, judge)
521            .run("rank", &runner, &infra)
522            .await
523            .unwrap();
524
525        let produced = r.candidates.iter().filter(|o| o.succeeded()).count();
526        assert_eq!(produced, 2, "only two competitors fit the agent budget");
527    }
528}
car_multi/patterns/tournament.rs

car_multi/patterns/
tournament.rs
