tools_2048/
core.rs

1//! A module that contains the logic for the 2048 game.
2
3// std imports
4use std::fmt::{self, Display, Formatter, Write};
5use std::sync::{Arc, Mutex};
6
7// external imports
8use rand::seq::IteratorRandom;
9use rand::{random, thread_rng};
10use tinypool::ThreadPool;
11
12// internal imports
13use crate::error::Error;
14
15/// An enum that represents the moves that can be made in the game of 2048.
16#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
17pub enum GameMove {
18    Left,
19    Right,
20    Up,
21    Down,
22}
23impl GameMove {
24    /// Returns the index of the move.
25    /// Used internally for indexing arrays.
26    /// # Returns
27    /// * ```usize``` - The index of the move.
28    fn index(&self) -> usize {
29        match self {
30            Self::Left => 0,
31            Self::Right => 1,
32            Self::Up => 2,
33            Self::Down => 3,
34        }
35    }
36
37    /// Returns the move from the index.
38    /// Used internally for indexing arrays.
39    /// # Arguments
40    /// * ```index``` - The index of the move.
41    /// # Returns
42    /// * ```GameMove``` - The move.
43    fn from_index(index: usize) -> Self {
44        match index {
45            0 => Self::Left,
46            1 => Self::Right,
47            2 => Self::Up,
48            3 => Self::Down,
49            _ => panic!("Invalid index: {}", index),
50        }
51    }
52}
53
54/// An enum that represents the possible states of the 2048 game.
55#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
56pub enum GameState {
57    /// The game is in progress.
58    InProgress,
59    /// The game is over. Result is either victory or loss.
60    GameOver,
61}
62
63/// An enum that represents the possible results of the 2048 game.
64#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
65pub enum GameResult {
66    /// The result is not yet determined.
67    Pending,
68    /// The game is won, 2048 was reached.
69    Victory,
70    /// The game is over, 2048 was not reached, there are no valid moves left.
71    Loss,
72}
73
74#[derive(Debug)]
75/// A struct that represents the 2048 game.
76pub struct Game<const SIZE: usize> {
77    /// Game tiles.
78    board: [[u64; SIZE]; SIZE],
79    /// Game score.
80    score: u64,
81    /// Additional score for each move.
82    score_next: [u64; 4],
83    /// Availability of moves.
84    moves: [bool; 4],
85    /// Board after each of the moves.
86    moves_next: [[[u64; SIZE]; SIZE]; 4],
87    /// The state of the game.
88    state: GameState,
89    /// The result of the game.
90    result: GameResult,
91}
92impl<const SIZE: usize> Game<SIZE> {
93    /// Creates a new game of 2048.
94    /// # Returns
95    /// * ```Ok(Game)```: The game was created successfully.
96    /// * ```Err(Error)```: The game was not created successfully.
97    /// # Errors
98    /// * ```Error::InvalidSize```: The SIZE is invalid. Must be at least 4.
99    pub fn new() -> Result<Self, Error> {
100        if SIZE < 4 {
101            return Err(Error::InvalidSize);
102        }
103
104        let board = [[0; SIZE]; SIZE];
105        let score = 0;
106        let score_next = [0; 4];
107        let moves = [true; 4];
108        let moves_next = [[[0; SIZE]; SIZE]; 4];
109        let state = GameState::InProgress;
110        let result = GameResult::Pending;
111
112        let mut game_object: Self = Self {
113            board,
114            score,
115            score_next,
116            moves,
117            moves_next,
118            state,
119            result,
120        };
121
122        game_object.new_tile();
123        game_object.update();
124
125        Ok(game_object)
126    }
127
128    /// Creates a game of 2048 from an existing board.
129    /// The board must be a square matrix filled with 0 for empty tiles and powers of 2 for filled tiles.
130    /// # Arguments
131    /// * ```board```: The board to use.
132    /// * ```score```: The score of the game.
133    /// # Returns
134    /// * ```Ok(Game)```: The game was created successfully.
135    /// * ```Err(Error)```: The game was not created successfully.
136    /// # Errors
137    /// * ```Error::InvalidSize```: The SIZE is invalid. Must be at least 4.
138    /// * ```Error::InvalidValue```: The board contains invalid value. Must be 0 or a power of 2, starting from 2.
139    pub fn from_existing(board: &[[u64; SIZE]; SIZE], score: u64) -> Result<Self, Error> {
140        if SIZE < 4 {
141            return Err(Error::InvalidSize);
142        }
143
144        for row in board.iter() {
145            for tile in row.iter() {
146                if *tile == 1 || (*tile != 0 && !tile.is_power_of_two()) {
147                    return Err(Error::InvalidValue);
148                }
149            }
150        }
151
152        let board = *board;
153        let score_next = [0; 4];
154        let moves = [true; 4];
155        let moves_next = [[[0; SIZE]; SIZE]; 4];
156        let state = GameState::InProgress;
157        let result = GameResult::Pending;
158
159        let mut game_object = Self {
160            board,
161            score,
162            score_next,
163            moves,
164            moves_next,
165            state,
166            result,
167        };
168        game_object.update();
169
170        Ok(game_object)
171    }
172
173    /// Returns the reference to the board.
174    /// The board is a square matrix filled with 0 for empty tiles and powers of 2 for filled tiles.
175    /// # Returns
176    /// * ```&[[u64; SIZE]; SIZE]```: The board.
177    pub fn board(&self) -> &[[u64; SIZE]; SIZE] {
178        &self.board
179    }
180
181    /// Returns the result of the game.
182    /// # Returns
183    /// * ```Result::Victory```: The game is won, 2048 was reached.
184    /// * ```Result::Pending```: The game is in progress, 2048 is not reached yet.
185    /// * ```Result::Loss```: The game is over, 2048 was not reached.
186    pub fn result(&self) -> GameResult {
187        self.result
188    }
189
190    /// Returns the score of the game.
191    /// # Returns
192    /// * ```u64```: The score of the game.
193    pub fn score(&self) -> u64 {
194        self.score
195    }
196
197    /// Returns the size of the board.
198    /// # Returns
199    /// * ```usize```: The size of the board. The board is ```usize```x```usize```.
200    pub fn size(&self) -> usize {
201        SIZE
202    }
203
204    /// Returns the state of the game.
205    /// # Returns
206    /// * ```State::InProgress```: The game is in progress.
207    /// * ```State::GameOver```: The game is over.
208    pub fn state(&self) -> GameState {
209        self.state
210    }
211
212    /// Make a move in the game.
213    /// # Arguments
214    /// * ```direction```: The direction to move in.
215    /// # Returns
216    /// * ```true``` - The move was successful.
217    /// * ```false``` - The move was invalid/impossible.
218    pub fn make_move(&mut self, direction: GameMove) -> bool {
219        let next_ind = direction.index();
220        if self.moves[next_ind] {
221            self.board = self.moves_next[next_ind];
222            self.score += self.score_next[next_ind];
223            self.new_tile();
224            self.update();
225            true
226        } else {
227            false
228        }
229    }
230
231    /// Add a new tile to the board.
232    fn new_tile(&mut self) {
233        // create iterator over all tiles (cartesian product of two ranges)
234        // filter only empty tiles -> get iterator over empty tiles
235        // choose one of the empty tiles with rng
236        let loc = (0..SIZE)
237            .flat_map(|ind1| (0..SIZE).map(move |ind2| (ind1, ind2)))
238            .filter(|&pos| self.board[pos.0][pos.1] == 0)
239            .choose(&mut thread_rng())
240            .unwrap();
241
242        // add 2 or 4 to that tile
243        self.board[loc.0][loc.1] = if random::<f64>() < 0.9 { 2 } else { 4 };
244    }
245
246    /// Update moves, moves_next, score_next, state and result.
247    fn update(&mut self) {
248        // update left
249        self.score_next[0] = 0;
250        for (i, row) in self.board.iter().enumerate() {
251            let mut j = 0;
252            let mut merge = false;
253            for elem in row.iter().filter(|&&x| x != 0) {
254                if merge && *elem == self.moves_next[0][i][j - 1] {
255                    self.moves_next[0][i][j - 1] *= 2;
256                    self.score_next[0] += self.moves_next[0][i][j - 1];
257                    merge = false;
258                } else {
259                    self.moves_next[0][i][j] = *elem;
260                    j += 1;
261                    merge = true;
262                }
263            }
264            for empty_elem in self.moves_next[0][i].iter_mut().skip(j) {
265                *empty_elem = 0;
266            }
267        }
268        self.moves[0] = self.board != self.moves_next[0];
269
270        // update right
271        self.score_next[1] = 0;
272        for (i, row) in self.board.iter().enumerate() {
273            let mut j = SIZE - 1;
274            let mut merge = false;
275            let mut negative_index = false;
276            for elem in row.iter().filter(|&&x| x != 0).rev() {
277                if merge && *elem == self.moves_next[1][i][j + 1] {
278                    self.moves_next[1][i][j + 1] *= 2;
279                    self.score_next[1] += self.moves_next[1][i][j + 1];
280                    merge = false;
281                } else {
282                    self.moves_next[1][i][j] = *elem;
283                    j = match j.checked_sub(1) {
284                        Some(x) => x,
285                        None => {
286                            // we processed the whole row, we can safely break
287                            negative_index = true;
288                            break;
289                        }
290                    };
291                    merge = true;
292                }
293            }
294            if !negative_index {
295                for empty_elem in self.moves_next[1][i].iter_mut().rev().skip(SIZE - 1 - j) {
296                    *empty_elem = 0;
297                }
298            }
299        }
300        self.moves[1] = self.board != self.moves_next[1];
301
302        // update up
303        self.score_next[2] = 0;
304        for col in 0..SIZE {
305            let mut i = 0;
306            let mut merge = false;
307            for elem in self.board.iter().map(|row| row[col]).filter(|&x| x != 0) {
308                if merge && elem == self.moves_next[2][i - 1][col] {
309                    self.moves_next[2][i - 1][col] *= 2;
310                    self.score_next[2] += self.moves_next[2][i - 1][col];
311                    merge = false;
312                } else {
313                    self.moves_next[2][i][col] = elem;
314                    i += 1;
315                    merge = true;
316                }
317            }
318            for empty_elem in self.moves_next[2].iter_mut().skip(i).map(|row| &mut row[col]) {
319                *empty_elem = 0;
320            }
321        }
322        self.moves[2] = self.board != self.moves_next[2];
323
324        // update down
325        self.score_next[3] = 0;
326        for col in 0..SIZE {
327            let mut i = SIZE - 1;
328            let mut merge = false;
329            let mut negative_index = false;
330            for elem in self.board.iter().map(|row| row[col]).filter(|&x| x != 0).rev() {
331                if merge && elem == self.moves_next[3][i + 1][col] {
332                    self.moves_next[3][i + 1][col] *= 2;
333                    self.score_next[3] += self.moves_next[3][i + 1][col];
334                    merge = false;
335                } else {
336                    self.moves_next[3][i][col] = elem;
337                    i = match i.checked_sub(1) {
338                        Some(x) => x,
339                        None => {
340                            // we processed whole column, we can safely break
341                            negative_index = true;
342                            break;
343                        }
344                    };
345                    merge = true;
346                }
347            }
348            if !negative_index {
349                for empty_elem in self.moves_next[3].iter_mut().rev().skip(SIZE - 1 - i).map(|row| &mut row[col]) {
350                    *empty_elem = 0;
351                }
352            }
353        }
354        self.moves[3] = self.board != self.moves_next[3];
355
356        // update state
357        if self.moves.iter().all(|&x| !x) {
358            self.state = GameState::GameOver;
359        }
360
361        // update result
362        match self.result {
363            GameResult::Pending => {
364                let victory = self.board.iter().flat_map(|row| row.iter()).any(|&x| x >= 2048);
365                if victory {
366                    self.result = GameResult::Victory;
367                } else if self.state == GameState::GameOver {
368                    self.result = GameResult::Loss;
369                }
370            }
371            GameResult::Victory => {}
372            GameResult::Loss => {}
373        }
374    }
375
376    /// Find the best move to make based on the current board state.
377    /// Based on Monte Carlo algorithm (randomized guessing).
378    /// Uses multiple threads to speed up the process.
379    /// # Arguments
380    /// * ```depth``` - The number of simulated games to play to determine the best move. Recommended value is 1000.
381    /// # Returns
382    /// * ```Ok(GameMove)``` - The best move to make.
383    /// * ```Err(Error)``` - There are no valid moves left.
384    /// # Errors
385    /// * ```Error::NoValidMove``` - There are no valid moves left.
386    pub fn find_best_move(&self, depth: usize) -> Result<GameMove, Error> {
387        let possible_moves_count = self.moves.iter().filter(|&&x| x).count();
388
389        match possible_moves_count {
390            0 => Err(Error::NoValidMove),
391            1 => Ok(GameMove::from_index(self.moves.iter().position(|&val| val).unwrap())),
392            2.. => {
393                let mut thread_pool = ThreadPool::new(None).unwrap();
394
395                let mut depth_per_thread = depth / (possible_moves_count * thread_pool.size());
396                if depth_per_thread == 0 {
397                    depth_per_thread = 1;
398                } else if depth_per_thread * possible_moves_count * thread_pool.size() != depth {
399                    depth_per_thread += 1;
400                }
401
402                let moves_values = Arc::new(Mutex::new([0; 4]));
403
404                for move_ind in self.moves.iter().enumerate().filter_map(|(ind, &x)| if x { Some(ind) } else { None }) {
405                    let move_type = GameMove::from_index(move_ind);
406
407                    for _ in 0..thread_pool.size() {
408                        let board_copy = self.board;
409                        let moves_values = Arc::clone(&moves_values);
410                        thread_pool.add_to_queue(move || {
411                            let mut thread_score = 0;
412
413                            for _ in 0..depth_per_thread {
414                                let mut work_game = Self::from_existing(&board_copy, 0).unwrap();
415
416                                work_game.make_move(move_type);
417                                while let GameState::InProgress = work_game.state {
418                                    if work_game.make_move(
419                                        work_game
420                                            .moves
421                                            .iter()
422                                            .enumerate()
423                                            .filter_map(|(i, &b)| if b { Some(GameMove::from_index(i)) } else { None })
424                                            .choose(&mut thread_rng())
425                                            .unwrap(),
426                                    ) && work_game.state == GameState::GameOver
427                                    {
428                                        break;
429                                    }
430                                }
431
432                                thread_score += work_game.score;
433                            }
434
435                            moves_values.lock().unwrap()[move_ind] += thread_score;
436                        });
437                    }
438                }
439                thread_pool.join();
440
441                let max_ind = moves_values.lock().unwrap().iter().enumerate().max_by_key(|(_, &x)| x).unwrap().0;
442
443                Ok(GameMove::from_index(max_ind))
444            }
445        }
446    }
447}
448impl<const SIZE: usize> Display for Game<SIZE> {
449    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
450        // find the maximum value in the board
451        let mut max_val = 0;
452        for row in &self.board {
453            for val in row {
454                if *val > max_val {
455                    max_val = *val;
456                }
457            }
458        }
459
460        // find the number of digits in the maximum value
461        let mut max_len = 0;
462        if max_val == 0 {
463            max_len = 1;
464        }
465        while max_val != 0 {
466            max_len += 1;
467            max_val /= 10;
468        }
469        max_len += 1; // add one space
470
471        // create the output string
472        let mut output = String::from("Board:\n");
473        for row in &self.board {
474            for val in row {
475                write!(&mut output, "{:width$}", val, width = max_len).unwrap();
476            }
477            output.push('\n');
478        }
479        writeln!(&mut output, "Score: {}", self.score).unwrap();
480
481        write!(f, "{}", output)
482    }
483}
484
485#[cfg(test)]
486mod tests {
487    use super::*;
488
489    #[test]
490    fn create_game_4() {
491        //! Test the creation of a new game with the default size (4x4)
492
493        let game: Game<4> = Game::new().unwrap();
494        let game_from = Game::from_existing(game.board(), 0).unwrap();
495
496        assert_eq!(game.size(), 4);
497        assert_eq!(game_from.size(), 4);
498
499        assert_eq!(game.score(), 0);
500        assert_eq!(game_from.score(), 0);
501
502        assert_eq!(game.state(), GameState::InProgress);
503        assert_eq!(game_from.state(), GameState::InProgress);
504
505        assert_eq!(game.result(), GameResult::Pending);
506        assert_eq!(game_from.result(), GameResult::Pending);
507    }
508
509    #[test]
510    fn create_game_5() {
511        //! Test the creation of a new game with a bigger size (5x5)
512
513        let game: Game<5> = Game::new().unwrap();
514        let game_from = Game::from_existing(game.board(), 0).unwrap();
515
516        assert_eq!(game.size(), 5);
517        assert_eq!(game_from.size(), 5);
518
519        assert_eq!(game.score(), 0);
520        assert_eq!(game_from.score(), 0);
521
522        assert_eq!(game.state(), GameState::InProgress);
523        assert_eq!(game_from.state(), GameState::InProgress);
524
525        assert_eq!(game.result(), GameResult::Pending);
526        assert_eq!(game_from.result(), GameResult::Pending);
527    }
528
529    #[test]
530    fn game_4_ai() {
531        //! Test the AI's ability to play a game with the default size (4x4)
532
533        let mut game: Game<4> = Game::new().unwrap();
534        while let Ok(best_move) = game.find_best_move(1_000) {
535            game.make_move(best_move);
536        }
537
538        assert_eq!(game.state(), GameState::GameOver);
539        assert_ne!(game.score(), 0);
540    }
541
542    #[test]
543    fn game_5_ai() {
544        //! Test the AI's ability to play a big game
545
546        let mut game: Game<5> = Game::new().unwrap();
547        while let Ok(best_move) = game.find_best_move(1_000) {
548            game.make_move(best_move);
549        }
550
551        assert_eq!(game.state(), GameState::GameOver);
552        assert_ne!(game.score(), 0);
553    }
554}
tools_2048/core.rs

tools_2048/
core.rs
