nimlib/moves.rs
1//! Code for handling moves.
2//! This module contains code for handling moves in Nim games,
3//! such as calculating the resulting position after a move is applied,
4//! determining if a move is valid, and generating all possible moves
5//! for a given position.
6
7use std::{error::Error, fmt::Display};
8
9use serde::{Deserialize, Serialize};
10
11use crate::{
12 nimbers::calculate_splits, NimAction, NimGame, NimRule, NimSplit, PlaceAction, Split, Stack,
13 TakeAction, TakeSize,
14};
15
16/// Errors which may occur when applying a move
17#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
18pub enum MoveError {
19 // TODO remove `InvalidMove` and replace it with more specific errors
20 /// The move is invalid for the given position
21 ///
22 /// This error is very generic and is subject to be replaced with more specific errors
23 InvalidMove,
24
25 /// The stack index is out of bounds
26 NoSuchStack,
27
28 /// The stack does not have enough coins to take (before a possible split)
29 NotEnoughCoins,
30
31 /// No rule exists which supports the desired move
32 NoSuchRule,
33
34 /// The split is invalid for the given move under ever rule in the specified game
35 InvalidSplit,
36}
37
38impl Display for MoveError {
39 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
40 match self {
41 MoveError::InvalidMove => write!(f, "The move is invalid for the given position"),
42 MoveError::NoSuchStack => write!(f, "The stack index is out of bounds"),
43 MoveError::NotEnoughCoins => write!(f, "The stack does not have enough coins to take"),
44 MoveError::NoSuchRule => write!(f, "No rule exists which supports the desired move"),
45 MoveError::InvalidSplit => write!(f, "The split is invalid for the given move"),
46 }
47 }
48}
49
50impl Error for MoveError {}
51
52/// Determine if a move is valid for a given position
53///
54/// Returns `Ok(())` if the move is valid, or an error if the move is invalid
55/// (see [`MoveError`] for possible errors).
56pub fn check_move(game: &NimGame, mov: &NimAction) -> Result<(), MoveError> {
57 match mov {
58 NimAction::Take(TakeAction {
59 stack_index,
60 amount,
61 split,
62 }) => {
63 // Get the stack to take coins from
64 let stack = game
65 .stacks
66 .get(*stack_index)
67 .ok_or(MoveError::NoSuchStack)?;
68
69 // Check if a rule can support the desired move (taking)
70 let mut supporting_rules = Vec::new();
71
72 for rule in &game.rules {
73 let supports = match &rule.take {
74 TakeSize::List(list) => list.contains(amount),
75 TakeSize::Any => true,
76 TakeSize::Place => false,
77 };
78
79 if supports {
80 supporting_rules.push(rule);
81 break;
82 }
83 }
84
85 if supporting_rules.is_empty() {
86 return Err(MoveError::NoSuchRule);
87 }
88
89 // Check if the stack has enough coins to take
90 if stack.0 < *amount {
91 return Err(MoveError::NotEnoughCoins);
92 }
93
94 // Check if the move is valid for at least one rule (splitting)
95 let mut valid = false;
96 for rule in supporting_rules {
97 match rule.split {
98 Split::Never => {
99 // TODO consider replacing this with a regular if statement
100 if let NimSplit::No = split {
101 valid = true;
102 break;
103 }
104 }
105 Split::Optional => {
106 // TODO consider replacing this with a regular if statement
107 if let NimSplit::Yes(a, b) = split {
108 // FIXME replace `true` with a check if the rule allowing for the split allows taking the `amount` of coins
109 if ((a.0 + b.0 + amount) <= stack.0) && a.0 != 0 && b.0 != 0 && (true) {
110 valid = true;
111 break;
112 }
113 } else {
114 // Splitting is optional and no split was specified, so the move is valid
115 valid = true;
116 break;
117 }
118 }
119 Split::Always => {
120 // TODO consider replacing this with a regular if statement
121 if let NimSplit::Yes(a, b) = split {
122 // FIXME replace `true` with a check if the rule allowing for the split allows taking the `amount` of coins
123 if ((a.0 + b.0 + amount) <= stack.0) && a.0 != 0 && b.0 != 0 && (true) {
124 valid = true;
125 break;
126 }
127 }
128 // No `else` clause as the move is invalid if no split was specified
129 }
130 }
131 }
132
133 if !valid {
134 return Err(MoveError::InvalidSplit);
135 }
136 }
137 NimAction::Place(PlaceAction {
138 stack_index,
139 amount: _,
140 }) => {
141 // Get the stack to place coins onto
142 let _stack = game
143 .stacks
144 .get(*stack_index)
145 .ok_or(MoveError::NoSuchStack)?;
146
147 return Err(MoveError::InvalidMove);
148 }
149 }
150
151 Ok(())
152}
153
154/// The implementation of [`apply_move`] and [`apply_move_unchecked`]
155fn apply_move_(game: &mut NimGame, mov: &NimAction, unchecked: bool) -> Result<(), MoveError> {
156 // Assure that the move is valid
157 if !unchecked {
158 check_move(game, mov)?;
159 }
160
161 match mov {
162 NimAction::Take(TakeAction {
163 stack_index,
164 amount,
165 split,
166 }) => {
167 // Get the stack to take coins from
168 let stack = game
169 .stacks
170 .get_mut(*stack_index)
171 .ok_or(MoveError::NoSuchStack)?;
172
173 // Take coins from the stack
174 stack.0 -= amount;
175
176 // Split the coins if necessary
177 if let NimSplit::Yes(a, b) = split {
178 // Insert stacks `a` and `b` into `stacks` at position `stack_index`
179 // And remove the original stack at `stack_index`
180 game.stacks
181 .splice(*stack_index..=*stack_index, [*a, *b].into_iter());
182 }
183 }
184 NimAction::Place(PlaceAction {
185 stack_index,
186 amount,
187 }) => {
188 // Get the stack to place coins onto
189 let stack = game
190 .stacks
191 .get_mut(*stack_index)
192 .ok_or(MoveError::NoSuchStack)?;
193
194 // Place coins onto the stack
195 stack.0 += amount;
196 }
197 }
198
199 Ok(())
200}
201
202/// Applies a move to a position, if the move is valid
203///
204/// The validity of the move is checked with [`check_move`] before applying it.
205///
206/// # Arguments
207///
208/// - `game` - The game state before the move is applied
209/// - `mov` - The move to apply
210///
211/// # Returns
212///
213/// [`Ok`] with the unit type if the move is valid and was applied successfully,
214/// an [`Err`] with the reason why the move is invalid otherwise (see [`MoveError`])
215pub fn apply_move(game: &mut NimGame, mov: &NimAction) -> Result<(), MoveError> {
216 apply_move_(game, mov, false)
217}
218
219/// Applies a move to a position, even if the move is invalid
220///
221/// # Arguments
222///
223/// - `game` - The game state before the move is applied
224/// - `mov` - The move to apply
225///
226/// # Returns
227///
228/// [`Ok`] with the unit type if the move is valid and was applied successfully,
229/// an [`Err`] otherwise, usually [`MoveError::NoSuchStack`] (see [`MoveError`])
230///
231/// # Safety
232///
233/// While this function does not perform _traditionally_ unsafe operations,
234/// applying moves without checking them for validity can lead to unexpected
235/// behaviour. This function is therefore marked as unsafe;
236/// but this is possibly subject to change.
237///
238/// Please note that the bounds checks of the [`Vec`] indices are not disabled by this function.
239pub unsafe fn apply_move_unchecked(game: &mut NimGame, mov: &NimAction) -> Result<(), MoveError> {
240 apply_move_(game, mov, true)
241}
242
243/// Generate all possible (legal) moves for a given position
244///
245/// # Arguments
246///
247/// - `stacks` - The stacks of coins in the position
248/// - `rules` - The rules of the game (see [`NimRule`])
249/// - `pool_coins` is currently not fully implemented.
250///
251/// # Returns
252///
253/// A [`Vec`] of all possible (legal) moves for the given position
254/// in the form of [`NimAction`]s.
255///
256/// The returned value does not reference the given `stacks` or `rules`,
257/// only the stack indices and the amount of coins to take are referenced,
258/// along with the split of coins if necessary.
259///
260/// # Example
261///
262/// ```
263/// use nimlib::{moves, NimAction, NimRule, NimSplit, Split, Stack, TakeSize};
264///
265/// let rules = vec![NimRule {
266/// take: TakeSize::List(vec![1, 2, 3]),
267/// split: Split::Never,
268/// }];
269///
270/// let stacks = vec![Stack(10)];
271///
272/// let moves = moves::calculate_legal_moves(&stacks, &rules, (0, 0))
273/// .into_iter()
274/// .map(|mov| {
275/// if let NimAction::Take(take) = mov {
276/// take
277/// } else {
278/// panic!("Expected a take action");
279/// }
280/// })
281/// .collect::<Vec<_>>();
282///
283/// assert_eq!(moves.len(), 3);
284///
285/// assert_eq!(moves[0].amount, 1);
286/// assert_eq!(moves[0].stack_index, 0);
287/// assert_eq!(moves[0].split, NimSplit::No);
288///
289/// assert_eq!(moves[1].amount, 2);
290/// assert_eq!(moves[1].stack_index, 0);
291/// assert_eq!(moves[1].split, NimSplit::No);
292///
293/// assert_eq!(moves[2].amount, 3);
294/// assert_eq!(moves[2].stack_index, 0);
295/// assert_eq!(moves[2].split, NimSplit::No);
296/// ```
297pub fn calculate_legal_moves(
298 stacks: &[Stack],
299 rules: &[NimRule],
300 (pool_coins_a, _pool_coins_b): (u64, u64),
301) -> Vec<NimAction> {
302 let mut moves = Vec::new();
303
304 // Iterate over all stacks
305 for (s_idx, stack) in stacks.iter().enumerate() {
306 // Iterate over all rules
307 for NimRule { take, split } in rules {
308 match take {
309 TakeSize::List(take_sizes) => {
310 for take_size in take_sizes {
311 if stack.0 >= *take_size {
312 match split {
313 Split::Never => {
314 // Without split
315 moves.push(NimAction::Take(TakeAction {
316 stack_index: s_idx,
317 amount: *take_size,
318 split: NimSplit::No,
319 }));
320 }
321 Split::Optional => {
322 // Without split
323 moves.push(NimAction::Take(TakeAction {
324 stack_index: s_idx,
325 amount: *take_size,
326 split: NimSplit::No,
327 }));
328
329 // With split
330 // Enumerate all possible splits
331 for (a, b) in
332 calculate_splits(stack.0.saturating_sub(*take_size))
333 {
334 moves.push(NimAction::Take(TakeAction {
335 stack_index: s_idx,
336 amount: *take_size,
337 split: NimSplit::Yes(a, b),
338 }));
339 }
340 }
341 Split::Always => {
342 // With split
343 // Enumerate all possible splits
344 for (a, b) in
345 calculate_splits(stack.0.saturating_sub(*take_size))
346 {
347 moves.push(NimAction::Take(TakeAction {
348 stack_index: s_idx,
349 amount: *take_size,
350 split: NimSplit::Yes(a, b),
351 }));
352 }
353 }
354 }
355 }
356 }
357 }
358
359 TakeSize::Any => {
360 for h in 1..=stack.0 {
361 match split {
362 Split::Never => {
363 // Without split
364 moves.push(NimAction::Take(TakeAction {
365 stack_index: s_idx,
366 amount: h,
367 split: NimSplit::No,
368 }));
369 }
370 Split::Optional => {
371 // Without split
372 moves.push(NimAction::Take(TakeAction {
373 stack_index: s_idx,
374 amount: h,
375 split: NimSplit::No,
376 }));
377
378 // With split
379 // Enumerate all possible splits
380 for (a, b) in calculate_splits(stack.0.saturating_sub(h)) {
381 moves.push(NimAction::Take(TakeAction {
382 stack_index: s_idx,
383 amount: h,
384 split: NimSplit::Yes(a, b),
385 }));
386 }
387 }
388 Split::Always => {
389 // With split
390 // Enumerate all possible splits
391 for (a, b) in calculate_splits(stack.0.saturating_sub(h)) {
392 moves.push(NimAction::Take(TakeAction {
393 stack_index: s_idx,
394 amount: h,
395 split: NimSplit::Yes(a, b),
396 }));
397 }
398 }
399 }
400 }
401 }
402
403 TakeSize::Place => {
404 // The player can add 1..pool_coins coins to the stack
405 // The placed coins are taken from the pool
406 // FIXME only the coins of player A can be placed; this must not be hardcoded
407 for c in 1..=pool_coins_a {
408 match split {
409 Split::Never => {
410 // Without split
411 moves.push(NimAction::Place(PlaceAction {
412 stack_index: s_idx,
413 amount: c,
414 }));
415 }
416 Split::Optional | Split::Always => {
417 // TODO consider replacing this panic with a Result or improve the types themselves
418 panic!("Split is not allowed with Place")
419 }
420 }
421 }
422 }
423 }
424 }
425 }
426
427 moves
428}