A good data structure for representing a tic-tac-toe board?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

A good data structure for representing a tic-tac-toe board?

Costello, Roger L.
Hi Folks,

Currently I am representing a tic-tac-toe board as a string, with 'X' denoting player 1 and 'O' denoting player 2. For example, I represent this 2x2 game board:

     'X' |  
-----------------------
  |   'O'

with this string: "X  O"

The nice thing about that representation is that it is each to identify which cells are filled or empty, and it is easy to mark a cell with an 'X' or 'O'.

The problem with the representation is that it is difficult to determine when a player has won.

Can you recommend a representation that makes it easy to:

1. determine when a player has won
2. identify cells that are filled or empty
3. mark an empty cell

/Roger


Reply | Threaded
Open this post in threaded view
|

A good data structure for representing a tic-tac-toe board?

Peter Hall
Start with a data type for the cell values, instead of Char. Then use an
Array of Arrays, containing those values.

data Cell = Empty | O | X
type Board = Array Int Cell

Finding winning "rows" and "columns" is easy. Diagonals are slightly more
complicated.

Peter



On 18 March 2013 15:54, Costello, Roger L. <costello at mitre.org> wrote:

> Hi Folks,
>
> Currently I am representing a tic-tac-toe board as a string, with 'X'
> denoting player 1 and 'O' denoting player 2. For example, I represent this
> 2x2 game board:
>
>      'X'        |
> -----------------------
>         |   'O'
>
> with this string: "X  O"
>
> The nice thing about that representation is that it is each to identify
> which cells are filled or empty, and it is easy to mark a cell with an 'X'
> or 'O'.
>
> The problem with the representation is that it is difficult to determine
> when a player has won.
>
> Can you recommend a representation that makes it easy to:
>
> 1. determine when a player has won
> 2. identify cells that are filled or empty
> 3. mark an empty cell
>
> /Roger
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130318/5023767b/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

A good data structure for representing a tic-tac-toe board?

Brent Yorgey-2
In reply to this post by Costello, Roger L.
Consider the following game:

Two players take turns choosing a number from 1-9 (inclusive).  Once a
number has been chosen it cannot be chosen again.  The winner is the
first player to have three of their selected numbers which sum
to 15.

Surprisingly, this game turns out to be isomorphic to tic-tac-toe,
which can be seen by arranging the numbers from 1-9 in a magic square,
such as

8 3 4
1 5 9
6 7 2

It is not hard to check that three distinct numbers from 1-9 sum to 15
if and only if they correspond to a tic-tac-toe win on the board
above.  This means you can represent the state of the board as a pair
of sets.  To check the state of a cell you look up the corresponding
number from the board above in both sets.  To mark an empty cell you
add the corresponding number to one of the sets.  To check whether a
player has won, you list all size-3 subsets of their set and check
whether any of them sum to 15.

You may or may not agree that this fulfills your criteria, but at
least it is cute.

-Brent

On Mon, Mar 18, 2013 at 03:54:58PM +0000, Costello, Roger L. wrote:

> Hi Folks,
>
> Currently I am representing a tic-tac-toe board as a string, with 'X' denoting player 1 and 'O' denoting player 2. For example, I represent this 2x2 game board:
>
>      'X' |  
> -----------------------
>   |   'O'
>
> with this string: "X  O"
>
> The nice thing about that representation is that it is each to identify which cells are filled or empty, and it is easy to mark a cell with an 'X' or 'O'.
>
> The problem with the representation is that it is difficult to determine when a player has won.
>
> Can you recommend a representation that makes it easy to:
>
> 1. determine when a player has won
> 2. identify cells that are filled or empty
> 3. mark an empty cell
>
> /Roger
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners


Reply | Threaded
Open this post in threaded view
|

A good data structure for representing a tic-tac-toe board?

Lyndon Maydwell
In reply to this post by Peter Hall
If taking the array approach, I'd recommend using a single array indexed by
the (x,y) position of the cell, this way neither direction has a greater
implied significance. Diagonals should also be easier.

Aside: Tony Morris wrote a very interesting exercise based on tic-tac-toe
and it is available on Hackage: http://hackage.haskell.org/package/TicTacToe


On Tue, Mar 19, 2013 at 3:49 AM, Peter Hall <peter.hall at memorphic.com>wrote:

> Start with a data type for the cell values, instead of Char. Then use an
> Array of Arrays, containing those values.
>
> data Cell = Empty | O | X
> type Board = Array Int Cell
>
> Finding winning "rows" and "columns" is easy. Diagonals are slightly more
> complicated.
>
> Peter
>
>
>
> On 18 March 2013 15:54, Costello, Roger L. <costello at mitre.org> wrote:
>
>> Hi Folks,
>>
>> Currently I am representing a tic-tac-toe board as a string, with 'X'
>> denoting player 1 and 'O' denoting player 2. For example, I represent this
>> 2x2 game board:
>>
>>      'X'        |
>> -----------------------
>>         |   'O'
>>
>> with this string: "X  O"
>>
>> The nice thing about that representation is that it is each to identify
>> which cells are filled or empty, and it is easy to mark a cell with an 'X'
>> or 'O'.
>>
>> The problem with the representation is that it is difficult to determine
>> when a player has won.
>>
>> Can you recommend a representation that makes it easy to:
>>
>> 1. determine when a player has won
>> 2. identify cells that are filled or empty
>> 3. mark an empty cell
>>
>> /Roger
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130319/5ae4c620/attachment-0001.htm>

Reply | Threaded
Open this post in threaded view
|

A good data structure for representing a tic-tac-toe board?

emacstheviking
In reply to this post by Costello, Roger L.
Roger,

Without writing any code, and still learning Haskell I personally don't see
anything intrinsically wrong with using a String, it's simple, it works and
what more can you ask from code than that!

I would go so far as to add "\n" after each line so that you can print the
status of the game to the console in one go, then checking for a winning
line would be as simple as writing a function that takes as its input the
String and a list of string offsets which make up a line, with the
assumption that [0] is the first board position, [2] is the end of the
first line and [3] contains the first "\n" character I would (pseudo-code /
made up from keyboard, pebcak may apply) go for this approach:

topLineWin     = checkLine myBoard  "O" [0,1,2]   -- did O win ?
topleftDiagWin = checkLine myBoard  "X" [0,5,10]  -- did X win ?
botLineWin     = checkLine my Board "X" [8,9,10]  -- did X win ?

and so on. The implementation of checkLine is left as an exercise for the
reader as they say but by using partial application you can make the code
very readbable. I might even try this myself and post it back for a laugh.
It's surprising sometime the difference between what you think you know and
what you actually know!

Some coding hints and thinking as I go...

topLine = [0,1,2]
topleftDiagWin = [0,5,10]
etc.

winnerO = checkLine myString "O"
winnerX = checkLine myString "X"

checkLine topLine playerCode -- did the top line win?
...


By making the checkLine return a Bool then you can have a list of functions
that you could then pass through the Data.List.all and make it something
like this:

  all [ winnerO topLine, winnerO botLine, ... etc]

Just to make the array number clear, here is the complete board:

         "\n"
0  1   2  3
4  5   6  7
8  9  10 10

All the best, that's no coding and pure thought for that so YMMV!

Sean Charles.


On 18 March 2013 15:54, Costello, Roger L. <costello at mitre.org> wrote:

> Hi Folks,
>
> Currently I am representing a tic-tac-toe board as a string, with 'X'
> denoting player 1 and 'O' denoting player 2. For example, I represent this
> 2x2 game board:
>
>      'X'        |
> -----------------------
>         |   'O'
>
> with this string: "X  O"
>
> The nice thing about that representation is that it is each to identify
> which cells are filled or empty, and it is easy to mark a cell with an 'X'
> or 'O'.
>
> The problem with the representation is that it is difficult to determine
> when a player has won.
>
> Can you recommend a representation that makes it easy to:
>
> 1. determine when a player has won
> 2. identify cells that are filled or empty
> 3. mark an empty cell
>
> /Roger
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130319/a571166b/attachment.htm>

Reply | Threaded
Open this post in threaded view
|

A good data structure for representing a tic-tac-toe board?

Peter Hall
In reply to this post by Lyndon Maydwell
Ah yes, that is nicer! I got too used to the limitations of the other
languages I use :)

Peter


On 19 March 2013 03:16, Lyndon Maydwell <maydwell at gmail.com> wrote:

> If taking the array approach, I'd recommend using a single array indexed
> by the (x,y) position of the cell, this way neither direction has a greater
> implied significance. Diagonals should also be easier.
>
> Aside: Tony Morris wrote a very interesting exercise based on tic-tac-toe
> and it is available on Hackage:
> http://hackage.haskell.org/package/TicTacToe
>
>
> On Tue, Mar 19, 2013 at 3:49 AM, Peter Hall <peter.hall at memorphic.com>wrote:
>
>> Start with a data type for the cell values, instead of Char. Then use an
>> Array of Arrays, containing those values.
>>
>> data Cell = Empty | O | X
>> type Board = Array Int Cell
>>
>> Finding winning "rows" and "columns" is easy. Diagonals are slightly more
>> complicated.
>>
>> Peter
>>
>>
>>
>> On 18 March 2013 15:54, Costello, Roger L. <costello at mitre.org> wrote:
>>
>>> Hi Folks,
>>>
>>> Currently I am representing a tic-tac-toe board as a string, with 'X'
>>> denoting player 1 and 'O' denoting player 2. For example, I represent this
>>> 2x2 game board:
>>>
>>>      'X'        |
>>> -----------------------
>>>         |   'O'
>>>
>>> with this string: "X  O"
>>>
>>> The nice thing about that representation is that it is each to identify
>>> which cells are filled or empty, and it is easy to mark a cell with an 'X'
>>> or 'O'.
>>>
>>> The problem with the representation is that it is difficult to determine
>>> when a player has won.
>>>
>>> Can you recommend a representation that makes it easy to:
>>>
>>> 1. determine when a player has won
>>> 2. identify cells that are filled or empty
>>> 3. mark an empty cell
>>>
>>> /Roger
>>>
>>> _______________________________________________
>>> Beginners mailing list
>>> Beginners at haskell.org
>>> http://www.haskell.org/mailman/listinfo/beginners
>>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130319/c6500a08/attachment.htm>

KC
Reply | Threaded
Open this post in threaded view
|

A good data structure for representing a tic-tac-toe board?

KC
In reply to this post by Costello, Roger L.
You may want more than one data structure.
For example, one for machine use and another for display to the user.

Since your data structure is "relatively" small, lists should be fast
enough and strings are lists.


On Mon, Mar 18, 2013 at 8:54 AM, Costello, Roger L. <costello at mitre.org> wrote:

> Hi Folks,
>
> Currently I am representing a tic-tac-toe board as a string, with 'X' denoting player 1 and 'O' denoting player 2. For example, I represent this 2x2 game board:
>
>      'X'        |
> -----------------------
>         |   'O'
>
> with this string: "X  O"
>
> The nice thing about that representation is that it is each to identify which cells are filled or empty, and it is easy to mark a cell with an 'X' or 'O'.
>
> The problem with the representation is that it is difficult to determine when a player has won.
>
> Can you recommend a representation that makes it easy to:
>
> 1. determine when a player has won
> 2. identify cells that are filled or empty
> 3. mark an empty cell
>
> /Roger
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners



--
--
Regards,
KC