Hash table for connect four

This is a discussion on Hash table for connect four within the C++ Programming forums, part of the General Programming Boards category; I'm trying to make a hash table for a connect four program that stores different board positions. The problem I ...

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Hash table for connect four

    I'm trying to make a hash table for a connect four program that stores different board positions. The problem I am having though is finding a suitable key reference so that each key doesn't have too many to sort through.

    My first attempt just had 48 keys, and a board was stored in the proper key depending on how many spots on the board were taken up (its a 6x8 board). The problem though was that some keys ended up managing over 4000 boards and I've only just begun.

    Anyone have an idea for a key function that can span it out to say at most 30-50 boards per key (even better if less)? It would have to be a property of the board object so that the same board will always produce the same key number.

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Couldn't you just modify a hashing scheme like the one
    most chess programs use
    http://www.seanet.com/~brucemo/topics/zobrist.htm
    I don't think it has to be all that efficient since
    chess has more possible positions than connect 4.

    This has a program that solves connect 4 and lots more infomation.
    http://www.ce.unipr.it/~gbe/velena.html

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Okay, thanks. I don't have time to look at those right now to see if they'd work with what I got, but I'll look tonight!

    Not sure why it didn't occur to me that examples of connect four hashes might be available on the internet!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 10:23 PM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 06:06 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-25-2007, 12:36 AM
  4. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 07:54 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 10:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21