4
\$\begingroup\$

EDIT: I simplified the challenge and posted it in the sandbox. Summary: python2/python3 compatible judge script that works on a solution's output (instead of fork/exec-ing the solution); users are trusted not to cheat; arbitrary large file for input instead of randomness; no time limit; totalScore = gameScore - codeSize

I'm thinking of designing a single-player game strategy challenge in which programs are fed lines on stdin, to which they respond on stdout. A program must respond to the current line before learning the next one. This is similar to how the popular Moby Dick challenge works. Ideally, I would provide a judge program that forks the solution as a separate process, supplies the input and computes the score.

What language should I use for an easy-to-run, fast, cross-platform judge? From the mainstream I speak Python (it may be too slow), C (but only on Linux), Java and JavaScript (for some users installing a JDK or Node may be too much bother). Or should I ask the users to rewrite the judge in their own language, perhaps as a separate challenge, and risk having many of them give up?

What would be a good scoring scheme that discourages excessive use of resources? I was thinking some linear combination of code size, timing (self-measured? hard limit?), and challenge-specific "points". Would it be too rude to tweak a published formula and ask everyone to rejudge?

\$\endgroup\$

2 Answers 2

Reset to default
5
\$\begingroup\$

Python is a good choice. Writing cross-platform code takes very little work (basically just don't use stuff in the os module), and it's really not all that slow. It will suit your needs just fine.

However, C is also a decent choice, so long as you write standard-conforming C (C11). The code should be portable as long as you're careful (don't assume things like word size or integer size - use the fixed-width types in the standard library).

\$\endgroup\$
9
  • \$\begingroup\$ I'm leaning towards Python. It's considerably slower than C but at least its docs claim compatibility for subprocess.Popen(). I don't think C offers a cross-platform way to do start processes. Windows has its own APIs, very different from fork()/exec(). \$\endgroup\$
    – ngn
    Feb 7, 2018 at 2:25
  • \$\begingroup\$ @ngn Yeah, fork is tricky in C. With Python, the subprocess module is really nice. \$\endgroup\$
    – user45941
    Feb 7, 2018 at 2:25
  • 3
    \$\begingroup\$ @ngn have you tried PyPy? If it does what you need it will usually run several times faster than the standard Python interpreter. It runs Python programs and supports most aspects of Python \$\endgroup\$
    – trichoplax is on Codidact now
    Feb 7, 2018 at 18:19
  • \$\begingroup\$ @trichoplax Thanks, I'll give it a try, though the point here is to make it easy and fast for solvers of my challenge, not for me. \$\endgroup\$
    – ngn
    Feb 7, 2018 at 18:29
  • 4
    \$\begingroup\$ I thought of PyPy because if you write the Python code so that it runs with PyPy, then people who want it fast can run it through PyPy, and people who don't want to download PyPy can run it slower on Python. For extra wide appeal, you can write it to be compatible with both Python 2 and Python 3, so people can just use whatever comes built in with their operating system and not have to install anything. \$\endgroup\$
    – trichoplax is on Codidact now
    Feb 7, 2018 at 19:14
  • 1
    \$\begingroup\$ I am not 100% sure, but I suspect that piping stuff through STDIN/STDOUT is relatively slow, so you'd lose most of the speed benefits of C anyway, unless the evaluation process itself is computationally intensive. \$\endgroup\$
    – N. Virgo
    Feb 11, 2018 at 4:06
  • \$\begingroup\$ @Nathaniel That's a good point. Pipes will definitely be the dominating factor for performance, so the underlying language won't matter as much. Given that, using a language with a good high-level interface for IPC (like Python) is the best choice IMO. \$\endgroup\$
    – user45941
    Feb 11, 2018 at 15:45
  • 1
    \$\begingroup\$ @trichoplax FYI: As a good sceptic, I measured. PyPy runs my program about 3-3.5 times faster than Python2 (Python3 is slower in my case). Thanks again for letting me know about it! \$\endgroup\$
    – ngn
    Feb 13, 2018 at 23:22
  • \$\begingroup\$ @ngn glad to hear it helped! If you still want it to be faster, PPCG is a great place to get help optimising such things... \$\endgroup\$
    – trichoplax is on Codidact now
    Feb 16, 2018 at 1:02
0
\$\begingroup\$

For the language I recommend Python, for similar reasons to what Mego says.

For discouraging excessive use of resources, I would recommend to consider why you want to do this. Are you planning to verify all the answers yourself? (That would be a lot of work, and I would recommend trusting people instead - the community can usually spot if someone is trying to cheat, and it happens rarely in any case.) Or are restrictions on resource use an inherent part of the challenge?

If neither of these is the case, I would recommend not trying to restrict it. If someone is willing to put tons of resources into something then just let them - it could lead to an interesting answer. (See, for example, Anders Kaseorg's answer to Paint Starry Night. He built a GPU machine specifically for the challenge and it led to a really interesting answer.)

If limitations on resource use are an inherent part of the challenge, I recommend sticking to code size as the only limited resource. It's a fun constraint to satisfy, it's easy to verify, and it's the kind of challenge people on this site like. You can do this by limiting the size of the code (as per the Starry Night challenge) or just by including code length in the score (as per Write Moby Dick, or just about any Code Golf challenge).

\$\endgroup\$
4
  • \$\begingroup\$ Thanks, that's all good advice. I don't plan to test everything. The challenge isn't terribly resource-hungry (at least the judge part; strategies may go wild), but it does involve randomness, so my concern is more about the ability to tell apart good from bad strategies. The game itself scales well - I can set the number of "steps" (interactions between judge and solution) anywhere between hundreds and millions. I just have to pick some number that (a.) wouldn't discriminate against weak hardware, like my own; and (b.) wouldn't give Fortuna too much weight. I'll make some experiments. \$\endgroup\$
    – ngn
    Feb 11, 2018 at 7:10
  • \$\begingroup\$ @ngn hmm, randomness is tricky, since it would make it hard (impossible?) to calculate a consistent score. You could require that people average their score over 100 (or 1000 or 10000) runs, which would automatically discourage excessive resource use, but there would still be an element of luck in what score you get (and hence a danger that people will run the scoring multiple times until they get a good one). One way around this is to fix the random seed, so that the runs are actually deterministic, but this may or may not work for your challenge, depending on its details. \$\endgroup\$
    – N. Virgo
    Feb 11, 2018 at 10:46
  • 1
    \$\begingroup\$ Downvoted? This answer seemed to me rather useful. Is there anything wrong with it that I should know about? \$\endgroup\$
    – ngn
    Feb 12, 2018 at 18:06
  • \$\begingroup\$ @ngn I can only guess about the downvote, but on reflection it's possible someone might object to my approach to resource use, on the grounds that we should all be on a level playing field. If a challenge becomes primarily about who can put in the most computing power, that would not be a good thing. (I don't think there is any danger of that happening with your challenge though, having looked at your sandbox post.) \$\endgroup\$
    – N. Virgo
    Feb 13, 2018 at 0:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .