Thread: Searching for new challenges

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    147

    Searching for new challenges

    Hi,

    I have been developing a chess engine for two years now. It has been a very entertaiment and didactic experience where you compite with other engines.

    Althought I will not leave chess programming (I like it a lot and it is very addictive), I would like to know if there are other games/project/challenges to try programming skills agains others.

    do you know any?

    thanks.
    FS

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,436
    For a bit of low-level fun, try Core War - Wikipedia, the free encyclopedia

    http://en.wikipedia.org/wiki/Go_(game) has a game tree which is far bushier than a chess game tree
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Note that both chess and Go are two-person zero sum games with full information. Hence, there's always an optimal algorithm. In particular, there's the Minimax-algorithm, which is always optimal, but slightly inefficient on our current machines.

    If you're interested in more challenging problems, check out the following two:

    1)
    Last Friday I've been told of an interesting open question:

    Consider MICB, the problem of finding a minimal integral cycle basis in graphs. So far, it is known that MICB is NP-hard.

    Question: is MICB NP-complete?

    Find a proof or show the converse by finding a P-complete algorithm which computes a solution.

    If you find a solution, please let me know.


    2)
    Today I discovered the following problem. It seems pretty easy, but given that it took two years from the release of the first Malbolge interpreter to the first Malbolge program (a Hello-World-program), it's probably a bit harder than it looks at first sight.

    It is not known whether Malbolge is Turing-complete. Proof that it's not or show the converse, e.g. by implementing a translator from any Turing-complete language to Malbolge. A nice candidate for such a Turing-complete language is BrainF, because of its extremely simple syntax and its very restricted set of operations.

    I strongly believe that it's possible to implement such a translator, but the semantics of Malbolge turn this task into a horrible nightmare.


    Greets,
    Philip
    Last edited by Snafuist; 05-26-2009 at 09:47 AM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. C++ std routines
    By siavoshkc in forum C++ Programming
    Replies: 33
    Last Post: 07-28-2006, 12:13 AM
  3. Visual C++ 2005 linking and file sizes
    By Rune Hunter in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2005, 10:41 PM
  4. Searching and matching strings: segmentation fault
    By Smola in forum C Programming
    Replies: 18
    Last Post: 07-11-2005, 12:25 AM

Tags for this Thread