gno4.gno
7.76 Kb · 292 lines
1// Package gno4 is a Connect Four engine: the rules, and nothing else.
2//
3// It imports no chain package, takes no address and reads no height, so it is
4// unit-testable with no node and a realm that uses it stays thin. Everything a
5// caller needs to know about a position is derivable from a [Board], and a
6// whole game round-trips through a string of at most 42 digits ([Board.Encode]).
7//
8// Live demo: [r/moul/gno4](/r/moul/gno4).
9package gno4
10
11import "errors"
12
13// Cols and Rows are the standard board. They are constants rather than fields
14// because every rule below, the win scan in particular, is written against
15// them; a variable board is a different package, not a flag on this one.
16const (
17 Cols = 7
18 Rows = 6
19)
20
21// Disc identifies whose disc occupies a cell. Empty is the zero value, so a
22// freshly allocated Board is a legal empty board with no constructor call.
23type Disc byte
24
25const (
26 Empty Disc = 0
27 Red Disc = 1
28 Yellow Disc = 2
29)
30
31// Other returns the opponent of d, and Empty for Empty.
32func (d Disc) Other() Disc {
33 switch d {
34 case Red:
35 return Yellow
36 case Yellow:
37 return Red
38 }
39 return Empty
40}
41
42func (d Disc) String() string {
43 switch d {
44 case Red:
45 return "red"
46 case Yellow:
47 return "yellow"
48 }
49 return "empty"
50}
51
52var (
53 ErrColumnRange = errors.New("gno4: column out of range")
54 ErrColumnFull = errors.New("gno4: column is full")
55 ErrGameOver = errors.New("gno4: game is over")
56 ErrBadEncoding = errors.New("gno4: not a valid game encoding")
57)
58
59// Board is a position plus the moves that produced it.
60//
61// The winner and the winning line are computed once, by the Drop that creates
62// them, and stored. A realm renders a finished game far more often than it
63// plays a move, and rescanning 69 lines on every Render is gas spent to learn
64// something the board already knew.
65type Board struct {
66 cells [Cols * Rows]Disc
67 moves []int
68 winner Disc
69 line []int
70}
71
72// New returns an empty board. Red moves first.
73func New() *Board { return &Board{} }
74
75func idx(col, row int) int { return row*Cols + col }
76
77// At returns the disc at (col, row), counting rows from the bottom. Out of
78// range is Empty rather than a panic: At is called from render loops that walk
79// past the edge on purpose, and a Render that panics is a permanently
80// unreadable page.
81func (b *Board) At(col, row int) Disc {
82 if col < 0 || col >= Cols || row < 0 || row >= Rows {
83 return Empty
84 }
85 return b.cells[idx(col, row)]
86}
87
88// Turn returns whose move it is. Red on even move counts, Yellow on odd.
89func (b *Board) Turn() Disc {
90 if len(b.moves)%2 == 0 {
91 return Red
92 }
93 return Yellow
94}
95
96// MoveCount returns how many discs are on the board.
97func (b *Board) MoveCount() int { return len(b.moves) }
98
99// Moves returns a copy of the move list, as zero-based column indexes.
100func (b *Board) Moves() []int {
101 out := make([]int, len(b.moves))
102 copy(out, b.moves)
103 return out
104}
105
106// Height returns how many discs are stacked in col.
107func (b *Board) Height(col int) int {
108 if col < 0 || col >= Cols {
109 return 0
110 }
111 n := 0
112 for row := 0; row < Rows; row++ {
113 if b.cells[idx(col, row)] == Empty {
114 break
115 }
116 n++
117 }
118 return n
119}
120
121// Winner returns the disc that made four in a row, or Empty.
122func (b *Board) Winner() Disc { return b.winner }
123
124// Line returns the four cell indexes that won, or nil. An index is
125// row*Cols+col, the same order [Board.At] uses.
126func (b *Board) Line() []int {
127 out := make([]int, len(b.line))
128 copy(out, b.line)
129 return out
130}
131
132// Full reports whether all 42 cells are taken.
133func (b *Board) Full() bool { return len(b.moves) == Cols*Rows }
134
135// Over reports whether the game is decided: someone won, or the board filled.
136func (b *Board) Over() bool { return b.winner != Empty || b.Full() }
137
138// Draw reports whether the board filled with no winner.
139func (b *Board) Draw() bool { return b.winner == Empty && b.Full() }
140
141// CanDrop reports whether the current player may play col right now.
142func (b *Board) CanDrop(col int) bool {
143 return !b.Over() && col >= 0 && col < Cols && b.Height(col) < Rows
144}
145
146// Legal returns every column the current player may play. Empty once the game
147// is over, which is what makes it safe to render as the move menu.
148func (b *Board) Legal() []int {
149 out := []int{}
150 if b.Over() {
151 return out
152 }
153 for col := 0; col < Cols; col++ {
154 if b.Height(col) < Rows {
155 out = append(out, col)
156 }
157 }
158 return out
159}
160
161// Drop plays the current player's disc into col and returns the row it landed
162// on. It is the only method that mutates a Board, so every illegal state this
163// package could reach is refused in one place.
164func (b *Board) Drop(col int) (int, error) {
165 if b.Over() {
166 return 0, ErrGameOver
167 }
168 if col < 0 || col >= Cols {
169 return 0, ErrColumnRange
170 }
171 row := b.Height(col)
172 if row >= Rows {
173 return 0, ErrColumnFull
174 }
175 d := b.Turn()
176 b.cells[idx(col, row)] = d
177 b.moves = append(b.moves, col)
178 if line := b.scan(col, row, d); line != nil {
179 b.winner = d
180 b.line = line
181 }
182 return row, nil
183}
184
185// Clone returns an independent copy. Callers that search (a hint, a bot) mutate
186// a clone; a Board handed out by a realm is never a scratch pad.
187func (b *Board) Clone() *Board {
188 c := &Board{cells: b.cells, winner: b.winner}
189 c.moves = make([]int, len(b.moves))
190 copy(c.moves, b.moves)
191 c.line = make([]int, len(b.line))
192 copy(c.line, b.line)
193 return c
194}
195
196// WinningMove returns a column where d wins on the spot, or -1.
197//
198// It is deliberately one ply deep. That covers the two things a player wants
199// from a board they are looking at ("can I win now", "can they win now, so I
200// must block") and costs seven clones; a real search belongs off-chain, in the
201// front-end, where nobody pays gas to think.
202func (b *Board) WinningMove(d Disc) int {
203 if b.Over() {
204 return -1
205 }
206 for col := 0; col < Cols; col++ {
207 row := b.Height(col)
208 if row >= Rows {
209 continue
210 }
211 if b.scan(col, row, d) != nil {
212 return col
213 }
214 }
215 return -1
216}
217
218// dirs are the four axes a line can run along: east, north, north-east,
219// north-west. Their opposites are covered by scanning both ways from the
220// placed disc.
221var dirs = [4][2]int{{1, 0}, {0, 1}, {1, 1}, {1, -1}}
222
223// scan looks for a line of four through (col, row) for d.
224//
225// It never reads (col, row) itself, only the cells around it, so the same scan
226// answers both questions this package asks: "did the disc I just placed win"
227// and "would a disc placed here win". That is why [Board.WinningMove] needs no
228// clone and writes nothing.
229func (b *Board) scan(col, row int, d Disc) []int {
230 for _, dir := range dirs {
231 cells := []int{idx(col, row)}
232 for _, sign := range [2]int{1, -1} {
233 for step := 1; step < 4; step++ {
234 c := col + dir[0]*sign*step
235 r := row + dir[1]*sign*step
236 if c < 0 || c >= Cols || r < 0 || r >= Rows {
237 break
238 }
239 if b.cells[idx(c, r)] != d {
240 break
241 }
242 cells = append(cells, idx(c, r))
243 }
244 }
245 if len(cells) >= 4 {
246 return trimLine(cells, dir, col, row)
247 }
248 }
249 return nil
250}
251
252// trimLine reduces a run of five or six to the four cells adjacent to the disc
253// that was just played, walking outward from it so the highlighted line always
254// contains the winning move.
255func trimLine(cells []int, dir [2]int, col, row int) []int {
256 out := []int{idx(col, row)}
257 for _, sign := range [2]int{1, -1} {
258 for step := 1; step < 4 && len(out) < 4; step++ {
259 c := col + dir[0]*sign*step
260 r := row + dir[1]*sign*step
261 if !contains(cells, idx(c, r)) {
262 break
263 }
264 out = append(out, idx(c, r))
265 }
266 }
267 sortInts(out)
268 return out
269}
270
271func contains(haystack []int, needle int) bool {
272 for _, v := range haystack {
273 if v == needle {
274 return true
275 }
276 }
277 return false
278}
279
280// sortInts is an insertion sort. gno has no sort.Slice, and the input is four
281// elements, so reaching for anything larger would be theatre.
282func sortInts(a []int) {
283 for i := 1; i < len(a); i++ {
284 v := a[i]
285 j := i - 1
286 for j >= 0 && a[j] > v {
287 a[j+1] = a[j]
288 j--
289 }
290 a[j+1] = v
291 }
292}
