how to win at checkers every time<div dir="auto"><br></div><div dir="auto">1. describe the board state (as an 8x8 or 4x8 or whatnot) grid</div><div dir="auto">2. determine how legals moves mutate any grid</div><div dir="auto">3. compose an (initial board state as the starting game state</div><div dir="auto">4. spend forever determining unique board states and arranging them in a tree rooted in the initial board state. hash them to check for uniqueness so as to produce loop links back in the tree rather than iterating repetitions truly forever.</div><div dir="auto"><br></div><div dir="auto">ok thinking a little here, been years since simple decision tree thoughts have gotten this far … uhh … when can it win …</div><div dir="auto">thinking</div><div dir="auto">- if the state is a win that’s good</div><div dir="auto">- if one of the moves makes a state that’s a win, that’s the move to make, and the state with that option can be considered a win</div><div dir="auto">i guess you’d want to propagate that win state upward so as to try to solve the game. but if the game is fair eventually it would stop propagating upward, and instead you’d want to propagate a percentage chance of guaranteeing a win</div><div dir="auto">(if this chance weren’t guaranteed, i guess we’d need to know when we have lost. we’ve lost when the opponent is in a state where they have won. at that point we need to engage their mind and behavior rather than the solution of the game states. ….</div><div dir="auto">(so you could propagate it up for both players. when can black reach a certain win, when can white reach a certain win</div><div dir="auto">(…(</div><div dir="auto">let’s consider a state where a win stops propagating (</div><div dir="auto">(if the opponent makes one move, it enters a certain win state. if they make another move, it enters a certain loss state. if they make a third move it enters an uncertain state again.</div><div dir="auto">so we could consider all the possible moves they can make, and what % makes certain loss and what % makes certain win. also what % enter a repeating state. given the game doesn’t end when it repeats that could have its %s calculated recursively or something, which might likely be equivalent to disregarding it if it’s in the play history. meanwhile unknown states can be defined recursively, and have their % defined by propagating upward from lower states.</div><div dir="auto">and of course in a real world scenario the likelihoods could be guessed as well as other heuristics or simplifying approaches like pattern identification or extraction.</div><div dir="auto">ok so each state can be broken into %win + %loss +(value derived from deeper wins and losses) = 100% , win and loss are the only options … unless there are draw options where it’s impossible for one player to win, such as no moveable pieces or only loops. ok so %win + %loss + %stall . we can then calculate the %win.</div><div dir="auto">- consider all the states that are wins and give them 100% win chance, similarly with losses. propagate these values upward assuming a simple uniform distribution of move choices …</div><div dir="auto">(does that work? i’m confused that (a) the distribution is uniform and (b) there is a winning choice ie picking the move with highest win %. … uhhh … uhhh …</div><div dir="auto">let’s consider a paired state again. it’s one player’s turn. some moves lead to certain win for them, some lead to certain loss.</div><div dir="auto">but because this contains a state of certain win as a possibility, it is also for them a state of certain win.</div><div dir="auto">if we had the computational capacity to evaluate every game state, how remains uncertainty in the game? would it be a situation where whoever moves first wins if they always make the best move?</div><div dir="auto">(…</div><div dir="auto"><br></div><div dir="auto">uhhh probably how can i confirm this (</div><div dir="auto"><br></div><div dir="auto">- leaf states are all among (red wins, black wins, there can be no winner, there is no way to know the winner). </div><div dir="auto">- each state is reached by a legal move from a previous state</div><div dir="auto">- in each previous state, if a future state leads to a win, whoever’s move it is it makes sense to make the move that does that. this makes that state effectively a win for the player whose move it is.</div><div dir="auto">- so all the parents of leaf states among (red wins, black wins) are also among (red wins, black wins).</div><div dir="auto">- if we assume the tree is fully expanded, we don’t expect any (there is no way to know the winner) states in leaves … do we? maybe not?</div><div dir="auto">- (there is no way to know the winner) is actually possible if the state would be (there can be no winner) under good move choice, but if a player makes a mistake, the other player could win. we could maybe combine those states into (there is no way for a player to guarantee a win in this state)</div><div dir="auto">- but given there are win states and loss states, and each real one has a valid history of moves … let’s consider their parents</div><div dir="auto"><br></div><div dir="auto">this is fun but we have a concern</div>