One of the methods is an implementation of the minimax algorithm. How would I go about testing this?

I'm a bit surprised by this question. My first reaction would "test it like you always test", but apparently, that isn't working for you. Which makes me wonder, how *do* you test? I test by giving the functionality I want to test input of which I know the output should be, and whether what I get is what I expect. Why wouldn't that work for a minimax algorithm? That algorithm doesn't depend on the phases of the moon, does it?

It's the same for the XS code. Test it the same way as you test Perl code. For the user it doesn't matter whether the implementation is pure Perl or XS, so why should it matter for the tests?

Abigail

The issue I'm grappling with is figuring out input and output for a function that depends on nearly every capability of every other class in the system. Now, that may be a design concern that's coming out in testing. If that's the case, then I need to redesign, and that's ok. But, I've never written tests for a function as ... far-reaching as my implementation of minimax seems to be. My largest concern is that I don't know if I'll have enough coverage in the tests. But, maybe I should start writing tests and see what happens. I just wanted to design at least one portion of the system before writing it. *sighs*

The XS portion wasn't a matter of how to test it, but that I want to write in XS, so I need the tests. :-)

------
We are the carpenters and bricklayers of the Information Age.

The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

The way to test an abstract class is to test one or more simple concrete examples of that class. For Game::Die you would test a few easy types of die: 1d6, 1d10, 2d20, etc. For Game::AI, you may have to make a tiny example game that uses all the features of an AI. It doesn't have to be a fun game, or a real game. Find a Tic Tac Toe game and implement that AI.

I don't know what the allure for XS would be in a minimax framework. It's so thin, and won't be the real work of any minimaxable game. Build a tree of foreseen board positions, using one AI per player. One method on AI can be coded to simply return a list of all legal possible moves, instead of rushing to commit the actual board to a single move. Then for any given board position, you have to rank the "value" of that position or the move that achieved it. The only real "work" involved would be to weed the tree of disastrous courses of action before you spent a ton of time asking the AI to think farther along those lines.

--
[ e d @ h a l l e y . c c ]

i think the problem you describe is a significant one, encountered less by modules which are less ambitious, algorithmically speaking:

it is really to do with the fact that your problem is dependent on a very large number of system states.

yes, you can test a few of these states for validity, whether the game plays well, but the combinatoric explosion results in test coverage that is less than statistically adequate. this has important implications for unit testing, for this type of problem.

see http://satisfice.com/testmethod.shtml for a perl implementation of one approach to solving the problem of testing for systems with large numbers of states - tho i believe your problem complexity bigger than those *it* tests.

at the site above, two different types of testing, exploratory versus scripted, are distinguished. i believe you need exploratory, tho most of our harnesses are geared towards 'scripted'.

perhaps halleys suggestion of forcing play for a small game works best, tho to do this with the range of games you have is a significant overhead.

best of luck, anyway.

...wufnik

-- in the world of the mules there are no rules --

Your situation is slightly different in that you already have code, but I would suggest that you should first document what you've written do far. Documentation should include, for each method:

• the calling convention (eg named parameters vs an ordinary list);
• which parameters are required and which are optional;
• any restrictions on the values passed;
• the return values;
• how and in what circumstances the methods should fail;
• any gotchas and corner-cases

If you are implementing complex algorithms, you should in theory derive the results to test your code's correctness in some other way, but if you are confident that your results are correct, then I'd say it's OK to cheat and to use the module to generate its test results, provided that you throw in a couple of the simpler results calculated by hand yourself. Using the module to generate results which you then hard-code into the test suite is still useful, as it provides a check in the future to make sure you haven't inadvertently broken the algorithm in the next release.

Speaking of documentation, that's the other hot item on my to-do list. How would you document 26 classes and how they all go together, given that all of the leaf classes have multiple inheritance. (This is because Board-specific functionality is stored in Games::Board and Othello-specific functionality is in Games::Othello, so Games::Board::Othello inherits from Games::Board and Games::Othello.)

Part of my issue seems to be that the design grew organic, so attempting to organize it looks like a huge problem, in my mind. I'm running into the "too big for my head" block.

------
We are the carpenters and bricklayers of the Information Age.

The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6

Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.

Personally, I like maps. So I would probably start with an Entity Relationship Diagram. After that, I would probably do some kind of interaction diagram.

I have been at that place before, it does help to have a map just to keep straight in my brain where in the code I am.

I would still document each class seperately, pointing out when it takes instances of your other classes as parameters - eg "this method takes named parameters. The 'bar' parameter is required, and must be a Bar object, the 'baz' parameteris optional ...". Document what the method does, including how it interacts with the objects passed to it. However, if any of those objects in turn do stuff to other objects, that is properly documented in their docs, not in the ones for the original class.

As for documenting inheritance, that's pretty simple. Something like this, perhaps:

=head1 INHERITANCE

This module inherits methods from Foo and Bar

=head1 METHODS

The following methods override methods in Foo:

...

The following methods override methods in Bar:

...

The following methods are additionally defined:

...
[download]

If you end up inheriting the same method name from two seperate base classes, then I suggest that you provide your own implementation which explicitly calls the correct base method, and you should also document that prominently.

So you will end up with a bunch of docs explaining what each method of each class does and how those methods interact with the outside world. From that, you can write your tests and it will probably now be a lot clearer to you what all the interactions are. Then some documentation covering very briefly what each class does and what it represents, and what their interdependencies are should be quite easy to write. You might be able to draw a diagram for that if it's reasonable simple - and if you can, do so, as pictures convey an awful lot more information than words in this situation. I believe there are automated tools for doing this, such as Autodia, although I don't use such things myself, preferring to grovel over the docs and draw on real paper with a real pencil ;-)

Consider a design that has not only inheritance but composition, maybe like:

package A;
...
package A::a;
use base 'A';
...
package A::b;
use base 'A';
...
package B;
use A; # A is abstract and contains 'factory' methods, so we
       # will actually use instances of A::a or A::b
...
package C;
use B;
...
package D;
use C;
use XYZ; # not our code...something we installed
...
[download]

Is part of your question how to write tests for D that will cover all the stuff in the included packages? That's a good question...I'm curious to find out The Answer™, but I think halley was on the right track.

From my own experience, this is simply one of those areas where you have to work from bottom to top: write the tests for A (including its subclasses), then those for B, and on up.

My insight, shallow as it might be, is based on a toy program (an "address book") I'm experimenting with. Substitute the following:

The tests require some thought and planning. I have separate test cases for the simplest cases (A::a), and slowly work up to the bigger ones (so far up to the C level).

To me it seems test design gets more complex if you want to "automate" testing. For example, lots of things in my toy app depend on the data available in backend database. I anticipate (unless The Answer™ proves otherwise) that I'll have to include in any automatic test scripts the creation and population of a test database.

So, I don't think I've really answered your question; it seems to be my question also (unless they're not really the same question and I'm projecting mine onto yours :-)).

Update: Another post has given me some more things to think about with respect to the question.

...every application I have ever worked on is a glorified munger...

I agree with you t'mo - where your classes interact with data in some external resource, such as a file or database, you can't test without test data.

The best solution I've found is to script as much of the database creation and population as possible ay you suggest.