Dodgem is a simple abstract strategy game invented by Colin Vout in 1972 while he was a mathematics student at the University of Cambridge as described in the book Winning Ways . It is played on an n × n board with n-1 cars for each player—two cars each on a 3×3 board is enough for an interesting game, but larger sizes are also possible.
21-458: The board is initially set up with n-1 blue cars along the left edge and n-1 red cars along the bottom edge, the bottom left square remaining empty. Turns alternate: player 1 ("Left")'s turn is to move any one of the blue cars one space forwards (right) or sideways (up or down). Player 2 ("Right")'s turn is to move any one of the red cars one space forwards (up) or sideways (left or right). Cars may not move onto occupied spaces. They may leave
42-407: A rule base containing the following four rules: With backward reasoning, an inference engine can determine whether Fritz is green in four steps. To start, the query is phrased as a goal assertion that is to be proven: "Fritz is green". 1. Fritz is substituted for X in rule #3 to see if its consequent matches the goal, so rule #3 becomes: Since the consequent matches the goal ("Fritz is green"),
63-416: A consequent ( Then clause) that matches a desired goal. If the antecedent ( If clause) of that rule is not known to be true, then it is added to the list of goals (for one's goal to be confirmed one must also provide data that confirms this new rule). For example, suppose a new pet, Fritz, is delivered in an opaque box along with two facts about Fritz: The goal is to decide whether Fritz is green, based on
84-477: A loss. If there are multiple options with the same outcome, perfect play is sometimes considered the fastest method leading to a good result, or the slowest method leading to a bad result. Perfect play can be generalized to non- perfect information games, as the strategy that would guarantee the highest minimal expected outcome regardless of the strategy of the opponent. As an example, the perfect strategy for rock paper scissors would be to randomly choose each of
105-443: A move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time. Many algorithms rely on a huge pre-generated database and are effectively nothing more. As a simple example of a strong solution, the game of tic-tac-toe is easily solvable as a draw for both players with perfect play (a result manually determinable). Games like nim also admit
126-410: A non-final position as identical to the position that is one move away and best valued for the player whose move it is. Thus a transition between positions can never result in a better evaluation for the moving player, and a perfect move in a position would be a transition between positions that are equally evaluated. As an example, a perfect player in a drawn position would always get a draw or win, never
147-509: A rigorous analysis using combinatorial game theory . Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if its solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g., Maharajah and the Sepoys ). An ultra-weak solution (e.g., Chomp or Hex on
168-405: A scholar to reason about the abstract properties of the game, and show how these properties lead to certain outcomes if perfect play is realized. By contrast, "strong" proofs often proceed by brute force — using a computer to exhaustively search a game tree to figure out what would happen if perfect play were realized. The resulting proof gives an optimal strategy for every possible position on
189-448: A solution to the game, in a process called backward induction . In chess, it is called retrograde analysis , and it is used to generate table bases for chess endgames for computer chess . Backward chaining is implemented in logic programming by SLD resolution . Both rules are based on the modus ponens inference rule. It is one of the two most commonly used methods of reasoning with inference rules and logical implications –
210-457: A sufficiently large board) generally does not affect playability. In game theory , perfect play is the behavior or strategy of a player that leads to the best possible outcome for that player regardless of the response by the opponent. Perfect play for a game is known when the game is solved. Based on the rules of a game, every possible final position can be evaluated (as a win, loss or draw). By backward reasoning , one can recursively evaluate
231-405: Is a conjunction of two statements, the inference engine breaks it into two sub-goals, both of which must be proven: 4. To prove both of these sub-goals, the inference engine sees that both of these sub-goals were given as initial facts. Therefore, the conjunction is true: therefore the antecedent of rule #1 is true and the consequent must be true: therefore the antecedent of rule #3 is true and
SECTION 10
#1732898294577252-412: Is usually applied to abstract strategy games , and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance. A two-player game can be solved on several levels: Despite their name, many game theorists believe that "ultra-weak" proofs are the deepest, most interesting and valuable. "Ultra-weak" proofs require
273-466: The board, but only by a forward move. A car which leaves the board is out of the game. There are no captures. A player must always leave their opponent a legal move or else forfeit the game. The winner is the player who first gets all their pieces off the board, or has all their cars blocked in by their opponent. The game can also be played in Misere, where you force your opponent to move their pieces off
294-475: The board. The 3×3 game can be completely analyzed ( strongly solved ) and is a win for the first player—a table showing who wins from every possible position is given in Winning Ways , and given this information it is easy to read off a winning strategy. David des Jardins showed in 1996 that the 4×4 and 5×5 games never end with perfect play—both players get stuck shuffling their cars from side to side to prevent
315-481: The board. However, these proofs are not as helpful in understanding deeper reasons why some games are solvable as a draw, and other, seemingly very similar games are solvable as a win. Given the rules of any two-person game with a finite number of positions, one can always trivially construct a minimax algorithm that would exhaustively traverse the game tree. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate
336-405: The consequent must be true: This derivation, therefore, allows the inference engine to prove that Fritz is green. Rules #2 and #4 were not used. Note that the goals always match the affirmed versions of the consequents of implications (and not the negated versions as in modus tollens ) and even then, their antecedents are then considered as the new goals (and not the conclusions as in affirming
357-525: The form of endgame tablebases ), which will allow it to play perfectly after some point in the game. Computer chess programs are well known for doing this. Backward chaining Backward chaining (or backward reasoning ) is an inference method described colloquially as working backward from the goal. It is used in automated theorem provers , inference engines , proof assistants , and other artificial intelligence applications. In game theory , researchers apply it to (simpler) subgames to find
378-444: The options with equal (1/3) probability. The disadvantage in this example is that this strategy will never exploit non-optimal strategies of the opponent, so the expected outcome of this strategy versus any strategy will always be equal to the minimal expected outcome. Although the optimal strategy of a game may not (yet) be known, a game-playing computer might still benefit from solutions of the game from certain endgame positions (in
399-469: The other from winning. He conjectures that this is true for all larger boards. For Dodgem on a 3x3 board, there are 1963 reachable positions. Out of the 1963 reachable positions, 1123 of them are winning and 840 of them are losing for the player-to-move. There are no draws. Solved game A solved game is a game whose outcome (win, lose or draw ) can be correctly predicted from any position, assuming that both players play perfectly. This concept
420-416: The other is forward chaining . Backward chaining systems usually employ a depth-first search strategy, e.g. Prolog . Backward chaining starts with a list of goals (or a hypothesis ) and works backwards from the consequent to the antecedent to see if any data supports any of these consequents. An inference engine using backward chaining would search the inference rules until it finds one with
441-433: The rules engine now needs to see if the antecedent ("Fritz is a frog") can be proven. The antecedent, therefore, becomes the new goal: 2. Again substituting Fritz for X, rule #1 becomes: Since the consequent matches the current goal ("Fritz is a frog"), the inference engine now needs to see if the antecedent ("Fritz croaks and eats flies") can be proven. The antecedent, therefore, becomes the new goal: 3. Since this goal
SECTION 20
#1732898294577#576423