Twixt

  Difficulty: Introductory   Keywords: Variant

A game published in the 1960s by the 3M corporation in their "bookshelf" line. The board consists of a 24x24 array of holes arranged in a square grid. The outermost line of holes surrounding the board is partitioned off, and opposite sides are assigned to opposing players by colors red and black (similarly to Hex).

Players take turns placing colored pegs into the holes, and when two pegs of the same color share a "Knight's Move" relationship to each other, they place a small plastic bar across the tops of the pegs. As in Hex, the goal is to complete a bridge from one side of the board to the opposite side using these bars. Since bars are not allowed to cross each other, they can be used defensively (block the way of the opponent) as well.


http://images.boardgamegeek.com/images/pic36542_md.jpg


There are two common rulesets:

    • Standard Twixt Rules allow one to remove links that are already on the board.
    • TwixtPP (Pencil and Paper, e.g. like played at Little Golem) means: no link removal, however you are instead allowed to cross your own links.

Practically, the game is about the same for both rulesets. "Link removal" does only matter in rare situations in the endgame.

Draws are possible (=locked up situation with neither player able to complete a connection).


Twixt playing (1): The Twixt Server k2z

[ext] http://www.gamerz.net/k2z/k2zWelcome.html

  • Steps to get started:
    • Download the client: [ext] http://www.gamerz.net/k2z/download
    • use the new Server URL: www.gamerz.net, Port: 57017 (both should be default in newest client)
    • use as Login: guest1,2,3,...9, Password: guest1,2,3,...9
    • or register an account, that way your rating will be tracked and opponents will know who they are playing.
    • one way to find other players is in the "little golem" [ext] twixt forum

Twixt playing (2)


Programming a Computer Opponent for Twixt

Thoughts on representing a board situation

  • For computer Twixt, standard rules without link removal can be used (as simplification). So, a representation of a move consists just of an x and y coordinate, and links are automatically added. There are 24x22=528 legal moves in the beginning.
  • simplest: keep a lists of pegs and links for each player
  • or, represent the board as a 24x24 array for the pegs and have another (about 24x24) array for the links (8 directions=8bit-bitfield); 2 possibilities:
    • store each link "twice" in the array (once for the point where the link begins and once for the point where it ends)
    • store each link only once in the array, but use the convention, that links have to go to the right (for example) =only 4 directions left (T1 uses this)
  • what next? Already "connected" pegs, together with the links that connect them, form a group, which the opponent can't break and which will stay on the board like it is till the end of the game (exception: link removal, if the rules allow it). So the program can recognize and represent such groups in some datastructure. The merging and breaking up of connected groups (undo) can be done incrementally, if the necessary infos are kept. Checking for a win or connectedness of groups is now very fast.
  • another useful idea might be to normalize the board, so that the player to move always plays horizontally (or vertically). This is useful to simplify generating moves, and other algorithms like pattern matching. To do this there are two instances of a TwixtBoard? used, first the normal board, and as second a diagonally mirrored board (x and y axis swapped). After making / undoing a move, two pointers are swapped and the player to move is again the horizontal player.
  • the next level would be to have also 2 boards mirrored along the vertical axis, for searching for connections to the left OR right border of the board, depending on which subgame you are considering (an example for subgames: moves at the left side of the board might be completely independent of moves at the right side of the board, although both areas might not yet be completley connected, but both sides have to get connected, finally (AND-situation)) (in the opening there are no subgames, so it doesn't matter which of the 2 (mirrored) boards you look at for choosing the move).
    • (So this gives a sum of 4 boards to update (or recalculate) for every move or undone move)
  • to mirror the board also along the horizontal axis (player-to-move still plays horizontally) might make sense for very few algorithms (opening database is an example, this is normalized for first peg in upper left corner). However the above 2 normalizations are more useful/important.
  • UPDATE (last 2 points): my opinion is now to use only the 2 mirrored boards that are updated for every move (during search etc). 4 or 8 boards is too complicated and not really useful (lots of coordinate-transformations to find the same point in another board). For 2 boards you just have to swap x and y coordinates, so not a too big problem.

Visualization of link crossing

http://www.johannes-schwagereit.de/twixt/T1/T1_OldVersion.png

Exactly 9 "virtual" bridges can cross an existing bridge.

Possible Strategies

  • an opening book for the first moves is necessary, but of course it can't cover all possible situations in the opening

About Search

  • there seems to be a special kind of search necessary:
    • sometimes (especially towards the end of the game) there might be a winning move a for Player A (or a move that gives a big advantage) but it's Player B's turn: so it's clear that B must block A's way "somehow" (play in same area); especially all the about 400-500 other legal moves would lose immediately, so they need not be generated if you can prove that they make no difference!
    • replace "a winning move a for Player A" by "an area (or a set of points), where at least some moves in the area would win (but definitely none out of this area)"

Rules/Patterns/Generating Moves

  • rules/patterns: there are a few moves, which are often good, so the computer can try these moves first (then some other moves in the same area):
    • extensions/jumps: 2-1,1-2;3-3,4-0, etc
    • blocks: 2-0,4-0, etc

Diagonal guide lines

Analyzing the goodness of a certain board position

Evaluation function

... to be written

Subgames (in simple situations)

  • another observation is, that independent subgames often emerge quite early in the game; sometimes as soon as a (longer) string in the middle of the board exists, and "only" the 2 ends have to be connected to the sides (AND-Situation).
  • to consider 2 situations (at the 2 ends of the large group/string, for example) as subgames might make sense, in a given situation, only, if the player-to-move is able to win both subgames provably (or at least very likely, according to heuristics). Being not able to win one of the 2 subgames directly means a different strategy has to be chosen, which possibly only uses the large group (at which's 2 ends the 2 subgames exist) as an indirect threat.
  • when analyzing subgames it is not only interesting whether the player-to-move can win the subgame, but also whether he can win it, even if he moves second in the subgame.

Perfect play (on small boards)

  • Rules:
    • (no swap allowed)

4x4

  • 8 legal moves as Move1 for Player1
  • all moves result in a tie, because no complete connection is possible on this small board
[Diagram]
4x4  

5x5

  • 6 possible moves (with considering symmetries) for Move1
  • all moves result in a draw with perfect play! Mainly because point (3,2) can't connect to the top.
[Diagram]
5x5  
[Diagram]
5x5  

If "Vertical" plays 1, H plays 2 (for example), etc...


6x6

[Diagram]
6x6  

Twixt Puzzles

  • [ext] http://www.gamerz.net/pbmserv/Twixt/puzzles.html 40 puzzles
    • These 40 problems can also be used as testcases for a program, to test whether it is able to solve the problems (though at the moment no good enough program exists). (-> there is no download address for this, but ask in littlegolem twixt forum, if you need it)

List of known Twixt-playing programs

http://www.johannes-schwagereit.de/twixt/T1/t1_06.png (picture of T1)

  • T2 (independently modified version of T1), it has some new features - very basic .sgf support, rewritten ai; for Windows + Linux, open source
  • [ext] http://www.johannes-schwagereit.de/twixt/ T1j (written in Java; open source), strongest program (but still weak in absolute terms)

other links:


Discussion about this page on /Discussion


Twixt last edited by 78.48.52.114 on February 27, 2010 - 22:49
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library