[Discussion] Kalah Network Protocol

[phikal]

Hi,

I have heard the complaint a few times, that the tournament "has to" programmed in Java/Scala (I know there are other JVM based languages, but it's still limiting). One idea was to implement a server, that interfaces with the existing infrastructure, where clients communicate via a network/local connection. I'm not sure if there will be enough time to implement this properly for this cycle, but I wanted to bring the point up anyway.

I've made a few sketches of how this would look like, but skimming the structure of the project, I don't think it can be trivially implemented without some restructuring.

The obvious advantage would be that nobody has to use a language they are uncomfortable with, so there are fewer advantages and disadvantages. The disadvantages would be that some languages can perform faster than others, there might delay, and monitoring the usage or resources could be harder. Also, security-wise, the clients would have to be containerised, to not manipulate the host system.

A protocol shouldn't have to be anything complicated, with some inspiration from using GTP, I could imagine something like, that should be parsable by even a programm written in C, without too much work.

  # this is a comment
  # lines beginning with ">" are client input, "<" are client output
  # the first two charachters of a line aren't part of the protocol
> version 1
> kahla 7 5 # start Kahla(7, 5)
> assign-player south
< sow-pit 3 south
> sow-pit 4 north
...
< resign

If there is any interest, further details could be discussed. I'm neither an expert when it comes to game protocols, nor Kalah, so there are certainly things that could be improved.

Even though there are issues, and work would have to be done, code has to be implemented, I do think it would be interesting. I wouldn't have opened the issue if that wasn't the case.

[tkw1536]

This is something that might be feasible for next year.

[tkw1536]

This might make it significantly easier to enforce resource limits, as when a response isn't received within a certain time limit the process could just be killed.

[phikal]

This might make it significantly easier to enforce resource limits, as when a response isn't received within a certain time limit the process could just be killed.

Time limits, yes, but memory might be harder. So some container architecture might be necessary, both to assue that bots don't break the system, but also for example to not just access a server with some ideal gameplay database.

[tkw1536]

Yes, but that isn't an issue. We already have a lot of stuff running on docker.

The other advantage I would see from this is we could give students a server that can easily test their own implementation.

[phikal]

Yes, that was my main intent behind the suggestion.

[tkw1536]

I'd love to build something for next year, once the correcting for this year is finished.

[phikal]

Tom Wiesing notifications@github.com writes:

I'd love to build something for next year, once the correcting for this year is finished.

I was planning on doing the same, or at least to create a prototype. Now that I have been playing around with Kalah for long enough, I think I understand it well enough to specify a reasonable protocol, and implement it in a few languages.

-- Philip K.

[jfschaefer]

There is one concern with supporting multiple languages: People who know e.g. C would have a very significant advantage over people who only know e.g. Python because they can get a better search depth with the same algorithms. That is particularly problematic because many non-CS students are taking the lecture.

[kohlhase]

I would not be terribly concerned about the constant factor you can get by choosing a lower-level programming language. After all the problems are exponential, so a constant factor will only get you a constant summand in search depth. Also an implementation in C will make the implementation by a constant (not small) more difficult, so I think this disadvantage will eat up the processing advantage. How exactly languages like Rust fare here I do not know.

[phikal]

Jan Frederik Schaefer notifications@github.com writes:

[1:text/plain Hide]

There is one concern with supporting multiple languages: People who know e.g. C would have a very significant advantage over people who only know e.g. Python because they can get a better search depth with the same algorithms. That is particularly problematic because many non-CS students are taking the lecture.

One way that this could be mitigated, though I'm not certain if it's "fair" or not, would be to dynamically adapt how much time a player has to make a move. For example: the arbiter-program might evaluate who's winning, and give the loosing side more time, or reduce the time the winner has (which will only work up until some point).

-- Philip K.