<jupyter_start><jupyter_text><NAME>, 1 Dec 2021 Mel's Konane BoardMy friend and former NASA colleague [<NAME>](https://www.linkedin.com/in/mel-montemerlo-a2040b205/) made this beautiful Konane set for me:![Wooden Konane Board](konane.jpg)I don't have the woodworking skills to make anything nearly as nice as that, so instead I thought I'd use my coding skills to make a nice program to solve the game. It's the least I can do to return the favor to Mel.  Konane RulesKonane (or Kōnane) is a two-player board game from Hawaii.  To set up the game, fill each space with a marble, alternating between black and white marbles in a checkerboard pattern.  To complete the set-up, remove two adjacent marbles (one black, one white) from the board. From there on, the players take turns, with black moving first. A move consists of jumping a marble of your color over an adjacent opponent marble, removing that marble, and landing on the empty space beyond it.  If there is another opponent marble followed by another empty space in the same direction, the player may optionally make a double (or more) jump. Jumps may not be diagonal, and a multiple jump may not change directions.When one player is unable to jump, that player loses.(Some rules say the removed marbles must be either in a corner or in the very center; others say the two can be anywhere on the board. If you accept that they must be in a corner or the center, then there are only two distinct starting positions; the others ten are equivalent under rotation and reflection.) Approach to Solving  KonaneA game is said to be **solved** if, for any state of the game that occurs during play, you can instantly say whether the player to move can force a win from that state. The first thing to consider is whether a 6 by 6 board is small enough that we can solve the game by exhaustive search of the graph of possible states of the game. By **state** I mean an indication of everything that matters: whose turn it is to play, and what marbles are in what spaces. The player to move is either black or white, and each of the 36 spaces can either hold a marble or not, so an upper bound is  237 ≈ 137 billion game states. However, the rules for jumping constrain the possible states of the game; most of those theoretical states are unreachable from the start state.  As a wild guess, I estimate that maybe 100 million to a billion states are rechable. That's few enough that I should be able to solve the game with exhaustive search. I'm lucky that Mel chose 6 by 6; even a 7 by 7 board would be far too large for exhaustive search.I will define a function `winner(state)` that will return the player who can force a win from that state, regardless of what the other player does. (There must be one such player, because ties are not allowed and there is no randomness.) Once I have cached the values of `winner`,  the optimal strategy is easy: - Play a move that leads to a game state where you are the winner.- If there is no such move, then you're doomed (against an optimal player); play anything.  Implementation of Basic TypesThe number of states for the 6 by 6 board puts us right on the edge: small enough that I'm confident I can get the program to work; big enough to require some judicious implementation choices to save time and space. For example, a straightforward way to implement a game state would be a structure with two fields, player and board, where the board is a 6 by 6 array where each element is either black, white, or empty. But a billion of those structures would consume a lot of memory. A more efficient encoding is to represent the board as a bit string: a binary integer where bit *s* is a 1 if there is a marble in space *s*, according to the following numbering scheme:     0  1  2  3  4  5     6  7  8  9 10 11    12 13 14 15 16 17    18 19 20 21 22 23    24 25 26 27 28 29    30 31 32 33 34 35    The bit representation for a board doesn't have to say whether a marble is black or white; black marbles can only be in spaces numbered 0, 2, 4, 7, 9, 11, ... (spaces where the x coordinates plus y coordinate is even) and white only in spaces 1, 3, 5, 6, 8, 10, ... (spaces where the x coordinate plus y coordinate is odd).The representation of a state can also be a single `int`, with the low-order bit being 1 for black, 0 for white, and the other bits being a board shifted left a bit.    Given this, the implementation choices are as follows:- **N**: the size of the board: a global variable, defined as 6.- **Board**: a bit string (`int`) indicating which spaces hold marbles.  - The function `get(board space)` returns the player on that space, or `empty`.  - The function `remove(board, spaces)` returns a new board with the marbles on `spaces` removed.- **State**: a bit string (`int`) indicating both the board and the player whose turn it is.  - The function `start_state(removed)` returns a state with a full board except for `removed` spaces.  - The functions `encode_state` and `decode_state` join and split a board/player pair.- **Space**: an integer from 0 to 35 (or in general, 0 to N2 - 1).   - The function `space(x, y)` returns an integer representing the space with given `x` and `y` coordinates.   - The functions `x_(space)` and `y_(space)` invert that.- **Player**: a one-character string, `'*'` for black and `'o'` for white.  - The function `other(player)` gives the opponent player.- **Direction**: a direction of movement is an integer giving the difference between adjacent spaces.  - This is +1 for right; -1 for left; -6 for up (or in general, -N); +6 for down (or in general, +N).  - The function `go(space, direction, k)` gives the space that is `k` steps in `direction` from `space`.Here is the code:<jupyter_code>from typing      import *
from dataclasses import dataclass
from functools   import lru_cache
from collections import Counter, defaultdict
from itertools   import takewhile
import random
################ Types

Board  = int # A board is a bit string with a 1 bit for each space with a marble
State  = int # A state is a board shifted left, with a bit indicated whose turn it is
Space  = int # A space is an integer from 0 to N**2 - 1
Player = str # A character, '*' or 'o'
Direction = int # Direction of movement (left, right, up, down)

################ Constants

N      = 6
black  = '*'
white  = 'o'
empty  = '·'

################ Boards

def get(board, space) -> str:
    """Get the contents of space on board: black, white, or empty."""
    return (empty if board & (1 << space) == 0 else
            black if (x_(space) + y_(space)) % 2 == 0 else
            white)

def remove(board, spaces) -> Board: 
    """Return a new board with the marbles on spaces removed."""
    return board - sum(1 << s for s in spaces)

################ States

def start_state(removed=(0, 1)) -> State:
    """A new NxN board with a marble in all spaces, except `removed`,
    which should be a tuple of two spaces (default upper-left corner)."""
    full = sum(1 << s for s in range(N * N))
    return encode_state(remove(full, removed), black)

def encode_state(board, player) -> State:
    """Combine the board and the player into a single int."""
    return board * 2 + (player == black)

def decode_state(state) -> Tuple[Board, Player]:
    """Split the state into board and player components."""
    return state // 2, (black if state & 1 else white)

################ Spaces

def space(x, y) -> int: return N * y + x
def x_(space) -> int:   return space % N
def y_(space) -> int:   return space // N

def center() -> Tuple[Space, Space]:
    """Two spaces in the center of the board."""
    m = N // 2
    return space(m, m), space(m - 1, m)

################ Players

def other(player) -> Player: return white if player == black else black

################ Directions

L, R, U, D = directions = (-1, +1, -N, +N)

def go(space, direction, steps=1) -> Optional[Space]:
    """The space that is `steps` in `direction` from `space`,
    or `None` if going in that direction ends up off the board."""
    x, y = x_(space), y_(space)
    return (space + steps * direction 
            if (direction == L and steps <= x)
            or (direction == R and steps < N - x)
            or (direction == U and steps <= y)
            or (direction == D and steps < N - y)
            else None)<jupyter_output><empty_output><jupyter_text>Displaying Game StatesThe representation of a state is not very informative to look at, neither in decimal nor binary notation:<jupyter_code>start_state()
bin(_)<jupyter_output><empty_output><jupyter_text>I'll define a function, `state_str`, to create better-looking output for a state:<jupyter_code>def state_str(state) -> str:
    """A string depicting the given state of the game."""
    board, player = decode_state(state)
    def row(y): return f'{y + 1} | {" ".join(get(board, space(x, y)) for x in range(N))}'
    return (f'    {" ".join(columns[:N])} ({player} to move)\n  +{"--" * N}\n' +
            '\n'.join(row(y) for y in range(N)))

columns = 'abcdefghijklmnopqrstuvwxyz'
print(state_str(start_state()))
print(state_str(start_state(removed=center())))<jupyter_output>a b c d e f (* to move)
  +------------
1 | * o * o * o
2 | o * o * o *
3 | * o * o * o
4 | o * · · o *
5 | * o * o * o
6 | o * o * o *<jupyter_text>Making MovesThe next step is to define `legal_moves(state)` which returns a list of the available legal moves from a state, and `make_move(state, move)` which returns a new state that is the result of the chosen move. A move is a structure with fields for the starting space, the ending space, and the space(s) of the opponent marble(s) that were jumped. I'll divide the task of finding legal moves into two phases: first define all the `potential_moves` that start at a given square and go in a given direction. In that direction there can be a single jump, a double jump, etc.; as long as the jump doesn't go off the edge of the board. The jumps are processed in that order, so when we get to, say, a triple jump, we know that the single- and double-jumps were legal; that makes checking each jump for legality easier. The function `potential_moves` doesn't consider what marbles are on the board; the function `legal_moves` does. I have these two separate functions and put a `@lru_cache` on `potential_moves` so that `Move` objects are created only once (for each of the 36 spaces and 4 directions), not millions of times for each state. Because `Move`s are not created millions of times, I'm not worried about trying to make them be efficient bit strings.<jupyter_code>@dataclass
class Move:
    """A jumping move."""
    start:  Space
    jumped: List[Space]
    end:    Space
        
    def __str__(self):
        start, end, *jumped = [f'{columns[x_(s)]}{y_(s) + 1}'
                               for s in (self.start, self.end, *self.jumped)]
        return f'{start} → {end} jumping {" and ".join(jumped)}'

def legal_moves(state) -> List[Move]:
    """All possible moves for player from this state."""
    board, player = decode_state(state)
    opponent = other(player)
    def legal(move) -> bool:
        return get(board, move.jumped[-1]) == opponent and get(board, move.end) == empty
    return [move for start in range(N * N) if get(board, start) == player
                 for d in directions
                 for move in takewhile(legal, potential_moves(start, d))]
        
@lru_cache(None)
def potential_moves(start: Space, d: Direction) -> List[Move]:
    """All potential moves starting from space and going in direction, shortest first."""
    moves = []
    for steps in range(2, N, 2):
        end = go(start, d, steps)
        if end is not None:
            moves.append(Move(start, list(range(start + d, end, 2 * d)), end))
    return moves
        
def make_move(state, move) -> State:
    """Make a move from this state to yield a new state."""
    board, player = decode_state(state)
    board2 = remove(board | 1 << move.end, [move.start, *move.jumped])
    return encode_state(board2, other(player))<jupyter_output><empty_output><jupyter_text>Here are some examples of how these functions work:<jupyter_code>state1 = start_state()
state2 = make_move(state1, Move(start=12, jumped=[6], end=0))
print(state_str(state1))
{str(m): m for m in legal_moves(state1)}
print(state_str(state2))
{str(m): m for m in legal_moves(state2)}
potential_moves(space(0, 0), D)<jupyter_output><empty_output><jupyter_text>Strategies and Playing GamesWe're now ready to play a game. The function `play_game` takes as input a dictionary with two keys, black and white, each mapped to a strategy for that player. A **strategy** is a function that takes a state as input and returns a move.<jupyter_code>Strategy = Callable[[State], Move]

def play_game(strategies: Dict[Player, Strategy], start=None, verbose=True) -> Player:
    """Play a game between black and white, using their respective strategies.
    Return the player that wins the game."""
    state = start or start_state()
    while True:
        board, player = decode_state(state)
        if verbose: print(state_str(state))
        moves = legal_moves(state)
        if not moves:
            if verbose: print(f'\n{player} has no moves and loses')
            return other(player)
        else:
            move = strategies[player](state)
            if verbose: print(f'\n{player} moves {move}\n')
            assert move in moves
            state = make_move(state, move)
            
def play_games(strategies, k, start=None) -> Counter:
    """Play k games silently; return a count of winning players."""
    return Counter(play_game(strategies, start, False) for _ in range(k))
            
def random_strategy(state) -> Move:
    """Pick a random legal move."""
    return random.choice(legal_moves(state))<jupyter_output><empty_output><jupyter_text>Below black and white each play randomly:<jupyter_code>randomly = {black: random_strategy, white: random_strategy}

play_game(randomly)<jupyter_output>a b c d e f (* to move)
  +------------
1 | · · * o * o
2 | o * o * o *
3 | * o * o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

* moves a3 → a1 jumping a2

    a b c d e f (o to move)
  +------------
1 | * · * o * o
2 | · * o * o *
3 | · o * o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

o moves d1 → b1 jumping c1

    a b c d e f (* to move)
  +------------
1 | * o · · * o
2 | · * o * o *
3 | · o * o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

* moves c3 → c1 jumping c2

    a b c d e f (o to move)
  +------------
1 | * o * · * o
2 | · * · * o *
3 | · o · o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

o moves e2 → a2 jumping d2 and b2

    a b c d e f (* to move)
  +------------
1 | * o * · * o
2 | o · · · · *
3 | · o · o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

* moves a5 → a3 jumping a4

    a b c d e f (o to move)
  +------------
1 | * o * · * o
2 | o · · · · *
3 | * o · o * o
4 | · * o * o *
5 | · o * o * o
6 | o * o * o *

o moves[...]<jupyter_text>We can play 1000 random games and see who has an advantage:<jupyter_code>play_games(randomly, 1000)<jupyter_output><empty_output><jupyter_text>It looks like white has a slight advantage if both players play randomly. But what if they are more clever?  Playing OptimallyAs promised, here I define:- `winner` to determine which player can force a win from a given state.- `optimal_strategy` to play perfectly, taking advantage of the knowledge cached in `winner`.<jupyter_code>@lru_cache(None)
def winner(state) -> Player:
    """The player that can force a win from this state."""
    _, player = decode_state(state)
    return (player if any(winner(make_move(state, move)) == player 
                          for move in legal_moves(state))
            else other(player))

def optimal_strategy(state) -> Move:
    """Make a winning move if there is one."""
    _, player = decode_state(state)
    for move in legal_moves(state):
        if winner(make_move(state, move)) == player:
            return move
    return move<jupyter_output><empty_output><jupyter_text>Solving a Smaller Board: 4 by 4Before starting a time-consuming computation of the winner for a 6 by 6 board, I'd like to quickly validate the program on a smaller board; let's say 4 by 4. But I can't simply execute the statement `N = 4`, because other parts of the program depend on the value of `N`: the "up" and "down" directions `U` and `D`, as well as the caches for `potential_moves` and `winner`. So I'll introduce the function `set_N`:<jupyter_code>def set_N(n):
    """Use an n x n board; set global variables accordingly."""
    global N, R, L, U, D, directions
    if n != N:
        N = n
        L, R, U, D = directions = (-1, +1, -N, +N)
        potential_moves.cache_clear()
        winner.cache_clear()<jupyter_output><empty_output><jupyter_text>Now we can solve 4 by 4 Konane:<jupyter_code>set_N(4)

winner(start_state()), winner(start_state(removed=center()))<jupyter_output><empty_output><jupyter_text>That says that **white is the winner on a 4 by 4 board, from either starting position**.Here's an optimally-played 4 by 4 game:<jupyter_code>optimally = {black: optimal_strategy, white: optimal_strategy}

play_game(optimally)<jupyter_output>a b c d (* to move)
  +--------
1 | · · * o
2 | o * o *
3 | * o * o
4 | o * o *

* moves a3 → a1 jumping a2

    a b c d (o to move)
  +--------
1 | * · * o
2 | · * o *
3 | · o * o
4 | o * o *

o moves d1 → b1 jumping c1

    a b c d (* to move)
  +--------
1 | * o · ·
2 | · * o *
3 | · o * o
4 | o * o *

* moves c3 → c1 jumping c2

    a b c d (o to move)
  +--------
1 | * o * ·
2 | · * · *
3 | · o · o
4 | o * o *

o moves b1 → d1 jumping c1

    a b c d (* to move)
  +--------
1 | * · · o
2 | · * · *
3 | · o · o
4 | o * o *

* has no moves and loses<jupyter_text>As expected, white wins.Although white will win every game with optimal play, if white plays randomly, an optimal black player can win a majority of games:<jupyter_code>play_games({black: optimal_strategy, white: random_strategy}, 1000)<jupyter_output><empty_output><jupyter_text>Solving a 5 by 5 BoardWe can repeat the exercise on a 5 by 5 board. This time I will check how long it takes to solve:<jupyter_code>set_N(5)

%time winner(start_state()), winner(start_state(removed=center()))<jupyter_output>CPU times: user 668 ms, sys: 3.7 ms, total: 671 ms
Wall time: 671 ms<jupyter_text>With a **5 by 5 board, black wins from either starting position**. The computation takes about 2/3 of a second.  Solving Mel's 6 by 6 BoardFinally we are ready to solve the 6 by 6 board.  A 6 by 6 board has 211 = 2048 times more states than a 5 by 5 board, and each state is bigger and thus will take more time to process. So I estimate it will take about a half hour to fill the `winner` cache for a 6 by 6 board.  Let's find out (one starting position at a time):<jupyter_code>set_N(6)

%time winner(start_state())<jupyter_output>CPU times: user 3min 55s, sys: 439 ms, total: 3min 55s
Wall time: 3min 58s<jupyter_text>So **white wins a 6 by 6 game** when we start with corner marbles removed. And the computation was a **lot faster** than I guessed! How many states were explored? The `cache_info` method will tell us:<jupyter_code>winner.cache_info()<jupyter_output><empty_output><jupyter_text>The `currsize` field is the number of states in the cache; about 10 million. Now let's see who wins if we start with the center marbles removed:<jupyter_code>%time winner(start_state(removed=center()))<jupyter_output>CPU times: user 1h 10min 59s, sys: 7.85 s, total: 1h 11min 7s
Wall time: 1h 13min 34s<jupyter_text>**White wins there too**, but my celebration over the speed of the program was a bit premature–that took a full hour, double my estimate. We can count the total number of states from both starting positions:<jupyter_code>winner.cache_info()<jupyter_output><empty_output><jupyter_text>That's 145 million states. I guess it makes sense that there would be more reachable states starting from a position with the center pieces removed, because we can spread to any corner. It also makes sense that the corner-removed board leads to a search space that is more tree-like (the ratio of hits/misses–that is, the ratio of paths that lead to a state a second time to total states–is 0.8) and the center-removed board leads to a search space that is more graph-like (the ratio is 1.3).Here's an optimally-played game (which we expect white to win):<jupyter_code>play_game(optimally)<jupyter_output>a b c d e f (* to move)
  +------------
1 | · · * o * o
2 | o * o * o *
3 | * o * o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

* moves a3 → a1 jumping a2

    a b c d e f (o to move)
  +------------
1 | * · * o * o
2 | · * o * o *
3 | · o * o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

o moves d1 → b1 jumping c1

    a b c d e f (* to move)
  +------------
1 | * o · · * o
2 | · * o * o *
3 | · o * o * o
4 | o * o * o *
5 | * o * o * o
6 | o * o * o *

* moves a5 → a3 jumping a4

    a b c d e f (o to move)
  +------------
1 | * o · · * o
2 | · * o * o *
3 | * o * o * o
4 | · * o * o *
5 | · o * o * o
6 | o * o * o *

o moves f1 → d1 jumping e1

    a b c d e f (* to move)
  +------------
1 | * o · o · ·
2 | · * o * o *
3 | * o * o * o
4 | · * o * o *
5 | · o * o * o
6 | o * o * o *

* moves c5 → a5 jumping b5

    a b c d e f (o to move)
  +------------
1 | * o · o · ·
2 | · * o * o *
3 | * o * o * o
4 | · * o * o *
5 | * · · o * o
6 | o * o * o *

o moves c2 → a[...]<jupyter_text>SummaryHere's a chart of who has a forced win for various values of **N**, in the cases where the two marbles are removed from the corner and from the center:|N|Corner|Center||-|------|------||4|white|white||5|black|black||6|white|white||7+|?????|?????| Further WorkI'll stop here, but here are some things that you could look into if you are interested:- **Make it prettier**: Use graphics for the output, e.g. ⚪️ and ⚫️ instead of 'o' and '*'.- **Make it interactive**: allow players to click on the board to make moves and set up positions. An interactive web page would be great, but loading 145 million positions into it would take a while. But you could trim that down: the 145 million states include the exploration of multiple paths for the optimal player, until a winning path is found. You could eliminate all branches of the tree except for one winning choice at each choice point for the optimal player (and all responses for the opponent).- **Use a faster language**: Statically-typed languages like Java or C++ or Go can typically execute faster than Python. Of particular interest for this program, in Python 3 the `int` returned by `start_state()` uses 32 bytes of memory. There is overhead to store the reference count, the type of the object, etc. Other languages can represent a state in just 8 bytes, as a 64-bit integer.- **Use concurrency**: Python is not a convenient language for taking advantage of multiple CPUs, so I didn't try to parallelize the search. But you could.- **Find heuristics for good but non-optimal play**: No matter how clever we get, there will be some value of **N** beyond which solving the game is impractical. But we could still achieve good play by doing alpha-beta search to a certain cut-off level and using an evaluation function to rank the resulting game states.  The evaluation function could be hand-crafted from features or learned with machine learning. Alternatively, Monte Carlo tree search could be used; this does not require an evaluation function.- **Explore the computational complexity**: My friend <NAME> has a nice [paper](https://www.semanticscholar.org/paper/Amazons%2C-Konane%2C-and-Cross-Purposes-are-Hearn/89f291d89c09de98a14bb265e996cd008ddd4e92) proving that Konane is PSPACE-complete. What else can be said?- **Apply combinatorial game theory**: A [paper](https://www.cs.cmu.edu/~sleator/papers/Sprouts.htm) by several authors including my friend <NAME> shows how to use combinatorial game theory to break a game state into components that can be analyzed separately and then combined. Using these techniques allowed them to solve the game of Sprouts for much larger sizes than had been done before; I suspect the same approach would work for Konane. Whether combinatorial game theory would work for Konane or not, it is a fascinating piece of mathematics to know about. As <NAME> said in [a review](http://webdocs.cs.ualberta.ca/~hayward/cgt/asn/hearn-WW.pdf) of the classic [Winning Ways for Your Mathematical Plays](https://www.amazon.com/Elwyn-R-Berlekamp/e/B001HQ1K5A/ref=dp_byline_cont_pop_book_1), "The theory hinges on an amazing discovery of [John] Conway. In a nutshell, the natural unification of Cantor’s construction of the ordinals with Dedekind’s construction of the reals yields, in one stroke, not only the fabulous number system that Donald Knuth dubbed the surreal numbers, but also a natural framework for combinatorial games. It’s as if the the mathematics we all know, that underpins all of science, were suddenly revealed to be a just special case of games: the universe is telling us that ultimately, it’s all about play."  Appendix: TestsSome simple tests of the low-level functions:<jupyter_code>def test():
    set_N(6)
    state = start_state()
    board, player = decode_state(state)
    assert state == encode_state(board, player)
    assert player == black
    assert get(board, 0) == empty and get(board, 2) == black and get(board, 3) == white
    
    board2 = remove(board, [3, 4])
    assert get(board2, 3) == empty
    
    s = space(0, 0)
    assert (go(s, R), go(s, L), go(s, U), go(s, D)) == (1, None, None, 6)
    
    s = space(2, 1)
    assert s == 8 and x_(s) == 2 and y_(s) == 1
    assert go(s, R) == space(3, 1)
    assert go(s, L) == space(1, 1)
    assert go(s, U) == space(2, 0)
    assert go(s, D) == space(2, 2)
    assert go(s, L, 2) == space(0, 1)
    assert go(s, L, 3) == None
    
    assert other(black) == white and other(white) == black
    
    assert potential_moves(0, R) == [Move(start=0, jumped=[1], end=2), 
                                     Move(start=0, jumped=[1, 3], end=4)]
    return True

test()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11145924878682512, 'fraction_numerical': 0.01925795728095984, 'mean_word_length': 3.291195277914412, 'pattern_counts': {'":': 0, '<': 91, '<?xml version=': 0, '>': 100, 'https://': 4, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '20', 'dir': 'jupyter-structured-clean-dedup', 'id': '463967', 'license': 'MIT', 'n_tokens_mistral': 8321, 'n_tokens_neox': 7914, 'n_words': 3941, 'path': 'ipynb/Konane.ipynb', 'repo_name': 'brezaei/pytudes', 'size': '26198'}