Grcov report - solitaire

1

use std::fmt::Debug;

2

3

use bitvec::bitvec;

4

use bitvec::order::Lsb0;

5

use bitvec::vec::BitVec;

6

use delegate::delegate;

7

use itertools::Itertools;

8

use log::trace;

9

10

use merc_collections::BlockIndex;

11

use merc_collections::BlockPartition;

12

use merc_collections::scc_decomposition;

13

use merc_utilities::MercIndex;

14

15

use crate::AsGraph;

16

use crate::Edge;

17

use crate::PG;

18

use crate::Player;

19

use crate::Pred;

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

500

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

38

500

    debug_assert!(

39

30200

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

40

20000

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

41

        "solve_solitair_game requires a solitaire game"

42

);

43

44

500

    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

500

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

48

500

    let predecessors = Predecessors::new(pg);

49

50

2300

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

51

2300

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

52

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

53

1100

            continue;

54

1200

55

56

        // Restrict the game to the current priority.

57

1200

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

58

1200

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

59

60

1200

        let subgame_solution = solve_solitaire_simple(&prio_subgame, player);

61

84128

        for vertex in prio_subgame.iter_vertices() {

62

84128

            if subgame_solution[*vertex] {

63

4190

                winning_vertices.set(*vertex, true)

64

79938

65

66

67

68

500

    backward_reachability(&predecessors, winning_vertices)

69

500

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

1200

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

81

1200

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

82

83

1200

    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

1200

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

87

88

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

89

1200

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

90

83487

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

91

83487

        if is_trivial_scc(pg, &block_partition, scc) {

92

64349

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

93

64349

            continue;

94

19138

95

96

19138

        if block_partition

97

19138

            .iter_block(scc)

98

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

99

19430

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

100

101

2368

            for vertex in block_partition.iter_block(scc) {

102

2368

                winning_vertices.set(vertex, true);

103

2368

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

104

105

17234

106

107

108

1200

    backward_reachability(pg, winning_vertices)

109

1200

110

111

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

112

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

113

/// does not have a self-loop.

114

83487

fn is_trivial_scc<G: PG, T: Clone + Debug + Default>(pg: &G, partition: &BlockPartition<T>, block: BlockIndex) -> bool {

115

83487

    if partition.iter_block(block).count() != 1 {

116

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

117

241

        return false;

118

83246

119

120

    // Otherwise, must have a self loop.

121

83246

    let vertex = VertexIndex::new(

122

83246

        partition

123

83246

            .iter_block(block)

124

83246

            .next()

125

83246

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

126

);

127

83246

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

128

83487

129

130

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

131

/// the given graph.

132

1700

fn backward_reachability<P: Pred>(predecessors: &P, mut initial: BitVec) -> BitVec {

133

    // The set of vertices that are already visited.

134

1700

    let visited = &mut initial;

135

1700

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

136

137

6450

    for v in visited.iter_ones() {

138

6450

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

139

6450

140

141

13016

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

142

13096

        for w in predecessors.predecessors(v) {

143

13096

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

144

4866

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

145

4866

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

146

4866

                queue.push(w);

147

8230

148

149

150

151

1700

    initial

152

1700

153

154

/// A subgame induced by restricting vertices to a given set.

155

pub struct Subgame<'a, G: PG, P: Pred> {

156

    /// Vertices that are part of the subgame.

157

    restricted: Set,

158

159

    /// The game that is being restricted.

160

    game: &'a G,

161

162

    /// Predecessor provider for the original game.

163

    predecessors: P,

164

165

166

impl<'a, G: PG, P: Pred> Subgame<'a, G, P> {

167

    /// Create a new subgame induced by the given restricted-vertex set.

168

1400

    pub fn new(game: &'a G, restricted: Set, predecessors: P) -> Subgame<'a, G, P> {

169

1400

        debug_assert_eq!(

170

1400

            restricted.len(),

171

1400

            game.num_of_vertices(),

172

            "Restricted set must have one bit per vertex"

173

);

174

175

1400

        Subgame {

176

1400

            restricted,

177

1400

            game,

178

1400

            predecessors,

179

1400

180

1400

181

182

183

impl<G: PG, P: Pred> PG for Subgame<'_, G, P> {

184

    type Label = G::Label;

185

186

8257

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

187

8257

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

188

8257

189

190

225687

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

191

225687

        debug_assert!(

192

225687

            self.restricted

193

225687

                .get(vertex_index.value())

194

225687

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

195

            "Vertex {vertex_index} is not in the restricted set"

196

);

197

198

246239

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

199

246239

            self.restricted

200

246239

                .get(*edge.to())

201

246239

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

202

246239

                == true

203

246239

})

204

225687

205

206

    fn highest_priority(&self) -> Priority {

207

        self.iter_vertices()

208

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

209

210

211

    fn is_total(&self) -> bool {

212

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

213

214

215

    delegate! {

216

        to self.game {

217

            fn initial_vertex(&self) -> VertexIndex;

218

87828

            fn num_of_vertices(&self) -> usize;

219

100

            fn num_of_edges(&self) -> usize;

220

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

221

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

222

223

224

225

226

impl<G: PG, P: Pred> Pred for Subgame<'_, G, P> {

227

6334

    fn predecessors(&self, vertex_index: VertexIndex) -> impl Iterator<Item = VertexIndex> + '_ {

228

6334

        debug_assert!(

229

6334

            self.restricted

230

6334

                .get(vertex_index.value())

231

6334

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

232

            "Vertex must be in the restricted set"

233

);

234

235

11173

        self.predecessors.predecessors(vertex_index).filter(move |from| {

236

11173

            self.restricted

237

11173

                .get(from.value())

238

11173

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

239

11173

                == true

240

11173

})

241

6334

242

243

244

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

245

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

246

pub struct PrioSubgame<'a, G: PG, P: Pred = Predecessors<'a>> {

247

    /// The restricted subgame.

248

    subgame: Subgame<'a, G, P>,

249

250

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

251

    max_priority: Priority,

252

253

254

impl<'a, G: PG> PrioSubgame<'a, G, Predecessors<'a>> {

255

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

256

100

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

257

100

        PrioSubgame::with_predecessors(game, max_priority, Predecessors::new(game))

258

100

259

260

261

impl<'a, G: PG, P: Pred> PrioSubgame<'a, G, P> {

262

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

263

    /// using the given predecessor provider.

264

1300

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

265

1300

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

266

125000

        for vertex in game.iter_vertices() {

267

125000

            if game.priority(vertex) <= max_priority {

268

85041

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

269

85041

270

271

272

1300

        PrioSubgame {

273

1300

            subgame: Subgame::new(game, restricted, predecessors),

274

1300

            max_priority,

275

1300

276

1300

277

278

279

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

280

    type Label = G::Label;

281

282

19430

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

283

19430

        debug_assert!(

284

19430

            self.subgame

285

19430

                .restricted

286

19430

                .get(vertex.value())

287

19430

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

288

            "Vertex must be in the restricted set"

289

);

290

291

19430

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

292

            // Return the priority for the opponent.

293

1904

            if self.max_priority.is_multiple_of(2) {

294

1855

                Priority::new(2)

295

            } else {

296

49

                Priority::new(1)

297

298

        } else {

299

            // Return the priority for the opponent.

300

17526

            if self.max_priority.is_multiple_of(2) {

301

10587

                Priority::new(1)

302

            } else {

303

6939

                Priority::new(0)

304

305

306

19430

307

308

    delegate! {

309

        to self.subgame {

310

6013

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

311

178145

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

312

            fn highest_priority(&self) -> Priority;

313

            fn is_total(&self) -> bool;

314

            fn initial_vertex(&self) -> VertexIndex;

315

87828

            fn num_of_vertices(&self) -> usize;

316

100

            fn num_of_edges(&self) -> usize;

317

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

318

319

320

321

322

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

323

4190

    fn predecessors(&self, vertex_index: VertexIndex) -> impl Iterator<Item = VertexIndex> + '_ {

324

4190

        self.subgame.predecessors(vertex_index)

325

4190

326

327

328

#[cfg(test)]

329

mod tests {

330

    use delegate::delegate;

331

332

    use merc_io::DumpFiles;

333

    use merc_utilities::random_test;

334

335

    use crate::Edge;

336

    use crate::PG;

337

    use crate::Player;

338

    use crate::Priority;

339

    use crate::VertexIndex;

340

    use crate::random_parity_game;

341

    use crate::solve_solitaire_game;

342

    use crate::solve_zielonka;

343

    use crate::write_pg;

344

345

    #[test]

346

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

347

1

    fn test_random_solitaire_game() {

348

100

        random_test(100, |rng| {

349

100

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

350

100

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

351

100

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

352

100

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

353

354

100

            let solution = solve_solitaire_game(&solitaire);

355

100

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

356

357

100

            assert_eq!(

358

100

                solution, expected_solution[0],

359

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

360

);

361

100

})

362

1

363

364

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

365

    /// solitaire game.

366

    struct SolitaireGame<'a, G: PG> {

367

        game: &'a G,

368

369

        player: Player,

370

371

372

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

373

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

374

100

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

375

100

            SolitaireGame { game, player }

376

100

377

378

379

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

380

        type Label = G::Label;

381

382

48348

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

383

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

384

48348

            self.player

385

48348

386

387

        delegate! {

388

            to self.game {

389

100

                fn initial_vertex(&self) -> VertexIndex;

390

15999

                fn num_of_vertices(&self) -> usize;

391

200

                fn num_of_edges(&self) -> usize;

392

800

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

393

78490

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

394

67488

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

395

100

                fn is_total(&self) -> bool;

396

100

                fn highest_priority(&self) -> Priority;

397

398

399

400