[Merged by Bors] - feat(set_theory/game): short games, boards, and domineering #1540
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
semorrison
force-pushed
the
domineering
branch
from
a275993
to
ed4c53e
Compare
robertylewis
added
the
awaiting-review
|
Obviously this, as some "recreational maths", is low priority, but I'll assign to @rwbarton as the only person who's previously been interested. :-) |
|
I'll take a look after the linting errors are addressed: https://github.com/leanprover-community/mathlib/runs/475593766#step:12:16 |
|
@bryangingechen, I've fixed up the linting problems. |
|
Thanks, I'll try to take a look this week. Update (2020-03-11): I have been looking at this, but it's taking a while since I started looking over all of |
bryangingechen
requested changes
Apr 12, 2020
There was a problem hiding this comment.
Overall this looks good to me! Mainly I would like the lines to be within the <100 limit if possible, and I also made a bunch of mostly proof golf suggestions, though some of those might break after you merge in master.
It's nice to see computable definitions put to work in Lean. The real test of short and state will be how easy it will be to define other games, so let's try and get this in quickly and then continue the experimentation in future PRs.
bryangingechen
added
awaiting-author
Co-Authored-By: Bryan Gin-ge Chen <bryangingechen@gmail.com>
… into domineering
|
Sorry about the line lengths, that PR was particularly egregious. Perhaps we need a linter. :-) Thanks very much for the review comments, they were all helpful! (And now I want to go off and tell mathlib about Hex. :-) |
bryangingechen
approved these changes
Apr 12, 2020
|
bors r+ |
|
👎 Rejected by label |
bryangingechen
removed
the
awaiting-author
github-actions
bot
added
the
ready-to-merge
|
bors r+ |
bors bot
pushed a commit
that referenced
this pull request
Apr 12, 2020
This is a do-over of my previous attempt to implement the combinatorial game of domineering. This time, we get a nice clean definition, and it computes!
To achieve this, I follow Reid's advice: generalise! We define
```
class state (S : Type u) :=
(turn_bound : S → ℕ)
(L : S → finset S)
(R : S → finset S)
(left_bound : ∀ {s t : S} (m : t ∈ L s), turn_bound t < turn_bound s)
(right_bound : ∀ {s t : S} (m : t ∈ R s), turn_bound t < turn_bound s)
```
a typeclass describing `S` as "the state of a game", and provide `pgame.of [state S] : S \to pgame`.
This allows a short and straightforward definition of Domineering:
```lean
/-- A Domineering board is an arbitrary finite subset of `ℤ × ℤ`. -/
def board := finset (ℤ × ℤ)
...
/-- The instance describing allowed moves on a Domineering board. -/
instance state : state board :=
{ turn_bound := λ s, s.card / 2,
L := λ s, (left s).image (move_left s),
R := λ s, (right s).image (move_right s),
left_bound := _
right_bound := _, }
```
which computes:
```
example : (domineering ([(0,0), (0,1), (1,0), (1,1)].to_finset) ≈ pgame.of_lists [1] [-1]) := dec_trivial
```
Build succeeded |
Pull request successfully merged into master. |
bors
bot
changed the title
b-mehta
pushed a commit
that referenced
this pull request
Apr 13, 2020
This is a do-over of my previous attempt to implement the combinatorial game of domineering. This time, we get a nice clean definition, and it computes!
To achieve this, I follow Reid's advice: generalise! We define
```
class state (S : Type u) :=
(turn_bound : S → ℕ)
(L : S → finset S)
(R : S → finset S)
(left_bound : ∀ {s t : S} (m : t ∈ L s), turn_bound t < turn_bound s)
(right_bound : ∀ {s t : S} (m : t ∈ R s), turn_bound t < turn_bound s)
```
a typeclass describing `S` as "the state of a game", and provide `pgame.of [state S] : S \to pgame`.
This allows a short and straightforward definition of Domineering:
```lean
/-- A Domineering board is an arbitrary finite subset of `ℤ × ℤ`. -/
def board := finset (ℤ × ℤ)
...
/-- The instance describing allowed moves on a Domineering board. -/
instance state : state board :=
{ turn_bound := λ s, s.card / 2,
L := λ s, (left s).image (move_left s),
R := λ s, (right s).image (move_right s),
left_bound := _
right_bound := _, }
```
which computes:
```
example : (domineering ([(0,0), (0,1), (1,0), (1,1)].to_finset) ≈ pgame.of_lists [1] [-1]) := dec_trivial
```
anrddh
pushed a commit
to anrddh/mathlib
that referenced
this pull request
May 15, 2020
…er-community#1540) This is a do-over of my previous attempt to implement the combinatorial game of domineering. This time, we get a nice clean definition, and it computes! To achieve this, I follow Reid's advice: generalise! We define ``` class state (S : Type u) := (turn_bound : S → ℕ) (L : S → finset S) (R : S → finset S) (left_bound : ∀ {s t : S} (m : t ∈ L s), turn_bound t < turn_bound s) (right_bound : ∀ {s t : S} (m : t ∈ R s), turn_bound t < turn_bound s) ``` a typeclass describing `S` as "the state of a game", and provide `pgame.of [state S] : S \to pgame`. This allows a short and straightforward definition of Domineering: ```lean /-- A Domineering board is an arbitrary finite subset of `ℤ × ℤ`. -/ def board := finset (ℤ × ℤ) ... /-- The instance describing allowed moves on a Domineering board. -/ instance state : state board := { turn_bound := λ s, s.card / 2, L := λ s, (left s).image (move_left s), R := λ s, (right s).image (move_right s), left_bound := _ right_bound := _, } ``` which computes: ``` example : (domineering ([(0,0), (0,1), (1,0), (1,1)].to_finset) ≈ pgame.of_lists [1] [-1]) := dec_trivial ```
anrddh
pushed a commit
to anrddh/mathlib
that referenced
this pull request
May 16, 2020
…er-community#1540) This is a do-over of my previous attempt to implement the combinatorial game of domineering. This time, we get a nice clean definition, and it computes! To achieve this, I follow Reid's advice: generalise! We define ``` class state (S : Type u) := (turn_bound : S → ℕ) (L : S → finset S) (R : S → finset S) (left_bound : ∀ {s t : S} (m : t ∈ L s), turn_bound t < turn_bound s) (right_bound : ∀ {s t : S} (m : t ∈ R s), turn_bound t < turn_bound s) ``` a typeclass describing `S` as "the state of a game", and provide `pgame.of [state S] : S \to pgame`. This allows a short and straightforward definition of Domineering: ```lean /-- A Domineering board is an arbitrary finite subset of `ℤ × ℤ`. -/ def board := finset (ℤ × ℤ) ... /-- The instance describing allowed moves on a Domineering board. -/ instance state : state board := { turn_bound := λ s, s.card / 2, L := λ s, (left s).image (move_left s), R := λ s, (right s).image (move_right s), left_bound := _ right_bound := _, } ``` which computes: ``` example : (domineering ([(0,0), (0,1), (1,0), (1,1)].to_finset) ≈ pgame.of_lists [1] [-1]) := dec_trivial ```
cipher1024
pushed a commit
to cipher1024/mathlib
that referenced
this pull request
Mar 15, 2022
…er-community#1540) This is a do-over of my previous attempt to implement the combinatorial game of domineering. This time, we get a nice clean definition, and it computes! To achieve this, I follow Reid's advice: generalise! We define ``` class state (S : Type u) := (turn_bound : S → ℕ) (L : S → finset S) (R : S → finset S) (left_bound : ∀ {s t : S} (m : t ∈ L s), turn_bound t < turn_bound s) (right_bound : ∀ {s t : S} (m : t ∈ R s), turn_bound t < turn_bound s) ``` a typeclass describing `S` as "the state of a game", and provide `pgame.of [state S] : S \to pgame`. This allows a short and straightforward definition of Domineering: ```lean /-- A Domineering board is an arbitrary finite subset of `ℤ × ℤ`. -/ def board := finset (ℤ × ℤ) ... /-- The instance describing allowed moves on a Domineering board. -/ instance state : state board := { turn_bound := λ s, s.card / 2, L := λ s, (left s).image (move_left s), R := λ s, (right s).image (move_right s), left_bound := _ right_bound := _, } ``` which computes: ``` example : (domineering ([(0,0), (0,1), (1,0), (1,1)].to_finset) ≈ pgame.of_lists [1] [-1]) := dec_trivial ```
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This is a do-over of my previous attempt to implement the combinatorial game of domineering. This time, we get a nice clean definition, and it computes!
To achieve this, I follow Reid's advice: generalise! We define
a typeclass describing
Sas "the state of a game", and providepgame.of [state S] : S \to pgame.This allows a short and straightforward definition of Domineering:
which computes: