Grcov report - solitaire

1

use std::collections::HashSet;

2

use std::fmt::Debug;

3

4

use bitvec::bitvec;

5

use bitvec::order::Lsb0;

6

use bitvec::vec::BitVec;

7

use delegate::delegate;

8

9

use itertools::Itertools;

10

use log::trace;

11

use merc_collections::BlockIndex;

12

use merc_collections::BlockPartition;

13

use merc_collections::scc_decomposition;

14

use merc_utilities::MercIndex;

15

16

use crate::AsGraph;

17

use crate::Edge;

18

use crate::PG;

19

use crate::Player;

20

use crate::Predecessors;

21

use crate::Priority;

22

use crate::Set;

23

use crate::VertexIndex;

24

25

/// Solves a solitaire game for the given player.

26

///

27

/// # Details

28

///

29

/// We assume that the input game is a trivial solitaire game, i.e., all

30

/// vertices are owned by the same player, and that the game is total. This

31

/// could be weakened to allow the other player to only do trivial moves, but

32

/// that is not yet necessary for our use case.

33

///

34

/// Solving is done by considering all subgames Gi restricted to priority `i`

35

/// belonging to `player`, and solving the simple solitaire game on each of

36

/// these subgames.

37

300

pub fn solve_solitaire_game<G: PG>(pg: &G) -> BitVec {

38

300

    debug_assert!(

39

20100

        pg.iter_vertices().all(|vertex| pg.owner(vertex) == Player::Even)

40

10000

            || pg.iter_vertices().all(|vertex| pg.owner(vertex) == Player::Odd),

41

        "solve_solitair_game requires a solitaire game"

42

);

43

44

300

    let mut winning_vertices = bitvec![usize, Lsb0; 0; pg.num_of_vertices()];

45

46

    // The game is solitaire, so all vertices are owned by the same player.

47

300

    let player = pg.owner(pg.initial_vertex());

48

49

1300

    for priority in 0..=pg.highest_priority().value() {

50

1300

        if Player::from_priority(&(Priority::new(priority))) != player {

51

            // Skip priorities that do not belong to the current player

52

600

            continue;

53

700

54

55

        // Restrict the game to the current priority.

56

700

        trace!("Solving subgame for max-priority {}", priority);

57

700

        let prio_subgame = PrioSubgame::new(pg, Priority::new(priority));

58

59

700

        let subgame_solution = solve_solitaire_simple(&prio_subgame, player);

60

48910

        for vertex in prio_subgame.iter_vertices() {

61

48910

            if subgame_solution[*vertex] {

62

4270

                winning_vertices.set(*vertex, true)

63

44640

64

65

66

67

300

    let predecessors = Predecessors::new(pg);

68

300

    backward_reachability(&predecessors, winning_vertices)

69

300

70

71

/// Solves a solitaire game that only contains two priorities, where `player`

72

/// should be the player that makes decisions.

73

///

74

/// # Details

75

///

76

/// For a solitaire game with only two priorities, the winning set for the player

77

/// is exactly those vertices that can reach a strongly connected component that

78

/// contains the highest priority. Note that the highest priority should belong

79

/// to the player.

80

700

fn solve_solitaire_simple<G: PG>(pg: &G, player: Player) -> BitVec {

81

700

    trace!("Subgame {{ {:?} }}, player {}", pg.iter_vertices().format(", "), player);

82

83

700

    let scc_partition = scc_decomposition(&AsGraph(pg), |_, _, _| true);

84

85

    // Determine vertices that are winning for the player in the restricted game, which are those that can reach a vertex with the current priority.

86

700

    let mut winning_vertices = bitvec![usize, Lsb0; 0; pg.num_of_vertices()];

87

88

700

    let subgame_vertices: HashSet<VertexIndex> = HashSet::from_iter(pg.iter_vertices());

89

90

    // Convert to block partition to compute reachability on the SCCs

91

700

    let block_partition = BlockPartition::<()>::from_indexed_partition(&scc_partition);

92

48342

    for scc in (0..scc_partition.num_of_blocks()).map(BlockIndex::new) {

93

48342

        if is_trivial_scc(pg, &block_partition, scc, &subgame_vertices) {

94

36066

            trace!("SCC {} is trivial, skipping", scc);

95

36066

            continue;

96

12276

97

98

12276

        if block_partition

99

12276

            .iter_block(scc)

100

            // TODO: This assumes that this is the highest priority, so priorities (0,1) for odd and (1,2) for even.

101

16126

            .any(|i| {

102

16126

                subgame_vertices.contains(&VertexIndex::new(i))

103

12491

                    && Player::from_priority(&pg.priority(VertexIndex::new(i))) == player

104

16126

})

105

106

6101

            for vertex in block_partition.iter_block(scc) {

107

6101

                if subgame_vertices.contains(&VertexIndex::new(vertex)) {

108

2383

                    winning_vertices.set(vertex, true);

109

2383

                    trace!("Player {} wins {} in SCC {}", player, vertex, scc);

110

3718

111

112

10352

113

114

115

700

    let predecessors = Predecessors::new(pg);

116

700

    backward_reachability(&predecessors, winning_vertices)

117

700

118

119

/// Returns true if the given SCC is trivial, i.e., it does not contain any

120

/// cycles. This is the case if the SCC contains only one vertex and that vertex

121

/// does not have a self-loop.

122

///

123

/// Only vertices contained in `subgame_vertices` are considered part of the SCC.

124

48342

fn is_trivial_scc<G: PG, T: Clone + Debug + Default>(

125

48342

    pg: &G,

126

48342

    partition: &BlockPartition<T>,

127

48342

    block: BlockIndex,

128

48342

    subgame_vertices: &HashSet<VertexIndex>,

129

48342

) -> bool {

130

48342

    if partition

131

48342

        .iter_block(block)

132

70000

        .filter(|&i| subgame_vertices.contains(&VertexIndex::new(i)))

133

48342

        .count()

134

        != 1

135

136

        // Contains at least 2 vertices, so non trivial.

137

187

        return false;

138

48155

139

140

    // Otherwise, must have a self loop.

141

48155

    let vertex = VertexIndex::new(

142

48155

        partition

143

50485

            .iter_block(block).find(|&i| subgame_vertices.contains(&VertexIndex::new(i)))

144

48155

            .expect("Block must contain at least one vertex"),

145

);

146

48155

    !pg.outgoing_edges(vertex).any(|edge| edge.to() == vertex)

147

48342

148

149

/// Computes the set of vertices reachable from the given initial vertices in

150

/// the given graph.

151

1000

fn backward_reachability(predecessors: &Predecessors, mut initial: BitVec) -> BitVec {

152

    // The set of vertices that are already visited.

153

1000

    let visited = &mut initial;

154

1000

    let mut queue: Vec<VertexIndex> = Vec::new();

155

156

6525

    for v in visited.iter_ones() {

157

6525

        queue.push(VertexIndex::new(v));

158

6525

159

160

12294

    while let Some(v) = queue.pop() {

161

13223

        for w in predecessors.predecessors(v) {

162

13223

            if !visited.get(w.index()).expect("Vertex must be in the reachable vector") {

163

4769

                trace!("Reached vertex {} from vertex {}", w, v);

164

4769

                visited.set(w.index(), true);

165

4769

                queue.push(w);

166

8454

167

168

169

170

1000

    initial

171

1000

172

173

/// A subgame Gi induced by mapping all priorities equal to `max_priority` to

174

/// the player's priority, and all other priorities to the opponent's priority.

175

pub struct PrioSubgame<'a, G: PG> {

176

    restricted: Set,

177

178

    /// The game that is being restricted.

179

    game: &'a G,

180

181

    /// The maximum priority in the sub-game.

182

    max_priority: Priority,

183

184

185

impl<G: PG> PrioSubgame<'_, G> {

186

    /// Create a new sub-game induced by the given strategy on the given game.

187

800

    pub fn new<'a>(game: &'a G, max_priority: Priority) -> PrioSubgame<'a, G> {

188

800

        let mut restricted = bitvec![usize, Lsb0; 0; game.num_of_vertices()];

189

75000

        for vertex in game.iter_vertices() {

190

75000

            if game.priority(vertex) <= max_priority {

191

49813

                restricted.set(vertex.value(), true);

192

49813

193

194

195

800

        PrioSubgame {

196

800

            game,

197

800

            restricted,

198

800

            max_priority,

199

800

200

800

201

202

203

impl<G: PG> PG for PrioSubgame<'_, G> {

204

    type Label = G::Label;

205

206

5403

    fn iter_vertices(&self) -> impl Iterator<Item = VertexIndex> + '_ {

207

        // Only consider vertices that are below the maximum priority.

208

5403

        self.restricted.iter_ones().map(VertexIndex::new)

209

5403

210

211

205668

    fn outgoing_edges<'a>(&'a self, vertex_index: VertexIndex) -> impl Iterator<Item = Edge<'a, G::Label>> + 'a {

212

205668

        debug_assert!(

213

205668

            self.restricted

214

205668

                .get(vertex_index.value())

215

205668

                .expect("Vertex must be in the restricted set"),

216

            "Vertex must be in the restricted set"

217

);

218

219

205668

        self.game.outgoing_edges(vertex_index).filter(move |edge| {

220

            // Only consider edges to vertices that are in the restricted set and follow the strategy.

221

200858

            self.restricted

222

200858

                .get(*edge.to())

223

200858

                .expect("Vertex must be in the restricted set")

224

200858

                == true

225

200858

})

226

205668

227

228

    fn highest_priority(&self) -> Priority {

229

        // Determine the highest priority in the restricted set.

230

        self.iter_vertices()

231

            .fold(Priority::new(0), |max, p| max.max(self.game.priority(p)))

232

233

234

    fn is_total(&self) -> bool {

235

        // The sub-game is total if every vertex in the restricted set has at least one outgoing edge.

236

        self.iter_vertices().all(|v| self.outgoing_edges(v).next().is_some())

237

238

239

12491

    fn priority(&self, vertex: VertexIndex) -> Priority {

240

12491

        debug_assert!(

241

12491

            self.restricted

242

12491

                .get(vertex.value())

243

12491

                .expect("Vertex must be in the restricted set"),

244

            "Vertex must be in the restricted set"

245

);

246

247

12491

        if self.game.priority(vertex) == self.max_priority {

248

            // Return the priority for the opponent.

249

1924

            if self.max_priority.is_multiple_of(2) {

250

1902

                Priority::new(2)

251

            } else {

252

22

                Priority::new(1)

253

254

        } else {

255

            // Return the priority for the opponent.

256

10567

            if self.max_priority.is_multiple_of(2) {

257

7200

                Priority::new(1)

258

            } else {

259

3367

                Priority::new(0)

260

261

262

12491

263

264

    delegate! {

265

        to self.game {

266

            fn initial_vertex(&self) -> VertexIndex;

267

51810

            fn num_of_vertices(&self) -> usize;

268

800

            fn num_of_edges(&self) -> usize;

269

            fn owner(&self, vertex: VertexIndex) -> Player;

270

271

272

273

274

/// A parity game where every player is now owned by given player, making this a

275

/// solitaire game.

276

#[cfg(test)]

277

struct SolitaireGame<'a, G: PG> {

278

    game: &'a G,

279

280

    player: Player,

281

282

283

#[cfg(test)]

284

impl<G: PG> SolitaireGame<'_, G> {

285

    /// Create a new solitaire game induced by the given strategy on the given game.

286

100

    fn new<'a>(game: &'a G, player: Player) -> SolitaireGame<'a, G> {

287

100

        SolitaireGame { game, player }

288

100

289

290

291

#[cfg(test)]

292

impl<G: PG> PG for SolitaireGame<'_, G> {

293

    type Label = G::Label;

294

295

40383

    fn owner(&self, _vertex: VertexIndex) -> Player {

296

        // All vertices are owned by the given player, making it a solitaire game.

297

40383

        self.player

298

40383

299

300

    delegate! {

301

        to self.game {

302

100

            fn initial_vertex(&self) -> VertexIndex;

303

16020

            fn num_of_vertices(&self) -> usize;

304

400

            fn num_of_edges(&self) -> usize;

305

800

            fn iter_vertices(&self) -> impl Iterator<Item = VertexIndex> + '_;

306

105792

            fn outgoing_edges<'a>(&'a self, vertex_index: VertexIndex) -> impl Iterator<Item = Edge<'a, G::Label>> + 'a;

307

67509

            fn priority(&self, vertex: VertexIndex) -> Priority;

308

100

            fn is_total(&self) -> bool;

309

100

            fn highest_priority(&self) -> Priority;

310

311

312

313

314

#[cfg(test)]

315

mod tests {

316

    use merc_io::DumpFiles;

317

    use merc_utilities::random_test;

318

319

    use crate::Player;

320

    use crate::parity_games::solitaire_game::SolitaireGame;

321

    use crate::random_parity_game;

322

    use crate::solve_solitaire_game;

323

    use crate::solve_zielonka;

324

    use crate::write_pg;

325

326

    #[test]

327

    #[cfg_attr(miri, ignore)] // Test is too slow under miri

328

1

    fn test_random_solitaire_game() {

329

100

        random_test(100, |rng| {

330

100

            let mut files = DumpFiles::new("test_random_solitaire_game");

331

100

            let pg = random_parity_game(rng, true, 100, 3, 3);

332

100

            let solitaire = SolitaireGame::new(&pg, Player::Even);

333

100

            files.dump("input.pg", |writer| write_pg(writer, &solitaire)).unwrap();

334

335

100

            let solution = solve_solitaire_game(&solitaire);

336

100

            let (expected_solution, _expected_strategy) = solve_zielonka(&solitaire, false);

337

338

100

            assert_eq!(

339

100

                solution, expected_solution[0],

340

                "The solution for the solitaire solver should match the zielonka solution"

341

);

342

100

})

343

1

344