Enum GameOutcome

Source

pub enum GameOutcome {
    Win,
    Draw,
    Lose,
}

Expand description

Outcome for the player whose turn it is. A draw is an infinite play.

Variants§

§

Win

§

Draw

§

Lose

Implementations§

Source §

impl GameOutcome

Source

fn from_win(win: bool) -> Self

Examples found in repository ?

crates/competitive/src/algorithm/game_analyzer/impartial.rs (line 309)

295    fn outcome(&mut self, state: &S, misere: bool) -> GameOutcome {
296        let win = memoized_wins(
297            state,
298            &mut self.outcomes[usize::from(misere)],
299            |s| {
300                if !misere && let Some(&value) = self.grundy.get(s) {
301                    return ControlFlow::Break(value != 0);
302                }
303                let moves = (self.moves)(s).into_iter().map(|n| n.to);
304                ControlFlow::Continue(moves)
305            },
306            |_, moves| moves.next(),
307            misere,
308        );
309        GameOutcome::from_win(win)
310    }
311
312    fn winning_moves(&mut self, state: &S, misere: bool) -> impl Iterator<Item = Neighbor<S, L>> {
313        (self.moves)(state).into_iter().filter(move |next| {
314            if !misere && let Some(&value) = self.grundy.get(&next.to) {
315                value == 0
316            } else {
317                self.outcome(&next.to, misere) == GameOutcome::Lose
318            }
319        })
320    }
321
322    fn sum_grundy(&mut self, state: &[S]) -> u64 {
323        match state {
324            [] => return 0,
325            [single] => return self.grundy(single),
326            _ => {}
327        }
328        let (xor, odd) = self.reduce_sum(state);
329        odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s))
330    }
331
332    #[allow(clippy::type_complexity)] // Sum states and labels both carry component information.
333    fn sum_winning_moves(&mut self, state: &[S]) -> Vec<Neighbor<Vec<S>, (usize, L)>> {
334        let xor = self.sum_grundy(state);
335        let mut result = Vec::new();
336        if xor == 0 {
337            return result;
338        }
339        for (i, component) in state.iter().enumerate() {
340            let target = xor ^ self.grundy(component);
341            for next in (self.moves)(component) {
342                if self.grundy(&next.to) == target {
343                    let mut to = state.to_vec();
344                    to[i] = next.to;
345                    result.push(Neighbor::new(to, (i, next.label)));
346                }
347            }
348        }
349        result
350    }
351
352    fn sum_outcome(&mut self, state: &[S], misere: bool) -> GameOutcome {
353        if state.is_empty() {
354            return GameOutcome::from_win(misere);
355        }
356        if let [single] = state {
357            return self.outcome(single, misere);
358        }
359        let win = if misere {
360            if let Some(&win) = self.sums.get(state) {
361                win
362            } else {
363                memoized_wins(
364                    &canonical_sum(state.to_vec(), &mut self.sum_ids),
365                    &mut self.sums,
366                    |_| ControlFlow::Continue((0, None)),
367                    |s, (i, moves)| {
368                        while *i < s.len() {
369                            if *i != 0 && s[*i - 1] == s[*i] {
370                                *i += 1;
371                                continue;
372                            }
373                            let iterator =
374                                moves.get_or_insert_with(|| (self.moves)(&s[*i]).into_iter());
375                            if let Some(next) = iterator.next() {
376                                let mut to = s.clone();
377                                to[*i] = next.to;
378                                return Some(canonical_sum(to, &mut self.sum_ids));
379                            }
380                            *i += 1;
381                            *moves = None;
382                        }
383                        None
384                    },
385                    true,
386                )
387            }
388        } else {
389            let (xor, odd) = self.reduce_sum(state);
390            if xor == 0 && odd.len() == 1 {
391                return self.outcome(odd.into_iter().next().unwrap(), false);
392            }
393            odd.into_iter().fold(xor, |value, s| value ^ self.grundy(s)) != 0
394        };
395        GameOutcome::from_win(win)
396    }

More examples

Hide additional examples

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 503)

501    fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
502        match state {
503            [] => return GameOutcome::from_win(misere),
504            [single] => return self.outcome(single, misere),
505            _ => {}
506        }
507        let indices = self.sum_indices(state);
508        if !misere {
509            self.solve_generalized_grundy();
510            return self.sum_normal_outcome(&indices);
511        }
512        let edges = &self.index.as_ref().unwrap().edges;
513        let root = self.sums.prepare(indices, edges);
514        self.sums.outcomes.values[root]
515    }
516
517    fn sum_normal_outcome(&self, state: &[usize]) -> GameOutcome {
518        let mut xor = 0;
519        let mut infinite = None;
520        for &v in state {
521            if let Some((value, _)) = self.generalized_grundy[v] {
522                xor ^= value;
523            } else if infinite.replace(v).is_some() {
524                return GameOutcome::Draw;
525            }
526        }
527        if let Some(v) = infinite {
528            let can_win = self.index.as_ref().unwrap().edges[v]
529                .iter()
530                .any(|&u| self.generalized_grundy[u].is_some_and(|(value, _)| value == xor));
531            if can_win {
532                GameOutcome::Win
533            } else {
534                GameOutcome::Draw
535            }
536        } else if xor == 0 {
537            GameOutcome::Lose
538        } else {
539            GameOutcome::Win
540        }
541    }
542
543    fn sum_indices(&mut self, state: &[G::Vertex]) -> Vec<usize> {
544        self.prepare();
545        state.iter().map(|&s| self.index_of(s)).collect()
546    }
547
548    fn prepare(&mut self) {
549        if self.index.is_some() {
550            return;
551        }
552        let vertices: Vec<_> = self.graph.vertices().collect();
553        let mut indices = self.graph.construct_vmap(|| None);
554        for (i, &v) in vertices.iter().enumerate() {
555            self.graph.vmap_set(&mut indices, v, Some(i));
556        }
557        let mut edges = vec![Vec::new(); vertices.len()];
558        let mut reverse = vec![Vec::new(); vertices.len()];
559        let mut seen = vec![None; vertices.len()];
560        for (i, &v) in vertices.iter().enumerate() {
561            for next in self.graph.neighbors(v) {
562                let j = self
563                    .graph
564                    .vmap_get(&indices, next.to)
565                    .expect("vertex is not enumerated by the graph");
566                if seen[j] != Some(i) {
567                    seen[j] = Some(i);
568                    edges[i].push(j);
569                    reverse[j].push(i);
570                }
571            }
572        }
573        self.index = Some(GraphIndex {
574            indices,
575            edges,
576            reverse,
577        });
578    }
579
580    fn index_of(&self, v: G::Vertex) -> usize {
581        self.graph
582            .vmap_get(&self.index.as_ref().unwrap().indices, v)
583            .expect("vertex is not enumerated by the graph")
584    }
585
586    fn solve_generalized_grundy(&mut self) {
587        let index = self.index.as_ref().unwrap();
588        let n = index.edges.len();
589        if self.generalized_grundy.len() == n {
590            return;
591        }
592        let mut values: Vec<Option<(u64, usize)>> = vec![None; n];
593        // Visit acyclic followers first, so DAGs need only one pass.
594        let reverse = UsizeGraph::new(n, |v: usize| index.reverse[v].iter().map(|&u| (u, ())));
595        let order = reverse.topological_sort();
596        if order.len() == n {
597            for (counter, v) in order.into_iter().enumerate() {
598                let mex = self.grundy.get(v).copied().flatten().unwrap_or_else(|| {
599                    let options = index.edges[v]
600                        .iter()
601                        .map(|&u| values[u].unwrap().0)
602                        .collect();
603                    game_mex(options)
604                });
605                values[v] = Some((mex, counter));
606            }
607            self.generalized_grundy = values;
608            return;
609        }
610        let mut queue: VecDeque<_> = order.into();
611        let mut queued = vec![false; n];
612        for &v in &queue {
613            queued[v] = true;
614        }
615        for (v, pending) in queued.iter_mut().enumerate() {
616            if !*pending {
617                *pending = true;
618                queue.push_back(v);
619            }
620        }
621        let mut counter = 0;
622        let mut options = vec![HashSet::new(); n];
623        let mut mexes = vec![0; n];
624        while let Some(v) = queue.pop_front() {
625            queued[v] = false;
626            let mex = mexes[v];
627            // Every unresolved option must be able to return to this mex.
628            let ready = index.edges[v]
629                .iter()
630                .all(|&u| values[u].is_some() || options[u].contains(&mex));
631            if !ready {
632                continue;
633            }
634            values[v] = Some((mex, counter));
635            counter += 1;
636            for &u in &index.reverse[v] {
637                if values[u].is_some() {
638                    continue;
639                }
640                let inserted = options[u].insert(mex);
641                if inserted {
642                    while options[u].contains(&mexes[u]) {
643                        mexes[u] += 1;
644                    }
645                }
646                // A larger value already had a follower at this vertex's mex.
647                if mex < mexes[u] && !queued[u] {
648                    queued[u] = true;
649                    queue.push_back(u);
650                }
651                if inserted {
652                    for &w in &index.reverse[u] {
653                        if queue.len() == n - counter {
654                            break; // All unresolved vertices are already queued.
655                        }
656                        if values[w].is_none() && !queued[w] && mexes[w] == mex {
657                            queued[w] = true;
658                            queue.push_back(w);
659                        }
660                    }
661                }
662            }
663        }
664        self.generalized_grundy = values;
665    }
666}
667
668impl GraphSums {
669    fn prepare(&mut self, state: Vec<usize>, components: &[Vec<usize>]) -> usize {
670        let state = Self::canonical(state, components);
671        if let Some(&root) = self.indices.get(&state) {
672            return root;
673        }
674        let root = self.outcomes.values.len();
675        self.indices.insert(state.clone(), root);
676        let mut edges = vec![Vec::new()];
677        let mut reverse = vec![Vec::new()];
678        let mut pending = VecDeque::from([(root, state)]);
679        while let Some((v, state)) = pending.pop_front() {
680            for (i, &component) in state.iter().enumerate() {
681                if i != 0 && state[i - 1] == component {
682                    continue;
683                }
684                for &next in &components[component] {
685                    let mut to = state.clone();
686                    to[i] = next;
687                    let to = Self::canonical(to, components);
688                    let u = *self.indices.entry(to).or_insert_with_key(|to| {
689                        let u = root + edges.len();
690                        pending.push_back((u, to.clone()));
691                        edges.push(Vec::new());
692                        reverse.push(Vec::new());
693                        u
694                    });
695                    edges[v - root].push(u);
696                }
697            }
698            edges[v - root].sort_unstable();
699            edges[v - root].dedup();
700            for &u in &edges[v - root] {
701                if u >= root {
702                    reverse[u - root].push(v);
703                }
704            }
705        }
706        self.outcomes.extend(&edges, &reverse, true);
707        root
708    }
709
710    fn canonical(mut state: Vec<usize>, components: &[Vec<usize>]) -> Vec<usize> {
711        state.retain(|&v| !components[v].is_empty());
712        state.sort_unstable();
713        state
714    }
715}
716
717impl GraphOutcomes {
718    fn extend(&mut self, edges: &[Vec<usize>], reverse: &[Vec<usize>], misere: bool) {
719        let start = self.values.len();
720        self.values.resize(start + edges.len(), GameOutcome::Draw);
721        self.winning.resize(start + edges.len(), None);
722        let mut remaining: Vec<_> = edges.iter().map(Vec::len).collect();
723        let mut queue = VecDeque::new();
724        for (i, next) in edges.iter().enumerate() {
725            let v = start + i;
726            if next.is_empty() {
727                self.values[v] = GameOutcome::from_win(misere);
728            } else if start != 0 {
729                // The old prefix is closed under moves; only the appended states need solving.
730                for &u in next {
731                    if u < start {
732                        match self.values[u] {
733                            GameOutcome::Lose => {
734                                self.values[v] = GameOutcome::Win;
735                                self.winning[v] = Some(u);
736                                break;
737                            }
738                            GameOutcome::Win => remaining[v - start] -= 1,
739                            GameOutcome::Draw => {}
740                        }
741                    }
742                }
743                if self.values[v] == GameOutcome::Draw && remaining[v - start] == 0 {
744                    self.values[v] = GameOutcome::Lose;
745                }
746            }
747            if self.values[v] != GameOutcome::Draw {
748                queue.push_back(v);
749            }
750        }
751        while let Some(v) = queue.pop_front() {
752            for &u in &reverse[v - start] {
753                if self.values[u] != GameOutcome::Draw {
754                    continue;
755                }
756                if self.values[v] == GameOutcome::Lose {
757                    self.values[u] = GameOutcome::Win;
758                    self.winning[u] = Some(v);
759                    queue.push_back(u);
760                } else {
761                    remaining[u - start] -= 1;
762                    if remaining[u - start] == 0 {
763                        self.values[u] = GameOutcome::Lose;
764                        queue.push_back(u);
765                    }
766                }
767            }
768        }
769    }